深度探索 Python：让我们审查 dict 模块

Question

Dictobject.c 是 Python 的 dict 对象背后的模块。它非常常用，但有一些鲜为人知的秘密，这些秘密对于了解最佳性能非常有用。

介绍 Python 中的深度探索系列

本文是旨在深入 Python 解释器系列的第一篇。Python 是一门成熟的语言，它的 提交 可以追溯到 1990 年八月份。一路走来，开发者们已经为贡献发展了一系列的 流程 ，从而允许他们对几个错误/问题相对快速地处理推进。

在这个系列中，我们将会看看 Python 各种各样的模块和功能块。我们将会看到设计选择，它们的影响及其演变。我们还会看到语言本身的设计，了解解释器一路解析语言到主要的 eval 循环。最后，我们将尝试提供由对该语言的进一步的理解所得到的实际小贴士。

Python 的 cpython 实现 (这是大多数机器上的标准) 已经从它的出生地 Mercurial 移植到了 GitHub 上。我想，它也在 SVN 下待过一段时间，但工程师们设法保存（大部分）的提交日志。

如果你之前从未见过，git 提供了一个非常赞的特性，可以查看单一文件的提交历史。这篇文章部分来源于下面这条命令：

我检查了 Objects/dictobject.c 大致十年的提交历史，带来历史考量的有趣花絮，以及 dict 算法现代实现的概述。(如果你发现任何不准确的地方或者勘误，请给我留言。) （Ele 注：翻译过程中有任何不准确或错误，也欢迎提 issue，O(∩_∩)O~）

dict 接口和 mapping

dict 接口多年来不断变化。实际上有一段很长的时间"for k in d"是不存在的！看看下面这个易得的时间表。

.values(), .keys(), .items()	May 19, 1993
.clear()	March 21, 1997
.copy()	May 28, 1997
.merge(), .update()	June 2, 1997
.pop()	October 6, 1997
.first()	November 30, 2000
.popitem()	December 12, 2000
for k in d	April 20, 2001
key in d, key not in d	April 20, 2001
.iterkeys(), .iteritems(), .itervalues()	May 1, 2001
d1 != d2, d1 == d2	May 8, 2001
dict(['foo', 'bar'])	October 26, 2001

dict 是 mapping 类型 的泛化。mapping 类型已经和我们永别了，但根据官方文档，dict 仍然是 Python 中它们唯一的实例。实际上，你可以找到 冲突文档 ，不过，我倾向于同意这种说法。如果 mapping 被定义为映射不可变的键到值的对象，那么 collections.OrderedDict 和 collections.defaultdict 也符合条件。

早期，有一个 mappingobject.c 文件，实际上已经重命名为 dictobject.c。

无论如何，很高兴知道这些 —— 但让我们看看关于这个模块的设计决定，以了解具体细节。

B 树，散列和冲突

Python 字典的实现中有大量的语义。在接下来的小节中，我们将讨论到字典基本方法的设计选择和实现细节。我们将几乎了解到字典现今所知的完整实现。我为将来的文章留下了一些东西没提（例如，分割字典盒指定类型的实现）。

B 树与散列

Python 使用哈希表来获得随机访问键的 O(1) 查找。mapping 对象的另一个最常见的选择是二叉树查找。Python 选择哈希表而不是 B 树是非常明智的。

Python 的字典作为可调整大小的哈希表实现。与 B 树相比，在大多数的情况下，对于查找（迄今为止最常见的操作）会获得更好的性能，并且实现更简单。--python.org

事实上，你可以非常清楚的看到性能差异：

@amon 在 stackexchange.com 上 / 通过 programmers.stackexchange.com

当键冲突时

冲突的思想是可以创建或打破哈希表实现的一个概念。为你的使用情况妥善处理这些可以让你的方法非常的快。处理不当，则会让操作非常慢。

Python 的哈希处理冲突的方法有问题历史，实现一次，然后用于 Python 2.7 之前的所有版本。检查这些变化集是了解关于解决冲突的不同设计抉择的缺点的一种显著方法。要了解 Python 处理哈希表的方法，知道一点术语是很重要的：

1. 哈希(hash)： 通过哈希算法映射到键的一个数值。也就是说，f(key) -> hash
2. 槽(slot)： 一个字典键值可保存的哈希表中的一个空位置
3. 哑键(dummy key)： 当删除字典的一个键值时，不留下一个空的槽。这将使得不可能找到其他的键（稍后详述）。我们留下一个哑键来代替。
4. NULL 键(NULL key)： 在表中的一个槽被键值对使用/占据之前，一个键所拥有的值
5. 项(entry)： 占据一个槽的哈希值和键值对

mapping 对象是 mapping 项的 容器 )。它维护了到ma_fill (非 NULL 键 —— 例如，哑键+项 —— 的数目); ma_used (非 NULL 键，非哑键的数目); 和ma_size（一个表示基础表的大小（分配的内存）的素数）的引用。

Python 查找算法的核心是一个名为"lookmapping"的方法。Guido 在他的提交中这样描述它：

