Python学习之路22-字典和集合

本篇主要介绍dict和set的高级用法以及它们背后的哈希表。

1. 前言

dict类型不但在各种程序中广泛使用，它也是Python的基石。模块的命名空间、实例的属性和函数的关键字参数等都用到了dict。与dict先关的内置函数都在__builtins__.__dict__模块中。

由于字典至关重要，Python对其实现做了高度优化，而散列表（哈希函数，Hash）则是字典性能突出的根本原因。而且集合(set)的实现也依赖于散列表。

本片的大纲如下：

• 常见的字典方法；

• 如何处理找不到的键；

• 标准库中dict类型的变种；

• set和frozenset类型；

• 散列表工作原理；

• 散列表带来的潜在影响（什么样的数据可以作为键、不可预知的顺序等）。

2. 字典

和上一篇一样，先来看看collections.abc模块中的两个抽象基类：Mapping和MutableMapping。它们的作用是为dict和其他类似的类型定义形式接口:

然而，非抽象映射类型一般不会直接继承这些抽象基类，它们会直接对dict或者collections.UserDict进行扩展。

2.1 创建字典

首先总结下常用的创建字典的方法：

2.2 字典推导

列表推导和生成器表达式可以用在字典上。字典推导（dictcomp）可从任何以键值对作为元素的可迭代对象中构建出字典。

2.3 两个重要的映射方法update和setdefault

2.3.1 update方法

它的参数列表如下：

update方法处理参数m的方法是典型的“鸭子类型”。该方法首先检测m是否有keys方法，如果有，那么update方法就把m当做映射对象来处理（即使它并不是映射对象）；否则退一步，把m当做包含了键值对(key, value)元素的迭代器。

Python中大多数映射类的构造方法都采用了类似的逻辑，因此既可用一个映射对象来新建一个映射对象，也可以用包含(key, value)元素的可迭代对象来初始化一个映射对象。

2.3.2 setdefault处理不存在的键

当更新字典时，如果遇到原字典中不存在的键时，我们一般最开始会想到如下两种方法：

以上两种方法至少进行2次键查询，如果键不存在，第一种方法要查询3次，非常低效。但如果使用setdefault方法，则只需一次就可以完成上述操作：

2.4 映射的弹性键查询

上述的setdefault方法在每次调用时都要我们手动指定默认值，那有没有什么办法能方便一些，在键不存在时，直接返回我们指定的默认值？两个常用的方法是：①使用defaultdict类；②自定义一个dict子类，在子类中实现__missing__方法，而这个方法又有至少两种方法。

2.4.1 defaultdict类

collections.defaultdict能优雅的解决3.3.2中的问题：

在实例化defaultdict时，需要给构造方法提供一个可调用对象（实现了__call__方法的对象），这个可调用对象存储在defaultdict类的属性default_factory中，当__getitem__找不到所需的键时就会通过default_factory来调用这个可调用对象来创建默认值。

上述代码中 my_dict[key] 的内部过程如下(假设key是新键)：

1. 调用list()来创建一个新列表；

2. 把这个新列表作为值，key作为它的键，放到my_dict中；

3. 返回这个列表的引用。

注意：

• 如果在实例化defaultdict时未指定default_factory，那么在查询不存在的键时则会触发KeyError；

• defaultdict中的default_factory只会在__getitem__里被调用，在其它的方法里完全不会发挥作用！比如，dd是个defaultdict，k是个不存在的键，dd[k]这个表达式则会调用default_factory，并返回默认值，而dd.get(k)则会返回None。

特殊方法__missing__

其实上述的功能都得益于特殊方法__missing__，实际调用default_factory的就是该特殊方法，且该方法只会被__getitem__调用。即：__getitem__调用__missing__，__missing__调用default_factory。

所有的映射类型在处理找不到键的情况是，都会牵扯到该特殊方法。基类dict没有定义这个方法，但dict有该方法的声明。

