Python中的字典和集合以及它们背后的散列表

字典(dict)这个数据结构在Python里无处不在,不但在各种程序里广泛使用,它也是 Python 语言的基石。模块的命名空间、实例的属性和函数的关键字参数中都可以看到字典的身影。正是因为字典至关重要,Python 对它的实现做了高度优化,而散列表则是字典类型性能出众的根本原因。集合(set)的实现也同样依赖于散列表


字典

标准库里的所有映射类型都是利用 dict 来实现的,因此它们有个共同的限制,即只有可散列的数据类型才能用作这些映射里的键(只有键有这个要求,值并不需要是可散列的数据类型)。

什么是可散列的数据类型:
如果一个对象是可散列的,那么在这个对象的生命周期中,它的散列值是不变的,而且这个对象需要实现 __hash__() 方 法。另外可散列对象还要有 __qe__() 方法,这样才能跟其他键做比较。如果两个可散列对象是相等的,那么它们的散列值一定是一样的。

Python中可散列的数据类型:
原子不可变数据类型(str、bytes 和数值类型)都是可散列类型,frozenset 也是可散列的,因为根据其定义,frozenset 里只能容纳可散列类型。元组的话,只有当一个元组包含的所有元素都是可散列类型的情况下,它才是可散列的。

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> tf = (1, 2, frozenset([30, 40]))
>>> hash(tf)
-4118419923444501110

“Python里所有的不可变类型都是可散列的”。这个说法其实是不准确的,比如虽然元组本身是不可变序列,它里面的元素可能是其他可变类型的引用。(恍然大悟,原来自己错了好几年。。)

创建字典的不同方式:

>>> 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

字典推导(dict comprehension)也可以用来建造新 dict:

>>> DIAL_CODES = [
... (86, 'China'),
... (91, 'India'),
... (1, 'United States'),
... (62, 'Indonesia'),
... (55, 'Brazil'),
... (92, 'Pakistan'),
... (880, 'Bangladesh'),
... (234, 'Nigeria'),
... (7, 'Russia'),
... (81, 'Japan'),
... ]
>>> country_code = {country: code for code, country in DIAL_CODES}
>>> country_code
{'Pakistan': 92, 'Bangladesh': 880, 'Japan': 81, 'China': 86, 'United States': 1, 'Indonesia': 62, 'Nigeria': 234, 'Brazil': 55, 'India': 91, 'Russia': 7}
>>> {code: country.upper() for country, code in country_code.items() if code < 66}
{1: 'UNITED STATES', 7: 'RUSSIA', 62: 'INDONESIA', 55: 'BRAZIL'}

用setdefault处理找不到的键,示例见这篇博客

像 k in my_dict.keys() 这种操作在 Python 3 中是很快的,而且即便映射类型对象很庞大也没关系。这是因为 dict.keys() 的返回值是一个“视图”。视图就像一个集合,而且跟字典类似的是,在视图里查找一个元素的速度很快。Python 2 的 dict.keys() 返回的是个列表,因此虽然上面的方法仍然是正确的,它在处理体积大的对象的时候效率不会太高,因为k in my_list 操作需要扫描整个列表

从 dict 或者其他内置类继承不好。
colllections.UserDict 这个类其实就是把标准 dict 用纯 Python 又实现了一遍。UserDict 是让用户继承写子类的。UserDict 并不是 dict 的子类,但是 UserDict 有一个叫作 data 的属性,是 dict 的实例,这个属性实际上是 UserDict 最终存储数据的地方。
示例:

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

不可变映射类型:

从 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[2] = 'x'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment
>>> d[2] = 'B'
>>> d_proxy
mappingproxy({1: 'A', 2: 'B'})
>>> d_proxy[2]
'B'

集合

集合中的元素必须是可散列的,set 类型本身是不可散列的,但是 frozenset 可以。

除了保证唯一性,集合还实现了很多基础的中缀运算符。给定两个集合 a 和 b,a | b 返回的是它们的合集,a & b 得到的是交集,而 a - b 得到的是差集。合理地利用这些操作,不仅能够让代码的行数变少,还能减少 Python 程序的运行时间。这样做同时也是为了让代码更易读,从而更容易判断程序的正确性,因为利用这些运算符可以省去不必要的循环和逻辑操作。

如果要创建一个空集,你必须用不带任何参数的构造方 法 set()。如果只是写成 {} 的形式,跟以前一样,你创建的其实是个空字典。

像 {1, 2, 3} 这种字面量句法相比于构造方法(set([1, 2, 3]))要更快且更易读。后者的速度要慢一些,因为 Python 必须先从 set 这个名字来查询构造方法,然后新建一个列表,最后再把这个列表传入到构造方法里。但是如果是像 {1, 2, 3} 这样的字面量,Python 会利用一 个专门的叫作 BUILD_SET 的字节码来创建集合。

用 dis.dis(反汇编函数)来看看两个方法的字节码的不同:

>>> from dis import dis
>>> dis('{1}')
>>> dis('set([1])')

集合推导:

>>> from unicodedata import name
>>> {chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i),'')}
{'¢', '®', '÷', '$', '§', '±', '©', '×', '%', '¬', '#', '°', '<', '¥', 'µ', '¶',}

unicodedata 模块里导入 name 函数,用以获取字符的名字。
把编码在 32~255 之间的字符的名字里有“SIGN”单词的挑出来,放到一个集合里。