T 所有操作都使用的基础查找函数。这实质上是来自 Knuth Vol. 3, Sec. 6.4 的算法 D。开放寻址优于链接，因为链接的链路开销将是巨大的。

现在我们有了构造块，让我们来了解下 开放寻址 和 链接 之间的差别。我会在下面解释，但是鼓励你看看上面链接的维基百科页面。如果你有兴趣，那么 Knuth 的书也可以在 Amazon 上找到。

开放寻址

在开放寻址中，分配整个地址空间。这包括可以直接插入到空间中的所有项的空间，以及那些通过冲突序列找到它们的槽的项的空间。

在下图中，你将看到一个线性探针的例子。键'a'哈希到 12416037344。以表大小(8) 为模，我们发现它落到槽 0 中。如果现在我们想要添加"i"，它也映射到槽 0，那该怎么办呢？只需简单地根据"incr"向前跳过一定数量的槽。在这个情况下，incr 设为 3。每个会与槽 0 冲突的键将会通过 n 倍的 incr 找到它的位置，其中，n 是到那个点发生冲突的数量。

我们在这里描述的场景在最好的情况下是 O(1) 次查找，最坏的情况下是 O(n) 次查找。在最坏的情况下，它相当于线性搜索空间。

链接

开放寻址与链接不同的地方在于内存的分配。冲突发生的时候，不是探索新的槽，而是将其附加到一个链表中。这在最好的情况下也是 O(1) 次查找，最坏的情况下也是 O(n) 次查找。而主要的差别是分配开销。在链接中，我们需要为每个在插入操作中发生的冲突进行额外的在堆中分配元素的操作。

聚集

在许多方面，一个哈希表实现的质量归结于它冲突解决机制的质量。如果键在表中变得过于紧密，最终我们会处在称之为“聚集”的处境中。聚集会使得对于一系列的键，比平常的冲突更多，因此，通常不可取。

勘误：如 reddit 上的用户 ggchappell 所指出的，这里的 incr 公式应该是(3 * hash + 1) % 8。

Python 开始实际的探测公式如上所示：(3 * hash + 1) % table_size。上面描述的是真实的场景，其中，我们会有一个线性聚集以及非常差的查找性能。

好啦。不过说真的。有什么问题呢？嗯，在 1997 年 1 月 16 日，Guido 写了 这个 ，确认 dict 查找背后的核心算法必须是 AFAP。

显然，在这个时候，它并不是。

在 GCC 和 clang 的现代实现中，你会发现优化了模运算。但是，曾几何时，它实际上分解成了这个公式：

…其中，一个操作中出现了三种操作。哇！为了摆脱这点，并更进一步使用更少更快的操作，Guido (在其他贡献者的帮助下) 提交了一个 新的实现了有限域的查找算法 用于随机查找。This decreased the collision rate substantially.

作为侧面说明：在 Python 中，模操作仍然比按位操作（提供类似功能）慢一点。

无论如何，有限域之后，lookmapping 方法有了一系列的小变化，这导致了 100%的速度提升。看看 这个提交 。真真杀千刀的。

对于那些在找出改了什么有困难的人，他们

• 将"if"语句序列改成了"if/else";
• 延迟计算"哈希值"直到需要；以及
• 将"哈希值"存储在寄存器中，而不是堆栈中。

在这些改动几年内在社区中有了一些时间之后，有人在 python-dev 列表中提出，当计算一个项应该放在哪个槽的时候，并不是所有的哈希值比特都实际发挥作用。

尤其是一个导致所有的项都落在相同的槽中的集合。这是由[i << 16 for i in range(20000)]定义的集合。考虑下 cpython 项目下面的提交信息：

如果表大小每次都加倍（对于上面提到的集合），那么每个单一的项都被放在槽 0.这非常糟糕。为了解决这个问题，Tim Peters 在 2001 年五月提交了 一个特性 ，它使用多项式除法来将哈希值的更多位数与每个后续的冲突进行合并。

我想团队认为这有点难以理解。不清楚为什么，但是一个月后，也就是 2001 年 6 月 1 日，多项式除法方法被一个 很简单的递归函数 取而代之。

引用 dictobject.c 中的注释：此时，冲突解决的前半部分是通过这个递归访问表索引……

j = ((5j) + 1) mod 2*i

对于 range(2 i) 中的任何初始 j，重复 i 次生成 range(2 i) 中的每个 int。

再次来自 dictobject.c：该策略的另一半是使用哈希码的其他位。这通过初始化一个（无符号) 变量"perturb"为完整的哈希码，并将递归改成下面这样来做到：

j = (5*j) + 1 + perturb;  
perturb >>= PERTURB_SHIFT;  
The next table index is just j % 2**i

此时，固化了以下规则：

• 表大小是 2**n，最小值是 8 个槽。
• 表索引是使用与表大小中比特相同数目的哈希比特数，根据哈希值计算的。
• 负载因素 (已填充槽的数目) 必须低于 2/3 表大小，否则表大小调整为 2 的下一个幂。