下面通过编写一个继承自dict的类来说明如何使用__missing__实现字典查询，不过这里并没有在找不到键时调用一个可调用对象，而是抛出异常。

2.4.2 自定义映射类：继承自dict

某些情况下可能希望在查询字典时，映射里的键通通转换成str类，但为了方便，也允许使用非字符串作为建，比如我们希望实现如下效果：

以下便是这个类的实现：

说明：

• 第3行：这里的isinstance(key, str)测试是必需的。如果没有这个测试，那么当str(key)是个不存在的键时便会发生无限递归，因为第4行self[str(key)]会调用__getitem__，进而又调用__missing__，然后一直重复下去。

• 第13行：为了保持一致性，__contains__方法在这里也是必需的，因为k in d这个操作会调用该方法。但是从dict继承到的__contains__方法在找不到键的时候不会调用__missing__（间接调用，不会直接调用）。

• 第14行：这里并没有使用更具Python风格的写法：key in my_dict，因为这样写会使__contains__也发生递归调用，所以这里采用了更显式的方法 key in self.keys。同时需要注意的是，这里有两个判断，因为我们本没有强行限制所有的键都必须是str，所以字典中可能存在非字符串的键（key in self.keys()）。

• 像k in my_dict.keys()这种操作在Python3中很快，即使映射类型对象很庞大也很快，因为dict.keys()返回的是一个”视图“，在视图中查找一个元素的速度很快。

2.4.3 子类化UserDict

如果要自定义一个映射类型，更好的策略是继承collections.UserDict类。它是把标准dict用纯Python又实现了一遍。之所以更倾向于从UserDict而不是从dict继承，是因为后者有时会在某些方法的实现上走一些捷径，导致我们不得不在它的子类中重写这些方法，而UserDict则没有这些问题。也正是由于这个原因，如果上个例子要实现将所有的键都转换成字符串，还需要做很多工作，而从UserDict继承则能很容易实现。

注意：如果我们想在上个例子中实现__setitem__，使其将所有的键都转换成str，则会发生无限递归：

下面使用UserDict来实现一遍StrKeyDict，它实现了__setitem__方法，将所有的键都转换成str。注意这里并没有自行实现get方法，原因在后面。

因为UserDict继承自MutableMapping，所以StrKeyDict里剩下的映射类型的方法都是从UserDict、MutableMapping和Mapping继承而来，这些方法中有两个值得关注：

MutableMapping.update：

这个方法不但可以直接用，它还用在__init__里，使其能支持各种格式的参数。而这个update方法内部则使用self[key] = value来添加新值，所以它其实是在使用我们定义的__setitem__方法。

Mapping.get：

对比StrKeyDict0和StrKeyDict的代码可以发现，我们并没有为后者定义get方法。前者如果不定义get方法，则会出现如下情况：

而在StrKeyDict中则没有必要，因为UserDict继承了Mapping的get方法，而查看源代码可知，这个方法的实现和StrKeyDict0.get一模一样。

2.5 其他字典

2.5.1 collections.OrderedDict

这个类型在添加键的时候会保持原序，即对键的迭代次序就是添加时的顺序。它的popitem方法默认删除并返回字典中的最后一个元素。值得注意的是，从Python3.6开始，dict中键的顺序也保持了原序。但出于兼容性考虑，如果要保持有序，还是推荐使用OrderedDict。

2.5.2 collections.ChainMap

该类型可容纳多个不同的映射对象，然后在查找元素时，这些映射对象会被当成一个整体被逐个查找。这个功能在给有嵌套作用域的语言做解释器的时候很有用，可以用一个映射对象来代表一个作用域的上下文。

2.5.3 collections.Counter

这个类会给键准备一个整数计数器，每次更新一个键时就会自动增加这个计数器。所以这个类型可以用来给可散列对象计数，或者当成多重集来使用（相同元素可以出现不止一次的集合）。

