dict 类型不但在各种程序里广泛使用,它也是 Python 语言的基石。模块的命名空间、实例的属性和函数的关键字参数中都可以看到字典的身影。跟它有关的内置函数都在 __builtins__.__dict__模块中。
正是因为字典至关重要,Python 对它的实现做了高度优化,而散列表则是字典类型性能出众的根本原因。
集合(set)的实现其实也依赖于散列表,因此本章也会讲到它。反过来说,想要进一步理解集合和字典,就得先理解散列表的原理。
collections.abc 模块中有 Mapping 和 MutableMapping 这两个抽象基类,它们的作用是为 dict 和其他类似的类型定义形式接口(在Python 2.6 到 Python 3.2 的版本中,这些类还不属于 collections.abc
模块,而是隶属于 collections 模块)。
collections.abc 中的 MutableMapping 和它的超类的UML 类图(箭头从子类指向超类,抽象类和抽象方法的名称以斜体显示)
然而,非抽象映射类型一般不会直接继承这些抽象基类,它们会直接对dict 或是 collections.User.Dict 进行扩展。这些抽象基类的主要作用是作为形式化的文档,它们定义了构建一个映射类型所需要的最基
本的接口。然后它们还可以跟 isinstance 一起被用来判定某个数据是不是广义上的映射类型:
>>> my_dict = {} >>> isinstance(my_dict, abc.Mapping) True
这里用 isinstance 而不是 type 来检查某个参数是否为 dict 类型,因为这个参数有可能不是 dict,而是一个比较另类的映射类型。
标准库里的所有映射类型都是利用 dict 来实现的,因此它们有个共同的限制,即只有可散列的数据类型才能用作这些映射里的键(只有键有这个要求,值并不需要是可散列的数据类型)。
什么是可散列的数据类型?
如果一个对象是可散列的,那么在这个对象的生命周期中,它的散列值是不变的,而且这个对象需要实现 __hash__() 方法。另外可散列对象还要有 __qe__() 方法,这样才能跟其他键做比较。如果两个可散列对象是相等的,那么它们的散列值一定是一样的……
原子不可变数据类型(str、bytes 和数值类型)都是可散列类型,frozenset 也是可散列的,因为根据其定义,frozenset 里只能容纳可散列类型。元组的话,只有当一个元组包含的所有元素都是可散列类型的情况下,它才是可散列的。来看下面的元组tt、tl 和 tf:
>>> tt = (1, 2, (30, 40)) >>> hash(tt) 8027212646858338501 >>> tl = (1, 2, [30, 40]) >>> hash(tl) Traceback (most recent call last): File "", line 1, in TypeError: unhashable type: 'list' >>> tf = (1, 2, frozenset([30, 40])) >>> hash(tf) -4118419923444501110
一般来讲用户自定义的类型的对象都是可散列的,散列值就是它们
的 id() 函数的返回值,所以所有这些对象在比较的时候都是不相
等的。如果一个对象实现了 __eq__ 方法,并且在方法中用到了这
个对象的内部状态的话,那么只有当所有这些内部状态都是不可变
的情况下,这个对象才是可散列的。
一般来讲用户自定义的类型的对象都是可散列的,散列值就是它们的 id() 函数的返回值,所以所有这些对象在比较的时候都是不相等的。如果一个对象实现了 __eq__ 方法,并且在方法中用到了这
个对象的内部状态的话,那么只有当所有这些内部状态都是不可变的情况下,这个对象才是可散列的。
>>> 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 True
当字典 d[k] 不能找到正确的键的时候,Python 会抛出异常,这个行为符合 Python 所信奉的“快速失败”哲学。也许每个 Python 程序员都知道可以用 d.get(k, default) 来代替 d[k],给找不到的键一个默认的
返回值(这比处理 KeyError 要方便不少)。但是要更新某个键对应的值的时候,不管使用 __getitem__ 还是 get 都会不自然,而且效率低。dict.get 并不是处理找不到的键的最好方法。
"""创建一个从单词到其出现情况的映射""" import sys import re WORD_RE = re.compile(r'\w+') index = {} with open(sys.argv[1], 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) # 这其实是一种很不好的实现,这样写只是为了证明论点 occurrences = index.get(word, []) ➊ occurrences.append(location) ➋ index[word] = occurrences ➌ # 以字母顺序打印出结果 for word in sorted(index, key=str.upper): ➍ print(word, index[word])
❶ 提取 word 出现的情况,如果还没有它的记录,返回 []。
❷ 把单词新出现的位置添加到列表的后面。
❸ 把新的列表放回字典中,这又牵扯到一次查询操作。
❹ sorted 函数的 key= 参数没有调用 str.uppper,而是把这个方法的引用传递给 sorted 函数,这样在排序的时候,单词会被规范成统一格式。
通过 dict.setdefault 可以只用一行解决。
"""创建从一个单词到其出现情况的映射""" import sys import re WORD_RE = re.compile(r'\w+') index = {} with open(sys.argv[1], 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) index.setdefault(word, []).append(location) ➊ # 以字母顺序打印出结果 for word in sorted(index, key=str.upper): print(word, index[word])
➊ 获取单词的出现情况列表,如果单词不存在,把单词和一个空列表
放进映射,然后返回这个空列表,这样就能在不进行第二次查找的情况
下更新列表了
也就是说,这样写:
my_dict.setdefault(key, []).append(new_value)
跟这样写:
if key not in my_dict: my_dict[key] = [] my_dict[key].append(new_value)
二者的效果是一样的,只不过后者至少要进行两次键查询——如果键不存在的话,就是三次,用 setdefault 只需要一次就可以完成整个操作。
在用户创建 defaultdict 对象的时候,就需要给它配置一个为找不到的键创造默认值的方法。
具体而言,在实例化一个 defaultdict 的时候,需要给构造方法提供一个可调用对象,这个可调用对象会在 __getitem__ 碰到找不到的键的时候被调用,让 __getitem__ 返回某种默认值。
比如,我们新建了这样一个字典:dd = defaultdict(list),如果键'new-key' 在 dd 中还不存在的话,表达式 dd['new-key'] 会按照以下的步骤来行事。
(1) 调用 list() 来建立一个新列表。
(2) 把这个新列表作为值,'new-key' 作为它的键,放到 dd 中。
(3) 返回这个列表的引用。
而这个用来生成默认值的可调用对象存放在名为 default_factory 的
实例属性里。
利用 defaultdict 实例而不是setdefault 方法
"""创建一个从单词到其出现情况的映射""" import sys import re import collections WORD_RE = re.compile(r'\w+') index = collections.defaultdict(list) ➊ with open(sys.argv[1], 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) index[word].append(location) ➋ # 以字母顺序打印出结果 for word in sorted(index, key=str.upper): print(word, index[word])
➊ 把 list 构造方法作为 default_factory 来创建一个
defaultdict。
➋ 如果 index 并没有 word 的记录,那么 default_factory 会被调用,为查询不到的键创造一个值。这个值在这里是一个空的列表,然后这个空列表被赋值给 index[word],继而被当作返回值返回,因此
.append(location) 操作总能成功。
如果在创建 defaultdict 的时候没有指定 default_factory,查询不存在的键会触发 KeyError。
defaultdict 里的 default_factory 只会在__getitem__ 里被调用,在其他的方法里完全不会发挥作用。比如,dd 是个 defaultdict,k 是个找不到的键, dd[k] 这个表达式会调用 default_factory 创造某个默认值,而 dd.get(k) 则会返回 None。
所有这一切背后的功臣其实是特殊方法 __missing__。它会在defaultdict 遇到找不到的键的时候调用 default_factory,而实际上这个特性是所有映射类型都可以选择去支持的。
所有的映射类型在处理找不到的键的时候,都会牵扯到 __missing__方法。这也是这个方法称作“missing”的原因。虽然基类 dict 并没有定义这个方法,但是 dict 是知道有这么个东西存在的。也就是说,如果
有一个类继承了 dict,然后这个继承类提供了 __missing__ 方法,那么在 __getitem__ 碰到找不到的键的时候,Python 就会自动调用它,而不是抛出一个 KeyError 异常。
_missing__ 方法只会被 __getitem__ 调用(比如在表达式 d[k] 中)。提供 __missing__ 方法对 get 或者__contains__(in 运算符会用到这个方法)这些方法的使用没有影响。这也是我在上一节最后的警告中提到,defaultdict 中的default_factory 只对 __getitem__ 有作用的原因。
Tests for item retrieval using `d[key]` notation:: >>> d = StrKeyDict0([('2', 'two'), ('4', 'four')]) >>> d['2'] 'two' >>> d[4] 'four' >>> d[1] Traceback (most recent call last): ... KeyError: '1' Tests for item retrieval using `d.get(key)` notation:: >>> d.get('2') 'two' >>> d.get(4) 'four' >>> d.get(1, 'N/A') 'N/A' Tests for the `in` operator:: >>> 2 in d True >>> 1 in d False
StrKeyDict0 在查询的时候把非字符串的键转换为字符串
class StrKeyDict0(dict): ➊ def __missing__(self, key): if isinstance(key, str): ➋ raise KeyError(key) return self[str(key)] ➌ def get(self, key, default=None): try: return self[key] ➍ except KeyError: return default ➎ def __contains__(self, key): return key in self.keys() or str(key) in self.keys() ➏
❶ StrKeyDict0 继承了 dict。
❷ 如果找不到的键本身就是字符串,那就抛出 KeyError 异常。
❸ 如果找不到的键不是字符串,那么把它转换成字符串再进行查找。
❹ get 方法把查找工作用 self[key] 的形式委托给 __getitem__,这样在宣布查找失败之前,还能通过 __missing__ 再给某个键一个机会。
❺ 如果抛出 KeyError,那么说明 __missing__ 也失败了,于是返回default。
❻ 先按照传入键的原本的值来查找(我们的映射类型中可能含有非字符串的键),如果没找到,再用 str() 方法把键转换成字符串再查找一次。
如果没有这个测试,只要 str(k) 返回的是一个存在的键,那么__missing__ 方法是没问题的,不管是字符串键还是非字符串键,它都能正常运行。但是如果 str(k) 不是一个存在的键,代码就会陷入无
限递归。这是因为 __missing__ 的最后一行中的 self[str(key)] 会调用 __getitem__,而这个 str(key) 又不存在,于是 __missing__又会被调用。
为了保持一致性,__contains__ 方法在这里也是必需的。这是因为 kin d 这个操作会调用它,但是我们从 dict 继承到的 __contains__方法不会在找不到键的时候调用 __missing__ 方法。__contains__
里还有个细节,就是我们这里没有用更具 Python 风格的方式——k in my_dict——来检查键是否存在,因为那也会导致 __contains__ 被递归调用。为了避免这一情况,这里采取了更显式的方法,直接在这个
self.keys() 里查询。
像 k in my_dict.keys() 这种操作在 Python 3 中是很快的,而且即便映射类型对象很庞大也没关系。这是因为dict.keys() 的返回值是一个“视图”。视图就像一个集合,而且跟字典类似的是,在视图里查找一个元素的速度很快。
标准库里所有的映射类型都是可变的,但有时候你会有这样的需求,比如不能让用户错误地修改某个映射。
从 Python 3.3 开始,types 模块中引入了一个封装类名叫MappingProxyType。如果给这个类一个映射,它会返回一个只读的映射视图。虽然是个只读视图,但是它是动态的。这意味着如果对原映射
做出了改动,我们通过这个视图可以观察到,但是无法通过这个视图对原映射做出修改。
用 MappingProxyType 来获取字典的只读实例mappingproxy
>>> from types import MappingProxyType >>> d = {1:'A'} >>> d_proxy = MappingProxyType(d) >>> d_proxy mappingproxy({1: 'A'}) >>> d_proxy[1] ➊ 'A' >>> d_proxy[2] = 'x' ➋ Traceback (most recent call last): File "", line 1, in TypeError: 'mappingproxy' object does not support item assignment >>> d[2] = 'B' >>> d_proxy ➌ mappingproxy({1: 'A', 2: 'B'}) >>> d_proxy[2] 'B' >>>
➊ d 中的内容可以通过 d_proxy 看到。
➋ 但是通过 d_proxy 并不能做任何修改。
➌ d_proxy 是动态的,也就是说对 d 所做的任何改动都会反馈到它上面。
“集”这个概念在 Python 中算是比较年轻的,同时它的使用率也比较低。set 和它的不可变的姊妹类型 frozenset 直到 Python 2.3 才首次以模块的形式出现,然后在 Python 2.6 中它们升级成为内置类型。
集合的本质是许多唯一对象的聚集。因此,集合可以用于去重:
>>> l = ['spam', 'spam', 'eggs', 'spam'] >>> set(l) {'eggs', 'spam'} >>> list(set(l)) ['eggs', 'spam']
集合中的元素必须是可散列的,set 类型本身是不可散列的,但是frozenset 可以。因此可以创建一个包含不同 frozenset 的 set。除了保证唯一性,集合还实现了很多基础的中缀运算符。给定两个集合
a 和 b,a | b 返回的是它们的合集,a & b 得到的是交集,而 a - b得到的是差集。合理地利用这些操作,不仅能够让代码的行数变少,还能减少 Python 程序的运行时间。这样做同时也是为了让代码更易读,从
而更容易判断程序的正确性,因为利用这些运算符可以省去不必要的循环和逻辑操作。
例如,我们有一个电子邮件地址的集合(haystack),还要维护一个
较小的电子邮件地址集合(needles),然后求出 needles 中有多少地
址同时也出现在了 heystack 里。借助集合操作,我们只需要一行代码
就可以了
needles 的元素在 haystack 里出现的次数,两个变量都是 set 类型
found = len(needles & haystack)
如果不使用交集操作的话,代码可能就变成了
found = 0 for n in needles: if n in haystack: found += 1
使用集合的内置方法会比用循环速度快
不要忘了,如果要创建一个空集,你必须用不带任何参数的构造方法 set()。如果只是写成 {} 的形式,跟以前一样,你创建的其实是个空字典。
>>> s = {1} >>> type(s) <class 'set'> >>> s {1} >>> s.pop() 1 >>> s set()
列出了可变和不可变集合所拥有的方法的概况,其中不少是运算符重载的特殊方法。包含了数学里集合的各种操作在 Python 中所对应的运算符和方法。
集合的数学运算
想要理解 Python 里字典和集合类型的长处和弱点,它们背后的散列表是绕不开的一环。
一个关于效率的实验
为了对比容器的大小对 dict、set 或 list 的 in 运算符效率的影响,我创建了一个有 1000 万个双精度浮点数的数组,名叫 haystack。另外还有一个包含了 1000 个浮点数的 needles 数组,其中 500 个数字是从
haystack 里挑出来的,另外 500 个肯定不在 haystack 里。作为 dict 测试的基准,我用 dict.fromkeys() 来建立了一个含有1000 个浮点数的名叫 haystack 的字典,并用 timeit 模块测试示例 3-14(与示例 3-11 相同)里这段代码运行所需要的时间。
在 haystack 里查找 needles 的元素,并计算找到的元素的个数
found = 0 for n in needles: if n in haystack: found += 1
也就是说,在从 1000 个字典键里搜索 1000 个浮点数所需的时间是 0.000202 秒,把同样的搜索在含有 10 000 000 个元素的字典里进行一遍,只需要 0.000337 秒。换句话说,在一个有 1000 万个键的
字典里查找 1000 个数,花在每个数上的时间不过是 0.337 微秒——没错,相当于平均每个数差不多三分之一微秒。作为对比,我把 haystack 换成了 set 和 list 类型,重复了同样的增长大小的实验。对于 set,除了上面的那个循环的运行时间,我还测量了示例 3-15 那行代码,这段代码也计算了 needles 中出现在
haystack 中的元素的个数。
利用交集来计算 needles 中出现在 haystack 中的元素的个数
found = len(needles & haystack)
列出了所有测试的结果。
散列表其实是一个稀疏数组(总是有空白元素的数组称为稀疏数组)。在一般的数据结构教材中,散列表里的单元通常叫作表元(bucket)。在 dict 的散列表当中,每个键值对都占用一个表元,每个表元都有两个部分,一个是对键的引用,另一个是对值的引用。因为所有表元的大小一致,所以可以通过偏移量来读取某个表元。
因为 Python 会设法保证大概还有三分之一的表元是空的,所以在快要达
到这个阈值的时候,原有的散列表会被复制到一个更大的空间里面。
如果要把一个对象放入散列表,那么首先要计算这个元素键的散列值。Python 中可以用 hash() 方法来做这件事情,接下来会介绍这一点。
散列值和相等性
内置的 hash() 方法可以用于所有的内置类型对象。如果是自定义对象调用 hash() 的话,实际上运行的是自定义的 __hash__。如果两个对象在比较的时候是相等的,那它们的散列值必须相等,否
则散列表就不能正常运行了。例如,如果 1 == 1.0 为真,那么hash(1) == hash(1.0) 也必须为真,但其实这两个数字(整型和浮点)的内部结构是完全不一样的.
为了让散列值能够胜任散列表索引这一角色,它们必须在索引空间中尽量分散开来。这意味着在最理想的状况下,越是相似但不相等的对象,它们散列值的差别应该越大。示例 3-16 是一段代码输
出,这段代码被用来比较散列值的二进制表达的不同。注意其中 1和 1.0 的散列值是相同的,而 1.0001、1.0002 和 1.0003 的散列值则非常不同。
从 Python 3.3 开始,str、bytes 和 datetime 对象的散列值计算过程中多了随机的“加盐”这一步。所加盐值是 Python进程内的一个常量,但是每次启动 Python 解释器都会生成一个不同的盐值。随机盐值的加入是为了防止 DOS 攻击而采取的一种安全措施。
散列表算法
为了获取 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 不匹配的话,这种情况称为散列
冲突。发生这种情况是因为,散列表所做的其实是把随机的元素映
射到只有几位的数字上,而散列表本身的索引又只依赖于这个数字
的一部分。为了解决散列冲突,算法会在散列值中另外再取几位,
然后用特殊的方法处理一下,把新得到的数字再当作索引来寻找表
元。 若这次找到的表元是空的,则同样抛出 KeyError;若非
空,或者键匹配,则返回这个值;或者又发现了散列冲突,则重复
以上的步骤。下图展示了这个算法的示意图。
添加新元素和更新现有键值的操作几乎跟上面一样。只不过对于前
者,在发现空表元的时候会放入一个新元素;对于后者,在找到相
对应的表元后,原表里的值对象会被替换成新值。
另外在插入新值时,Python 可能会按照散列表的拥挤程度来决定是
否要重新分配内存为它扩容。如果增加了散列表的大小,那散列值
所占的位数和用作索引的位数都会随之增加,这样做的目的是为了
减少发生散列冲突的概率。
表面上看,这个算法似乎很费事,而实际上就算 dict 里有数百万
个元素,多数的搜索过程中并不会有冲突发生,平均下来每次搜索
可能会有一到两次冲突。在正常情况下,就算是最不走运的键所遇
到的冲突的次数用一只手也能数过来。
了解 dict 的工作原理能让我们知道它的所长和所短,以及从它衍
生而来的数据类型的优缺点。下面就来看看 dict 这些特点背后的
原因。
使用散列表给 dict 带来的优势和限制都有哪些。
键必须是可散列的
(1) 支持 hash() 函数,并且通过 __hash__() 方法所得到的散列值是不变的。
(2) 支持通过 __eq__() 方法来检测相等性。
(3) 若 a == b 为真,则 hash(a) == hash(b) 也为真。所有由用户自定义的对象默认都是可散列的,因为它们的散列值由id() 来获取,而且它们都是不相等的。
字典在内存上的开销巨大
由于字典使用了散列表,而散列表又必须是稀疏的,这导致它在空
间上的效率低下。举例而言,如果你需要存放数量巨大的记录,那
么放在由元组或是具名元组构成的列表中会是比较好的选择;最好
不要根据 JSON 的风格,用由字典组成的列表来存放这些记录。用
元组取代字典就能节省空间的原因有两个:其一是避免了散列表所
耗费的空间,其二是无需把记录中字段的名字在每个元素里都存一
遍。
在用户自定义的类型中,__slots__ 属性可以改变实例属性的存储
方式,由 dict 变成 tuple。
记住我们现在讨论的是空间优化。如果你手头有几百万个对象,而
你的机器有几个 GB 的内存,那么空间的优化工作可以等到真正需
要的时候再开始计划,因为优化往往是可维护性的对立面。
键查询很快
dict 的实现是典型的空间换时间:字典类型有着巨大的内存开
销,但它们提供了无视数据量大小的快速访问——只要字典能被装
在内存里。正如表 3-5 所示,如果把字典的大小从 1000 个元素增
加到 10 000 000 个,查询时间也不过是原来的 2.8 倍,从 0.000163
秒增加到了 0.00456 秒。这意味着在一个有 1000 万个元素的字典
里,每秒能进行 200 万个键查询。
键的次序取决于添加顺序
当往 dict 里添加新键而又发生散列冲突的时候,新键可能会被安
排存放到另一个位置。于是下面这种情况就会发生:由
dict([key1, value1), (key2, value2)] 和 dict([key2,
value2], [key1, value1]) 得到的两个字典,在进行比较的时
候,它们是相等的;但是如果在 key1 和 key2 被添加到字典里的
过程中有冲突发生的话,这两个键出现在字典里的顺序是不一样
的。
# 世界人口数量前10位国家的电话区号 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 ➍
➊ 创建 d1 的时候,数据元组的顺序是按照国家的人口排名来决定的。
➋ 创建 d2 的时候,数据元组的顺序是按照国家的电话区号来决定的。
➌ 创建 d3 的时候,数据元组的顺序是按照国家名字的英文拼写来决定的。
➍ 这些字典是相等的,因为它们所包含的数据是一样的。
往字典里添加新键可能会改变已有键的顺序
无论何时往字典里添加新的键,Python 解释器都可能做出为字典扩
容的决定。扩容导致的结果就是要新建一个更大的散列表,并把字
典里已有的元素添加到新表里。这个过程中可能会发生新的散列冲
突,导致新散列表中键的次序变化。要注意的是,上面提到的这些
变化是否会发生以及如何发生,都依赖于字典背后的具体实现,因
此你不能很自信地说自己知道背后发生了什么。如果你在迭代一个
字典的所有键的过程中同时对字典进行修改,那么这个循环很有可
能会跳过一些键——甚至是跳过那些字典中已经有的键。
由此可知,不要对字典同时进行迭代和修改。如果想扫描并修改一
个字典,最好分成两步来进行:首先对字典迭代,以得出需要添加
的内容,把这些内容放在一个新字典里;迭代结束之后再对原有字
典进行更新。
set 和 frozenset 的实现也依赖散列表,但在它们的散列表里存放的
只有元素的引用(就像在字典里只存放键而没有相应的值)。在 set 加
入到 Python 之前,我们都是把字典加上无意义的值当作集合来用的。
在 节中所提到的字典和散列表的几个特点,对集合来说几乎都是
适用的。为了避免太多重复的内容,这些特点总结如下。