中缀运算符需要两侧的被操作对象都是集合类型,但是其他的所有方法则只要求所传入的参数是可迭代对象。例如,想求 4 个聚合类型 a、b、c 和 d 的合集,可以用 a.union(b, c, d),这里 a 必须是个 set,但是 b、c 和 d 则可以是任何类型的可迭代对象。

散列表

所有的 Python 程序员都从经验中得出结论,认为字典和集合的速度是非常快的。实际上是非常非常快的。dict和set的查找速度是极快的,归功于背后的散列表。

由于列表的背后没有散列表来支持 in 运算符,每次搜索都需要扫描一次完整的列表,导致所需的时间跟据大小呈线性增长。

散列表其实是一个稀疏数组(总是有空白元素的数组称为稀疏数组)。在一般的数据结构教材中,散列表里的单元通常叫作表元(bucket)。在 dict 的散列表当中,每个键值对都占用一个表元,每个表元都有两个部分,一个是对键的引用,另一个是对值的引用。因为所有表元的大小一致,所以可以通过偏移量来读取某个表元。

因为 Python 会设法保证大概还有三分之一的表元是空的,所以在快要达到这个阈值的时候,原有的散列表会被复制到一个更大的空间里面。

两个对象在比较的时候是相等的,那它们的散列值必须相等。

由于字典使用了散列表,而散列表又必须是稀疏的,这导致它在空间上的效率低下。举例而言,如果你需要存放数量巨大的记录,那么放在由元组或是具名元组构成的列表中会是比较好的选择;最好不要根据 JSON 的风格,用由字典组成的列表来存放这些记录。用元组取代字典就能节省空间的原因有两个:其一是避免了散列表所耗费的空间,其二是无需把记录中字段的名字在每个元素里都存一遍。记住我们现在讨论的是空间优化。如果你手头有几百万个对象,而你的机器有几个 GB 的内存,那么空间的优化工作可以等到真正需要的时候再开始计划,因为优化往往是可维护性的对立面。

dict 的实现是典型的空间换时间:字典类型有着巨大的内存开销,但它们提供了无视数据量大小的快速访问——只要字典能被装 在内存里。

无论何时往字典里添加新的键,Python 解释器都可能做出为字典扩容的决定。扩容导致的结果就是要新建一个更大的散列表,并把字典里已有的元素添加到新表里。这个过程中可能会发生新的散列冲突,导致新散列表中键的次序变化。如果你在迭代一个字典的所有键的过程中同时对字典进行修改,那么这个循环很有可能会跳过一些键——甚至是跳过那些字典中已经有的键。

由此可知,不要对字典同时进行迭代和修改。如果想扫描并修改一个字典,最好分成两步来进行:首先对字典迭代,以得出需要添加的内容,把这些内容放在一个新字典里;迭代结束之后再对原有字典进行更新。

在 Python 3 中,.keys()、.items() 和 .values() 方法返回的都是字典视图。也就是说,这些方法返回的值更像集合,而不是像 Python 2 那样返回列表。视图还有动态的特性,它们可以实时反馈字典的变化。

set 和 frozenset 的实现也依赖散列表,但在它们的散列表里存放的只有元素的引用(就像在字典里只存放键而没有相应的值)。在 set 加 入到 Python 之前,我们都是把字典加上无意义的值当作集合来用的。

字典和散列表的几个特点,对集合来说几乎都是适用的:

  • 集合里的元素必须是可散列的。
  • 集合很消耗内存。
  • 可以很高效地判断元素是否存在于某个集合。
  • 元素的次序取决于被添加到集合里的次序。
  • 往集合里添加元素,可能会改变集合里已有元素的次序。

总结

大多数映射类型都提供了两个很强大的方法:setdefault 和 update。setdefault 方法可以用来更新字典里存放的可变值(比如列 表),从而避免了重复的键搜索update 方法则让批量更新成为可能,它可以用来插入新值或者更新已有键值对,它的参数可以是包含 (key, value) 这种键值对的可迭代对象,或者关键字参数。映射类型的构造方法也会利用 update 方法来让用户可以使用别的映射对象、可迭代对象或者关键字参数来创建新对象。

dict 和 set 背后的散列表效率很高,对它的了解越深入,就越能理解为什么被保存的元素会呈现出不同的顺序,以及已有的元素顺序会发生变化的原因。同时,速度是以牺牲空间为代价而换来的。

Python 的特点是“简单而正确”。dict 类型正是这一特点的完美体现——对它的优化只为一个目标:更好地实现对随机键的读取。而优化的结果非常好,由于速度快而且够健壮,它大量地应用于 Python 的解释器当中。如果对排序有要求,那么还可以选择OrderedDict。然而对于映射类型来说,保持元素的顺序并不是一个常用需求,因此会把它排除在核心功能之外,而以标准库的形式提供其他衍生的类型。

由于拥有紧凑的列表和字典表达,JSON 格式可以完美地用于数据交换。

PHP 和 Ruby 的散列语法借鉴了 Perl,它们都用 => 作为键和值的连接。JavaScript 则从 Python 那儿偷师,使用了 :。而 JSON 又从 JavaScript 发展而来,它的语法正好是 Python 句法的子集。因此,除了在 true、false 和 null 这几个值的拼写上有出入之外, JSON 和 Python 是完全兼容的。于是,现在大家用来交换数据的格式全是 Python 的 dict 和 list。

整理自《流畅的Python》第3章内容。