2.5.4 不可变映射类型

标准库中所有的映射类型都是可变的，但有时候会有这样的需要，比如不能让用户错误地修改某个映射。从Python3.3开始，types模块中引入了一个封装类MappingProxyType。如果给这个类一个映射，它返回一个只读的映射视图。虽然是个只读视图，但它是动态的，如果原映射被修改，我们也能通过这个视图观察到变化。以下是它的一个例子：

3. 集合

和前面的字典一样，先来看看集合的超类的继承关系：

集合的本质是许多唯一对象的聚集。即，集合可以用于去重。集合中的元素必须是可散列的，set类型本身是不可散列的，但是frozenset可以。也就是说可以创建一个包含不同frozenset的set。

集合的操作

注意两个概念：字面量句法，构造方法：

字面量句法相对于构造方法更快更易读。后者速度之所以慢是因为Python必须先从set这个名字来查询构造方法，然后新建一个列表，最后再把这个列表传入到构造方法里。而对于字面量句法，Python会利用一个专门的叫做BUILD_SET的字节码来创建集合。

集合的字面量——{1}，{1, 2}等——看起来和它的数学形式一模一样。但要注意空集，如果要创建一个空集，只能是 temp = set()，而不是 temp = {}，后者创建的是一个空字典。

frozenset的标准字符串表示形式看起来就像构造方法调用一样：

对于frozenset，一旦创建便不可更改，常用作字典的键的集合。

除此之外，集合还实现了很多基础的中缀运算符，如交集a & b，合集a | b，差集a - b等，还有子集，真子集等操作，由于这类操作太多，这里不再一一列出。下面代码得到两个可迭代对象中共有的元素个数，这是一个常用操作：

集合推导

和列表推导，字典推导一样，集合也有推导（setcomps）：

4. dict和set的背后

有人做过实验（就在普通笔记本上），在1,000,000个元素中找1,000个元素，dict与set两者的耗时比较接近，大约为0.000337s，而使用列表list，耗时是97.948056s，list的耗时是dict和set的约29万倍。而造成这种差距的最根本的原因是，list中找元素是按位置一个一个找（虽然有像折半查找这类的算法，但本质依然是一个位置接一个位置的比较），而dict是根据某个信息直接计算元素的位置，显然后者速度要比挨个找快很多。而这个计算方法统称为哈希函数（hash），即 hash(key)–>position。

碍于篇幅，关于哈希算法的原理（哈希函数的选择，冲突的解决等）这里便不再赘述，相信经常和算法打交道或者考过研的老铁们一定不陌生。

哈希表（也叫散列表）其实是个稀疏数组（有很多空元素的数组），每个单元叫做表元（bucket），Python中每个表元由对键的引用和对值的引用两部分组成。因为所有表元的大小一致，所以当计算出位置后，可以通过偏移量来读取某个元素（变址寻址）。

Python会设法保证大概还有三分之一的表元是空的，当快要达到这个阈值的时候，原有的哈希表会被复制到一个更大的空间中。

4.1 哈希值和相等性

如果要把一个对象放入哈希表中，首先要计算这个元素的哈希值。Python中可以通过函数hash()来计算。内置的hash()可用于所有的内置对象。如果是自定义对象调用hash()，实际上运行的是自定义的__hash__。如果两个对象在比较的时候相等的，那么它们的哈希值必须相等，否则哈希表就不能正常工作。比如，如果 1 == 1.0 为真，那么hash(1) == hash(1.0)也必须为真，但其实这两个数字的内部结构完全不一样。而相等性的检测则是调用特殊方法__eq__。

_补充_：从Python3.3开始，为了防止DOS攻击，str、bytes和datetime对象的哈希值计算过程中多了随机的“加盐”步骤。所加的盐值是Python进程中的一个常量，但每次启动Python解释器都会生成一个不同的盐值。

4.2 Python中的哈希算法

