Python字典底层实现原理揭秘

文章不知道大家是否熟悉？今天我将给大家介绍《Python字典底层实现原理详解》，这篇文章主要会讲到等等知识点，如果你在看完本篇文章后，有更好的建议或者发现哪里有问题，希望大家都能积极评论指出，谢谢！希望我们能一起加油进步！

Python字典通过哈希表实现O(1)平均时间复杂度，其核心在于哈希函数、开放寻址冲突解决和动态扩容机制。

Python字典的底层实现核心在于其哈希表（Hash Table）的实现。它通过将键（Key）映射到一个存储位置来快速存取值（Value），这使得大多数操作都能保持接近常数时间复杂度，也就是我们常说的O(1)。

解决方案

Python字典的底层实现基于一个稀疏的数组（或者说一个列表），这个数组的每个元素被称为一个“桶”（bucket）或“槽位”（slot）。每个槽位可以存储一个 PyDictEntry 结构体，其中包含三部分：键的哈希值、键本身以及对应的值。

当我们要往字典里插入一个键值对时：

1. 哈希计算：Python会先计算键的哈希值。对于不可变类型（如字符串、数字、元组），这个哈希值是固定的。对于自定义对象，则需要实现 __hash__ 方法。
2. 索引映射：得到哈希值后，字典会用这个哈希值与当前内部数组的大小进行取模运算，从而得到一个初始的索引，这个索引指向了数组中的一个槽位。
3. 冲突处理：如果这个槽位是空的，键值对就会被直接存入。但如果这个槽位已经被占用（发生了哈希冲突），Python不会简单地覆盖，而是采用一种称为“开放寻址”（Open Addressing）的策略来寻找下一个可用的槽位。它会根据一个特定的探测序列（通常是一个伪随机序列，而不是简单的线性探测）去寻找下一个空的或匹配的槽位。
4. 键比较：在找到一个非空槽位时，它会先比较哈希值，如果哈希值相同，还会进一步比较键本身（使用 __eq__ 方法）以确保是同一个键。如果键相同，则更新值；如果键不同，则继续探测。

当我们要查找一个键时，过程类似：计算哈希值，得到初始索引，然后沿着探测序列查找，直到找到匹配的键或者遇到空槽位（表示键不存在）。

删除操作也类似，找到键后，它不会直接清空槽位，而是将该槽位标记为一个“虚拟”或“哑”条目（dummy entry）。这样做是为了在后续查找时，不中断探测链，确保其他哈希冲突的键仍然能被正确找到。这些虚拟条目会在字典扩容时被真正清除。

为了维持高效性能，当字典中的元素数量达到一定比例（通常是数组大小的2/3左右）时，字典会自动进行扩容（rehashing），创建一个更大的内部数组，并将所有现有元素重新计算哈希并插入到新数组中。这个过程虽然是O(N)的复杂度，但由于不频繁发生，平均到每次操作上，仍然能保持O(1)的摊销复杂度。

为什么Python字典的查找、插入和删除操作通常是O(1)的复杂度？

这背后的核心秘密在于哈希函数和哈希表的结构设计。当我们说O(1)时，我们指的是“平均情况”下的性能，而非“最坏情况”。

想象一下，你有一个巨大的图书馆，每本书都有一个唯一的编号（哈希值）。图书馆里有许多书架（槽位），每个书架都有一个地址（索引）。当你想要找一本书时，你不需要一本一本翻找，而是通过书的编号直接计算出它应该在哪个书架的哪个位置。这就是哈希表的基本思想：通过哈希函数将键直接映射到存储位置。

对于Python字典：

• 哈希函数的效率：Python内置的哈希函数（例如对整数、字符串、元组的哈希）设计得非常高效，能在常数时间内计算出键的哈希值。
• 直接寻址：一旦哈希值被计算出来，通过简单的取模运算，我们就能直接定位到哈希表中的一个“桶”或“槽位”。这就像直接走向图书馆的某个书架。
• 开放寻址的优化：即使发生哈希冲突，Python的开放寻址策略也经过精心设计，尽量减少探测次数。它不是简单的线性探测，而是使用一个更复杂的序列，这有助于避免“聚簇”现象，从而保持探测路径的短小。
• 动态扩容：字典在达到一定负载因子时会自动扩容。虽然扩容本身是O(N)操作，但它发生得不频繁，并且每次扩容都会将容量翻倍，使得在大量操作中，每次插入、查找和删除的平均成本（摊销成本）仍然是O(1)。这就好比图书馆在书架快满的时候，一次性增加大量新书架，虽然搬书很累，但之后很长一段时间内找书又会非常快。

当然，O(1)并非绝对。在极少数的“最坏情况”下，例如所有键都哈希到同一个值（这通常意味着哈希函数设计得很差，或者你故意构造了这样的键），或者哈希表在某个局部区域发生严重聚簇，那么查找、插入和删除操作可能会退化到O(N)，因为你需要遍历大量的槽位。不过，Python的哈希函数和冲突解决机制通常能很好地避免这种情况。

Python字典如何处理哈希冲突？