小贴士

好了。我们已经看了很多的实现了。从中获得一些你可以在日常中使用的实用的东西会更好。下面是从我们审查的东西中直接获得的几件事。

调整大小并不是“免费的”

默认的表大小是 8 个元素。由于加载率必须保持低于 2/3，因此在增加第 5 个元素的时候，我们的表将会调整大小。让我们看看实例化两个 4 元素字典对比一个 8 元素字典有什么区别。

你可能你期望由于创建两个独立的容器有关的开销，两个 4 元素的字典花的时间会长点。但情况并非如此。考虑以下代码：

输出显示为

…暗示因避免重新调整大小，有额外 30%的性能收益。

现在，用 Donald Knuth 的话来说，“过早的优化是一切罪恶的根源。”我当然不是主张分裂逻辑相关的字典以获得速度增益。如果你担心这样小的速度提升，那么你应该考虑使用 pypy 或者完全另一种语言。另一方面，例如，如果你进行数据库查询，那么你可能会考虑将 SELECT *替换成所需的元素（如果没有的话）。

小的键比大的好

我们看到对于那些比特位移了 16 次的整数集，有 500 倍的提升。那么 32 次呢？听上去很疯狂，不是吗？1 << 32 处在 4B 范围内。这很大，但并不是天文数字。事实上，分配用户 ID 的一些方案就用了这个范围。

考虑下面的代码：

你可能从上下文就可以猜到了，带有大键的 dict 花了需要大约 30%更长的世界来分配，这说明冲突的几率高得多。

dict 可能会浪费大量的内存

由于 dict 的大小调整计划遵循标准的指数(2**n) 过程，因此，比 2/3 略大的 dict 在调整大小的时候，会使用相当多的额外空间。

重新调整 dict 对象大小的代码。

次序有关系

可能有人告诉过你，dict 的顺序是无法保证的。这是对的！但实际上是……有点儿。cpython 中计算字典键放置元素的方法是确定的。这意味着每次传递相同的值将会获得相同的结果。

让元素乱了次序的原因实际上是 dict 的历史。考虑以下。

在这个例子中，我们有两个键：1111 和 111。由于我们的表大小是 8 (新的 dict 的默认大小)，我们知道将一个元素放进表的时候只会考虑三个位（因为对于三个位，只有 8 种可能的组合）。

知道了这一点，我们可以进行哈希了。每个键的最后三个位是 111，这意味着我们一定会有冲突。以一种次序将其添加到 dict a，以另一种次序将其添加到 dict b，保证了第一个元素获得这个 dict 中的第一个槽。当我们尝试添加下一个元素，将会有冲突，此时它将会被放在表中另一个槽（在这个例子中，恰好是第一个槽之前）。

当我们打印出这个 dict 的键时，可以看到，它们的次序乱了。虽然，这种行为是一致的，并且可重现。只要我们以相同的次序添加元素，那么对于写这篇文章的时候 Python 2.7 和 3.x 的最新版本来说，次序将保持一致。

dict 的键应该被视为不可变的

对那些没试过的人来说，当你试图使用一个可变类型作为 dict 的键时，会发生以下情况：

这里的问题源于这样的事实：默认情况下，可变类型没有 hash () 方法。对于给定的容器，对这种情况并无内在原因，但当你考虑到 hash () 是用来干嘛的，会看到理由很充分。

如果你把一个列表当成字典键，接着改变它，那么哈希值会发生改变。这意味着未来对这个元素的查找将会失败，因为传递该值用于查询将会得到一个不同的哈希值。来看个例子。

首先，必须用一个扩展 list 的类，它定义了 hash () 方法。这会做的不错。

现在，我们可以将我们的列表当成一个可变字典键了！hlist 是我们的可哈希列表。hlist2 是一个包含相同元素的单独的可哈希列表。

设置 d[hlist] = 'a'，我们可以用 hlist 或者新的列表 hlist2（包含相同次序的相同值）来查找值'a'。

这是因为，根据值，列表是相同的，并且，在 hash () 下，它们有相同的输出。现在，让我们来改变 hlist。需要明确的是：生成 a 的 d 的键是_hlist。它不是 hlist 的值_，而是 hlist 本身。

然后，通过引用修改 hlist 将会有一定的不良影响。这将会导致 hlist 的值和hash发生改变。虽然，它已经在分配给它的槽里面了，这将很可能不恰当地赋给它新的哈希值和值。

所以，正如你所想的那样，附加 4 到 hlist 引发查找错误。在 d 中，它仍然作为一个键存在，但是现在，它有了一个不同的哈希值和不同的值。

当我们通过原始变量 hlist 进行查找的时候，计算得到一个错误的哈希值，看起来 hlist 不再存在在 d 中。当我们通过原始值 hlist2 进行查找的时候，根据它的哈希值，找到正确的槽，但值并不匹配，所以看起来 hlist2 也不在 d 中。

原文： Deep Exploration Into Python: Let's Review The Dict Module