为获取my_dict[search_key]背后的值（不是哈希值），Python首先会调用hash(search_key)计算哈希值，然后取这个值最低的几位数字当作偏移量（这只是一种哈希算法）去获取所要的值，如果发生了冲突，则再取哈希值的另外几位，知道不冲突为止。

在插入新值的时候，Python可能会按照哈希表的拥挤程度来决定是否要重新分配内存为它扩容。如果增加了散列表的大小，散列值所占的位数和用作索引的位数都会随之增加（目的是为了减少冲突发生的概率）。

这个算法看似费事，但实际上就算dict中有数百万个元素，多数的搜索过程中并不会发生冲突，平均下来每次搜索可能会有一到两次冲突。

4.3 dict的优劣

1、键必须是可散列的

一个可散列对象必须满足一下要求：

（1）支持hash()函数，并且通过__hash__()方法得到的哈希值是不变的；

（2）支持通过__eq__()方法来检测相等性；

（3）若 a == b为真，则 hash(a) == hash(b)也必须为真。

所有自定义的对象默认都是可散列的，因为它们的哈希值有id()函数来获取，而且它们都是不相等的。如果你实现了一个类的__eq__方法，并且希望它是可散列的，那请务必保证这个类满足上面的第3条要求。

2、字典在内存上的开销巨大

典型的用空间换时间的算法。因为哈希表是稀疏的，这导致它的空间利用率很低。

如果需要存放数量巨大的记录，那么放在由元组或命名元组构成的列表中会是比较好的选择；最好不要根据JSON的风格，用由字典组成的列表来存放这些记录。

用元组代替字典就能节省空间的原因有两个：①避免了哈希表所耗费的空间；②无需把记录中字段的名字在每个元素里都存一遍。

关于空间优化：如果你的内存够用，那么空间优化工作可以等到真正需要的时候再开始，因为优化往往是可维护性的对立面。

3、键查询很快

本节最开始的实验已经证明，字典的查询速度非常快。如果再简单计算一下，上面的实验中，在有1000万个元素的字典里，每秒能进行200万次键查询。

这里之所以说的是“键查询”，而不是“查询”，是因为有可能值的数据不在内存，内在磁盘中。一旦涉及到磁盘这样的低速设备，查询速度将大打折扣。

4、键的次序取决于添加顺序

当往dict里添加新键而又发生冲突时，新键可能会被安排存放到另一个位置。并且同一组数据，每次按不同顺序进行添加，那么即便是同一个键，同一个算法，最后的位置也可能不同。最典型的就是这组数据全冲突（所有的hash值都一样），然后采用的是线性探测再散列解决冲突，这时的顺序就是添加时的顺序。

5、向字典中添加新键可能会改变已有键的顺序。

无论何时往字典中添加新的键，Python解释器都有可能做出扩容的决定。扩容时，在将原有的元素添加到新表的过程中就有可能改变原有元素的顺序。如果在迭代一个字典的过程中同时对修改字典，那么这个循环就很有可能会跳过一些键。

_补充_：Python3中，.keys()、.items()和.values()方法返回的都是字典视图。

4.4 set的实现

set和frozenset也由哈希表实现，但它们的哈希表中存放的只有元素的引用（类似于在字典里只存放了键而没放值）。在set加入到Python之前，都是把字典加上无意义的值来当集合用。5.3中对字典的几个特点也同样适用于集合。

5. 总结

字典是Python的基石。除了基本的dict，标准库中还有特殊的映射类型：defaultdict、OrderedDict、ChainMap、Counter和UserDict，这些类都在collections模块中。

大多数映射都提供了两个强大的方法：setdefault和update。前者可避免重复搜索，后者可批量更新。

在映射类型的API中，有个很好用的特殊方法__missing__，可以通过这个方法自定义当对象找不到某个键时的行为。

set和dict的实现都用到了哈希表，两者的查找速度都很快，但空间消耗大，典型的以空间换时间的算法。