哈希冲突是哈希表不可避免的问题，因为不同的键可能会计算出相同的哈希值，或者不同的哈希值经过取模运算后映射到同一个槽位。Python字典在C语言层面（CPython实现）采用了一种精巧的“开放寻址”（Open Addressing）策略来解决这个问题，而不是常见的“链表法”（Separate Chaining）。

具体来说，当一个键值对要插入到哈希表时：

1. 初始探测：首先，根据键的哈希值计算出一个初始的槽位索引。
2. 探测序列：如果这个槽位已经被占用，或者里面的键与要插入的键不匹配，字典就会开始“探测”。Python的探测序列不是简单的线性探测（即依次检查下一个槽位），而是采用了一种更复杂的伪随机序列。这种序列能够有效地“跳跃”到不同的位置，以减少连续冲突带来的聚簇效应。这种探测方式确保了即使初始位置被占用，也能相对快速地找到下一个可能的空闲位置。
3. 匹配与插入：
   • 找到空槽位：如果探测过程中找到一个完全空的槽位，那么新的键值对就会被插入到这里。
   • 找到虚拟槽位：如果找到一个被标记为“虚拟”或“已删除”的槽位，新的键值对也可以插入到这里，并覆盖这个虚拟条目。
   • 找到匹配键：如果探测到的槽位中，键的哈希值和键本身都与要插入的键完全相同（通过 __eq__ 比较），那么这表示是更新操作，旧值会被新值覆盖。
   • 未找到匹配键且槽位被占用：如果探测到的槽位中，键的哈希值或键本身不匹配，且该槽位未被标记为虚拟，则继续沿着探测序列寻找下一个槽位。
4. 删除的特殊处理：当一个键值对被删除时，它所在的槽位并不会立即被清空。相反，它会被标记为一个特殊的“虚拟”状态。这样做是为了不破坏哈希冲突时形成的探测链。如果直接清空，后续依赖这个槽位作为探测路径的键可能就找不到了。这些虚拟槽位会在字典扩容或缩容时被彻底清除。

这种开放寻址策略的优势在于它避免了额外的数据结构（如链表），使得内存布局更加紧凑，缓存命中率更高。然而，它的缺点是，一旦哈希表变得非常满，冲突会变得更加频繁，探测路径会变长，性能会下降。这也是为什么Python字典需要动态扩容机制来维持其高效性能。

Python字典何时以及如何进行扩容（Rehashing）？

Python字典的扩容（或者叫重新哈希，Rehashing）是其维持高效性能的关键机制之一。它不是随机发生的，而是根据字典的“负载因子”（load factor）来判断的。

何时扩容？

字典内部维护着两个重要的计数器：

1. ma_used：实际存储的键值对数量。
2. ma_fill：已占用的槽位数量（包括实际键值对和那些被标记为“虚拟”或“已删除”的槽位）。
3. ma_mask：哈希表当前容量减1（通常容量是2的幂次，所以 ma_mask + 1 就是容量）。

当 ma_fill （已占用槽位数）达到 ma_mask 的某个阈值时，字典就会触发扩容。具体来说，CPython通常在 ma_fill * 3 <= (ma_mask + 1) * 2 （即 ma_fill <= (ma_mask + 1) * 2 / 3，也就是当填充率达到约2/3时）这个条件不再满足时进行扩容。这意味着当字典变得比较满，冲突的可能性增加时，它会选择扩容。

此外，如果字典因为大量删除操作变得非常稀疏，并且 ma_used（实际键值对数）远小于 ma_fill（已占用槽位数），Python也可能会触发缩容，以节省内存。

如何扩容？

扩容是一个相对耗时的操作，因为它涉及重新构建整个哈希表：

1. 分配新空间：Python会创建一个新的、更大的内部数组。新数组的容量通常是旧数组的两倍或四倍，并且总是2的幂次方（例如，从8扩容到16，或从16扩容到32）。选择2的幂次方是为了让哈希值到索引的映射 hash_value & ma_mask （等同于 hash_value % (ma_mask + 1)，但位运算更快）更高效。
2. 遍历并重新插入：字典会遍历旧哈希表中的所有实际存在的键值对（忽略那些虚拟的或空的槽位）。
3. 重新哈希：对于每一个旧的键值对，它会重新计算其哈希值（尽管哈希值本身不变，但因为新数组大小不同，所以需要重新计算在新数组中的索引）。
4. 插入新表：然后，它会使用新的索引和新的冲突解决策略，将这个键值对插入到新的哈希表中。这个过程与普通的插入操作相同，可能会涉及探测。
5. 释放旧空间：所有键值对都迁移到新表后，旧的哈希表空间会被释放。

扩容操作的复杂度是O(N)，其中N是字典中元素的数量。这意味着如果字典非常大，扩容会消耗显著的时间。然而，由于容量是指数级增长的，每次扩容后，字典可以在很长一段时间内不需要再次扩容。这种设计使得平均到每次插入操作的成本（摊销成本）仍然保持在O(1)，因为扩容的成本被分摊到了多次插入操作上。

以上就是《Python字典底层实现原理揭秘》的详细内容，更多关于的资料请关注golang学习网公众号！