我们在这章讨论字典和集合，因为它们背后都是哈希表，下面是本章的大纲
如果一个对象有一个哈希值，而且在生命周期中不被改变（它需要实现一个 __hash__() 方法），而且可以与其它对象比较（需要实现 __eq__() 方法），就是可散列化的。原子不可变数据类型（str, bytes 和数值类型）都是可散列类型，fronenset 也是可散列类型，因为根据其定义，frozenset 只能容纳可散列类型，元祖的话，只有当一个元组的所有元素都是可散列的，元组才是可散列的。
In [2]:
tt = (1, 2, (30, 40))
hash(tt)
Out[2]:
In [5]:
t1 = (1, 2, [30, 40]) # 其中列表是可变的，所以没有哈希值
hash(t1)
In [6]:
tf = (1, 2, frozenset([30, 40])) #frozenset 是冻结的集合，不可变的，所以有哈希值
hash(tf)
Out[6]:
In [8]:
a = dict(one = 1, two = 2, three = 3)
b = {'one': 1, 'two': 2, 'three': 3}
c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
d = dict([('two', 2), ('one', 1), ('three', 3)])
e = dict({'three': 3, 'one': 1, 'two': 2})
a == b == c == d == e
Out[8]:
除了常规语法以及 dict 构建之外，我们可以使用字典推导来构建字典，dictcomp 会由任何一个可迭代对象产生一对 key:value 来构建 dict，下面是使用字典生成式的一个例子:
In [11]:
DIAL_CODES = [
(86, 'China'),
(91, 'India'),
(1, 'United States')
]
country_code = {country: code for code, country in DIAL_CODES}
country_code
Out[11]:
字典有一个内置方法 d.update(m, [**kargs]) 它会先判断 m，如果 m 有 keys 方法， update 就将它当做映射处理，否则，会退一步，将 m 当做包含键值对 (key, value) 的迭代器，python 绝大多数映射类型构造方法都用了类似的逻辑。因此我们既可以使用一个映射对象来新建一个映射对象，也可以使用 (key, value) 键值对来初始化一个映射对象
当 dict 使用 d[k] 时，发现 k 不是现有键时，会抛出 KeyError 错误，我们知道 d.get(k, default) 可以代替 d[k]，给找不到的键一个默认值。这比处理 KeyError 异常方便，但是如果要更新某个键对应的值时，使用 __getitem__() 和 get() 效率都很低，就像下面的例子这样，dict.get 并不是处理找不到键的最好方法。
In [15]:
#!/usr/bin/env python
# encoding: utf-8
import sys
import re
WORD_RE = re.compile('\w+') # \w 是匹配任意字母或数字，+ 是匹配一次到任意次
index = {}
#with open(sys.argv[1], encoding="utf-8") as fp: #正常文件名是参数传的
with open("/home/kaka/test.txt", encoding="utf-8") as fp:
for line_no, line in enumerate(fp, 1): # line_no 是索引（从 1 开始），line 是行的内容
for match in WORD_RE.finditer(line): # 返回所有匹配子串，返回类型是迭代器
word = match.group() # group 获取该单词 （match 是一个对象）
column_no = match.start() + 1 # 获取列数，索引从 0 开始
location = (line_no, column_no) # 构造一个元组，内容是 (row, col)
# 这样写很糟糕，这里仅仅是为了演示
occurrences = index.get(word, []) # 判断该单词是否被添加过，没有返回 [ ]，注意返回的是原列表的一个备份
occurrences.append(location) # 为该 key 对应的值添加内容
index[word] = occurrences # 这要搜索 word 这个 key 第二次
for word in sorted(index, key = str.upper): # 按照字母顺序排序，忽略大小写
print(word, index[word])
我们处理 occurrences 的三行可以使用 dict.setdefault 来改为一行
In [16]:
#!/usr/bin/env python
# encoding: utf-8
import sys
import re
WORD_RE = re.compile('\w+') # \w 是匹配任意字母或数字，+ 是匹配一次到任意次
index = {}
#with open(sys.argv[1], encoding="utf-8") as fp: #正常文件名是参数传的
with open("/home/kaka/test.txt", encoding="utf-8") as fp:
for line_no, line in enumerate(fp, 1): # line_no 是索引（从 1 开始），line 是行的内容
for match in WORD_RE.finditer(line): # 返回所有匹配子串，返回类型是迭代器
word = match.group() # group 获取该单词 （match 是一个对象）
column_no = match.start() + 1 # 获取列数，索引从 0 开始
location = (line_no, column_no) # 构造一个元组，内容是 (row, col)
#如果单词没有这个 key，把单词和一个空列表放入映射，然后返回这个空列表，这样就不用二次搜索就可以被更新列表了
index.setdefault(word, []).append(location)
for word in sorted(index, key = str.upper): # 按照字母顺序排序，忽略大小写
print(word, index[word])
换句话说 index.setdefault(word, []).append(location) 与下面等价
In [18]:
#if key not in my_dict:
# my_dict[key] = []
#my_dict[key].append(new_value)
有时在找不到键时，希望返回一个默认值，这里有两种方法，第一种是使用 defaultdict 而不是普通 dict，第二种是自定义一个字典的子类，然后在子类中添加一个 __missing__ 方法，下面会讨论两种做法
在实例化 defaultdict 时候，需要给构造方法提供一个可调用对象，这个可调用对象会在 __getitem__ 找不到键时被调用，让其返回一个默认值，例如我们创建了一个这样的字典 dd = defaultdict(lit)，如果 'new-key' 键在 dd 中不存在的话，表达式 dd['new-key']会先调用 list 新建一个列表，把这个新列表作为值，'new-key' 作为键放到 dd 中，最后返回这个列表的引用。下面是上面问题使用 collections.defaultdict 的一个例子。
In [20]:
#!/usr/bin/env python
# encoding: utf-8
import sys
import re
import collections
WORD_RE = re.compile('\w+')
index = collections.defaultdict(list) # 使用 list 建立 defaultdict，将它当成 default_factory
#with open(sys.argv[1], encoding="utf-8") as fp:
with open("/home/kaka/test.txt", encoding="utf-8") as fp:
for line_no, line in enumerate(fp, 1):
for match in WORD_RE.finditer(line):
word = match.group()
column_no = match.start() + 1
location = (line_no, column_no)
# 如果不存在 word 键，会调用初始化传的 default_factory 产生一个预设值, 如果没有指定 default_factory，会产生 KeyError 异常
index[word].append(location)
for word in sorted(index, key = str.upper):
print(word, index[word])
工作原理: 当我们初始化一个 defaultdict 时候，要提供一个方法，当 __getitem__() 找不到键的时候，会用它产生一个预设值，这里我们将 list 传进去，每次调用会产生一个空列表。
注意：defaultdict 的 default_factory 只会在调用 __getitem__() 方法时起作用，在其它方法不起作用。例如 dd 是 defaultdict，k 是不存在的键， dd[k] 会调用 default_factory 产生一个预设值，而 dd.get(k) 仍然传回 None，下面是例子
In [23]:
import collections
index = collections.defaultdict(list)
print(index.get('hello'))
这背后一切的工程其实是 __missing__() 方法，它会在 defaultdict 遇到找不到键的时候调用 default_factory，而实际上这个特性是所有映射类型都可以选择去支持的。
__missing__ 方法映射处理找不到键时，底层使用的是 __missing__() 方法，基础的 dict 并没有这个方法，但是 dict 是知道有这个接口存在的，所以你可以继承 dict 并实现 __missing__() 方法，如果 dict.__getitem__() 在找不到键时就调用它，而非发出 KeyError
__missing__() 只被 __getitem__() 调用（即 d[k] 运算符），__missing__() 方法的存在，并不会影响到其它方法查询键的行为，例如 get 或 __contains__（in 运算符），这就是 defaultdict 只能与 __getitem__() 一起使用的原因
有时候我们希望查询时，映射类型里的键统统转成 str，下面是一个可编程电路板项目（Raspberry 和 Arduino 等）的例子，其中电路板上针脚可能是数字或字符串，比如 "A0" 或 "12"，但是为了方便查询，我们希望 my_arduino.pins[13] 也是可以的，这样可以快速找到 arduino 的第 13 个针脚。
In [13]:
class StrKeyDict0(dict):
# 找不到键会调用此函数
def __missing__(self, key):
# 如果找不到的键本身就是 str 类型，直接抛出异常
# 这个判断是必要的，如果没有它，当 key 不是字符串，则会递归调用
if isinstance(key, str):
raise KeyError(key)
# 如果找不到的键不是字符串，那么将其转成字符串查找
return self[str(key)]
def get(self, key, default=None):
try:
# get 方法使用 self[key] 的方式调用 __getitem__() 方法查找，那么某个键不存在的话，还可以通过 __missing__() 给它一个机会
return self[key]
except KeyError:
# 如果抛出 KeyError，那么说明 __missing__() 也失败了，返回 default
return default
def __contains__(self, key):
# 先按照键原来的值查找，找不到将其转成字符串查找，注意 or 返回的不是 true 和 false，而是第一个不为假的那个值
# 例如 0 or 2 返回 2
# 注意这里没用 key in self, 这是因为这回导致 这个函数被递归调用，所以采用了显式的方法，直接在 self.keys() 中查询
return key in self.keys() or str(key) in self.keys()
d = StrKeyDict0([('2', 'two'), ('4', 'four')])
d['2']
Out[13]:
In [14]:
d[4]
Out[14]:
In [15]:
d[1]
In [16]:
d.get('2')
Out[16]:
In [17]:
d.get(4)
Out[17]:
In [18]:
d.get(1, 'N/A')
Out[18]:
In [19]:
2 in d
Out[19]:
In [20]:
1 in d
Out[20]:
像 key in my_dict.keys() 的这种操作是很快的，即使映射类型对象很庞大也没关系，因为 dict.keys() 返回的是一个视图，视图就像一个集合，而且跟字典类似的是，在视图中查找一个元素速度很快。
collections.OrderedDict
collections.ChainMap
下面是 collections 文档介绍 ChainMap 对象里的一个具体使用实例，包含了下面这个对 Python 变量查询规则的代码片段
import builtins
pylookup = ChainMap(locals(), globals(), vars(builtins))
collections.Counter
import collections
ct = collections.Counter('abracadabra')
ct
#Counter({'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2})
ct.update('aaaaazzz')
ct
#Counter({'a': 15, 'b': 2, 'c': 1, 'd': 1, 'r': 2, 'z': 6})
ct.most_common(2)
#[('a', 15), ('z', 6)]
要建立新的映射类型，继承 UserDict 要比继承 dict 容易，这体现在，我们可以很容易的改进前面的 StrKeyDict0 类，将所有的键都存成 str 类型。
我们更倾向继承 UserDict 而不是 dict 的原因是，dict 在某些方法的实现上会走一些捷径，导致我们不得不在它的子类重写这些方法，而 UserDict 就没有这个问题。
注意 UserDict 没有继承dict，而是内部有一个 dict 实例，称为 data，这是 UserDict 最终存储数据的地方，这样做的好处是，相比上面 StrKeyDict0 类，UserDict 的子类在实现 __setitem__ 这种方法时，可以避免不必要的地柜。而且可以使 __contains__ 方法更简洁。
下面的例子不仅比 StrKeyDict0 类更简洁，功能还更完善，不但把所有的键都以字符串的方式存储，还能处理一些创建或者更新实例时包含非字符串类型的键的意外情况
In [29]:
import collections
class StrKeyDict(collections.UserDict):
def __missing__(self, key):
if isinstance(key, str): # 这个方法和之前的一模一样
raise KeyError(key)
return self[str(key)]
def __contains__(self, key): #这个方法更简洁一些，因为已经放心假设所有的键都是字符串
return str(key) in self.data
# 这个方法会把所有的键都转成字符串
def __setitem__(self, key, item):
self.data[str(key)] = item
因为 UserDict 是 MutableMapping 的子类，所以 StrKeyDict 里的剩下的那些映射类型方法都是从 UserDict、MutableMapping 和 Mapping 这些超类继承来的，特别是最后的 Mapping 类，它虽然是一个抽象基类（ABC），但是却提供了好几个使用的方法，下面是比较值得关注的方法:
MutableMapping.update:
__init__ 里，让构造方法可以利用传入的各种参数（其它映射类型，元素是 (key, value) 对的可迭代对象和键值参数）来新建实例，因为这个方法背后用的是 self[key] = value 来添加新值的，所以它实际是在使用我们的 __setitem__() 方法。Mapping.get
__getitem__() 一致，而在我们的这个例子中就不用了，因为它继承 Mapping.get() 方法，而 Python 源码显示，这个方法的实现方式和 StrKeyDict0.get() 是一模一样的。Python3.3 后，types 提供 MappingProxyType 包装类，当你给它一个映射后，它返回一个只读的视图，但它是原始映射的动态展示，也就是说，你可以在视图中中看到原始映射的改变，但是无法通过它改变原始映射。下面的例子说明了这点：
In [30]:
from types import MappingProxyType
d = {1: 'A'}
d_proxy = MappingProxyType(d)
d_proxy
Out[30]:
In [31]:
d_proxy[1]
Out[31]:
In [32]:
d_proxy[2] = 'x'
In [34]:
d[2] = 'b'
d_proxy
Out[34]:
In [1]:
l = ['spam', 'spam', 'eggs', 'spam']
set(l)
Out[1]:
In [2]:
list(set(l))
Out[2]:
集合的元素必须可散列的，set 类型本身是不可散列的，但是 frozenset 可以，所以可以在 set 中放入 frozenset 元素。
为了保持唯一性，集合实现了很多基础的中缀运算符， a | b 代表 a 和 b 的并集， a & b 代表 a 和 b 的交集，a - b 为 a 和 b 的差集。合理使用这些操作，不仅可以使代码变少，而且还能减少 Python 程序的运行时间。
例如，我们有一个电子邮件地址的集合（haystack），还要维护一个较小的电子邮件地址集合（needles），然后求出 needles 中有多少地址同时也出现在了 haystack 中，借助集合实现非常简单。
In [ ]:
#found = len(needles & haystack)
但是上面的语法只支持集合，我们让其支持所有可迭代类型
In [ ]:
#found = len(set(needles) & set(haystack))
# 也可以写成
#found = len(set(needles).intersection(haystack))
In [3]:
# 下面这种方式比 set([1]) 快，因为后者需要先从 set 这个名字查询构造方法，然后新建一个列表，最后再把列表传到构造方法中
# 但是如果像 {1, 2, 3} 这种字面量，Python 有一个专门叫作 BUILD_SET 的字节码创建集合
s = {1}
type(s)
Out[3]:
In [4]:
s.pop()
Out[4]:
In [5]:
s
Out[5]:
In [8]:
s = {}
type(s) #看到这样定义的是一个字典，而不是 set
Out[8]:
In [9]:
from dis import dis
dis('{1}')
In [10]:
dis('set([1])')
看到 {1} 的方式直接执行了 1 的赋值， set([1]) 步骤比较多
frozenset 常数定义没有特殊的语法，必须使用构造方法。Python 3 里 fronzenset 的标准字符串表示形式看起来就像构造方法调用一样。来看这段控制台对话
In [11]:
frozenset(range(10))
Out[11]:
In [13]:
from unicodedata import name #用 name 函数获取字符的名字
{chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i), '')} # 将字符名里有 SIGN 的单词挑出来，放到集合
Out[13]:
集合中缀运算符要求两个运算元都是集合，但是所其它所有的方法不是这样，例如要产生 a，b，c，d 的并集，a.union(b, c, d) 只要求 a 是集合，b，c，d 是可迭代对象就行
这一节会回答下面几个问题：
我们有一个 1000 万个不重复双精度浮点数的字典，名叫 haystack，还有一个 1000 个浮点数的 needles 数组，其中 needles 中的 500 个数字可以在 haystack 中找到，另外 500 个肯定找不到。
我们使用下面代码来测试下面代码的运行时间（用 timeit 模块可以测试速度）
found = 0
for n in needles:
for n in haystack:
found += 1表明当 haystack 个数是 1000 的时候，需要 0.000202 秒，当 haystack 的个数是 10,000,000 的时候，只需要 0.000337 秒。
作为对比，我们把 haystack 换成 set 和 list 类型，做了同样的实验。对于 set，我们除了运行上面的代码，还测试了用交集计算 needles 出现在 haystack 中的次数运行时间
found = len(needles & haystack)我们发现，最快的是集合交集花费的时间，最慢是列表所花费的时间，集合使用两个 for 循环操作和字典用时差不多。
散列表其实是一个稀疏数组（总有空白元素的数组），散列表的单元称为表元，在 dict 散列表中，每个键值对都占用一个表元，每个表元有两部分，一个是对键的引用，一个是对值的引用。因为所有表元大小一致，所以可以通过偏移量来读取某个表元。
因为 python 会保证大概还有三分之一的表元是空的，所以快要到达这个阈值的时候，原有的散列表会被复制到一个更大的空间中。
如果把一个对象放到散列表，那么首先要计算这个元素键的散列值，Python 中可以用 hash() 方法来做这件事。
内置的 hash() 方法可以用于所有的内置类型对象，如果自定义对象调用 hash() 方法，实际上是运行自定义的 __hash__()。如果两个对象相等，那么它们的散列值必须相等，否则散列表就不能正常运行了。例如 1 == 1.0 为真，那么 hash(1) 和 hash(1.0) 也必须为真，但其实两个数字（整数和浮点）内部结构是完全不一样的。
为了获取 my_dict[search_key] 背后的值，Python 首先会调用 hash(search_key) 来计算 search_key 的散列值，把这个值的最低几个数字当做偏移量，在散列表里查找表元（具体取几位取决于当前散列表的大小）。若找到表元是空的，抛出 KeyError 异常。如果不是空的，则表元里会有一对 found_key:found_value。这时候 Python 会校验 search_key == found_key 是否为真，如果它们相等的话，就会返回 found_value
如果 search_key 和 found_key 不匹配的话，这种情况称为散列冲突，发生这种情况是因为，散列表所做的其实是把随机的元素映射到只有几位的数字上，而散列表本身的索引有只依赖这个数字的一部分。为了解决散列冲突，算法会在散列值中再取几位，然后用特殊方法处理一下，把新得到的数字再索引来寻找表元（C 语言写的用来打乱散列值位的算法名字叫 perturb）。如果这次找到的表元是空的，则抛出 KeyError，如果非空，看看是否匹配，如果键匹配，返回这个值，又发生了散列冲突的话，重复之前步骤。
添加新元素和更新现有元素操作几乎和上面一样。只不过对于前者，发现空表元会放入一个新表元，后者找到相应表元会将原表元的值替换。
另外插入新值时，Python 可能会按照散列表的拥挤程度来决定是否重新分配内存并为它扩容，如果增加了散列表大小，那么散列值所占的位数和用作索引的位数都会随之增加，这样做的目的是为了减少发生散列冲突的概率。
表面看来这个算法很费劲，实际上就算 dict 有上百万个元素，多数的搜索并不会有冲突发生，平均下来每次搜索可能有一到两次冲突，在正常情况下，最不走运时候键所遇到的冲突次数一只手也能数过来。
下面会讨论散列表给 dict 带来的优势和限制。
一个可散列的对象必须满足以下条件
__eq__() 方法判断是否相等如果你自定义了 __eq__()，一定要保证 a == b 和 hash(a) == hash(b) 结果相同，否则可能造成字典无法处理你的元素，另一方面，如果一个含有自定义的 __eq__() 依赖的类处于可变状态，那就不要在这个类中实现 __hash__() 方法，因为它的实例是不可散列的。
由于字典使用了散列表，而散列表又是稀疏的，这导致它在空间上效率低下，举例而言，如果我们需要存放数量巨大的记录，那么存放在元组或者具名元组构成的列表是一个比较好的选择。最好不要根据 JSON 风格，存放到字典中，用字典取代元组的原因有两个，其一是避免了散列表所耗费的空间，其二是无需把记录中字段的名字在每个元素都存一遍。
在用户自定义类型中 __stots__ 属性可以改变实例属性的存储方式，由 dict 变成 tuple，相关细节在第 9 章会谈到。
记住我们现在讨论的是空间优化，如果你手里有几百万对象而机器只有几 GB 内存时才真正需要考虑空间优化，因为优化往往是可维护性的对立面。
dict 是典型的空间换时间。有着巨大的内存开销，但是它提供了无视数据大小的快速访问-只要字典可以被装到内存里。
当往 dict 里添加新键而又发生散列冲突时，新建可能会被安排存放到另一个位置。于是下面这种情况就会发生：由 dict([(key1, value1), (key2, value2]) 和 dict([(key2, value2), (key1, value1]) 得到的两个字典，在比较的时候，它们是相等的，但是如果在 key1 和 key2 被添加到字典过程中有冲突的话，这两个键出现在字典里的顺序是不一样的。
下面展示了这个现象，用同样的数据创建了 3 个字典，唯一的区别就是数据出现的次序不一样，可以看到，虽然键的次序是乱的，这 3 个字典仍然被视为相等的。
In [21]:
DIAL_CODES = [
(86, 'China'),
(91, 'India'),
(1, 'United States'),
(62, 'Indonesia'),
(55, 'Brazil'),
(92, 'Pakistan'),
(880, 'Bangladesh'),
(234, 'Nigeria'),
(7, 'Russia'),
(81, 'Japan')
]
d1 = dict(DIAL_CODES) # 数组元组顺序按照国家人口排名决定
print('d1:', d1.keys())
d2 = dict(sorted(DIAL_CODES)) # 数组元组顺序按照国家区号大小排名决定
print('d2:', d2.keys())
d3 = dict(sorted(DIAL_CODES, key = lambda x: x[1])) # 数组元组顺序按照国家字母顺序排名决定
print('d3:', d3.keys())
assert d1 == d2 and d2 == d3
可以看到这些字典是相等的，但是 3 个字典的顺序是不一样的
无论何时往字典添加新的键，Python 解释器都可能做出为字典扩容的决定。扩容导致的结果就是要建更大的散列表，并把字典已有的元素添加到新表中。这个过程可能产生新的散列冲突。导致散列表中键的次序变化。要注意的是，上面提到的这些变化是否发生以及如何发生都取决于字典背后的具体实现。因此你不能很自信的说自己知道背后发生了什么，如果你在迭代一个字典所有键的过程中同时对字典进行修改，那么这个循环可能跳过一些键，甚至跳过字典中已有的键。
由此可知，不要对字典同时进行迭代和修改。如果想扫描并修改一个字典，最好分成两步来进行，首先对字典进行迭代，得出需要添加的内容，把这些内容放到一个新字典里，迭代结束后再进行更新。
在 Python 3 中 .keys() .items() 和.values() 返回的都是字典视图。也就是说，这些方法返回值更像集合，而不是 Python 2 中那样返回列表。视图还有动态的特性，它们可以实时反馈字典的变化。
set 和 frozenset 的实现也依赖于散列表，但在它们散列表存放的只元素的引用（就像在字典里存放的只有键没有值）。在 set 加入 Python 前，我们都是把字典加上无意义的值当做集合来用的。
在上面提到字典和散列表的几个特点，对于集合来说几乎都是适用的。为了避免重复，我们简单总结一下：
如果对 dict 的顺序有要求，可以使用 OrderdDict，然而对于映射类型来说，排序并不是一个常用的需求，因此会把它排除在核心功能之外，以标准库的形式提供其他的衍生类型。