字典（Dict）的底层实现原理是什么？

字典的底层基于哈希表，通过哈希函数将键映射到数组索引实现O(1)平均时间复杂度的查找。当不同键映射到同一位置时发生哈希冲突，主要采用开放寻址法解决，如CPython 3.6+使用的混合策略，结合紧凑entries数组与稀疏索引数组提升缓存效率。为维持性能，字典在负载因子过高时触发扩容，即重建更大数组并重新哈希所有元素，虽瞬时开销大但均摊后仍为O(1)。可作为键的对象必须是可哈希的，即具备不变的__hash__()和__eq__()方法，如int、str、tuple等不可变类型，而list、dict等可变类型因哈希值不恒定不可作键。

字典（Dict）的底层实现，核心在于其作为一种哈希表（Hash Table）的数据结构。它通过将键（key）映射到内存中的特定位置来存储值（value），从而实现极快的查找、插入和删除操作。这种映射依赖于一个哈希函数，它能将任意键转换成一个固定大小的整数，即哈希值，进而用于计算存储位置。

解决方案

理解字典的底层，就像是揭开一个魔术的秘密。它最根本的原理是利用哈希函数将键“散列”到一个数组的索引上。当你把一个键值对放进字典时，字典会先计算键的哈希值，然后根据这个哈希值确定它在内部数组（我们通常称之为“桶”或“槽”）中的位置。理想情况下，不同的键会散列到不同的位置，这样查找时就能直接通过键的哈希值跳到对应的位置，直接取出值，这也就是它能达到平均O(1)时间复杂度的奥秘。

然而，现实并非总是如此理想。不同的键可能会计算出相同的哈希值，或者哈希值经过取模运算后指向了同一个数组索引，这就是所谓的哈希冲突。字典的实现必须有一套机制来优雅地处理这些冲突，否则它的性能优势就会荡然无存。常见的冲突解决策略包括开放寻址法（Open Addressing）和链表法（Chaining）。Python的字典（特指CPython 3.6+）采取了一种混合且高度优化的开放寻址策略，它在内部维护了一个紧凑的项数组和一个稀疏的索引数组，以提高缓存局部性和内存效率。

当字典中的元素越来越多，哈希冲突的概率也会随之上升，导致查找效率下降。为了维持高效性能，字典会在达到一定“负载因子”（即已用槽位与总槽位的比例）时进行扩容（Resizing/Rehashing）。扩容意味着创建一个更大的内部数组，然后将所有现有的键值对重新计算哈希值并插入到新数组中。这个过程虽然会暂时消耗较多资源，但在均摊分析下，每次操作的平均时间复杂度依然保持在O(1)。

为什么Python字典的查找速度如此之快？

字典的查询速度之所以能达到惊人的平均O(1)，其核心在于哈希函数和直接寻址的巧妙结合。想象一下，你有一个巨大的图书馆，里面的书没有按照书名首字母排序，而是每本书都有一个独一无二的“定位码”。你拿到这个码，就能直接走到对应的书架和位置，瞬间找到那本书。字典的工作方式与此类似。

当我们尝试通过一个键（Key）去查找对应的值（Value）时，Python会首先调用该键的

__hash__()

当然，“平均O(1)”的说法也暗示了存在“最坏情况”。如果哈希函数设计不佳，或者键的分布非常极端，导致大量冲突，那么查找效率可能会退化到O(N)——需要遍历所有冲突的元素。但Python的哈希函数经过精心设计和优化，加上其冲突解决策略，使得这种情况在实际应用中极为罕见。此外，现代CPU的缓存机制也对字典的性能贡献良多，特别是CPython 3.6+引入的紧凑型字典，能够更好地利用CPU缓存，进一步加速了数据访问。

字典在处理哈希冲突时有哪些策略？

哈希冲突是哈希表设计中不可避免的问题，因为键空间通常远大于存储空间。当两个不同的键经过哈希函数计算后，指向了同一个存储位置时，我们就需要一套策略来解决这个“撞车”问题。Python字典主要依赖的是开放寻址法（Open Addressing）。

在开放寻址法中，如果计算出的索引位置已经被占用，字典不会在这个位置上额外开辟空间（比如链表），而是会按照某种预设的“探测序列”去寻找下一个空闲的槽位。最简单的是线性探测，即依次检查下一个、再下一个位置，直到找到一个空位。例如，如果位置

i

i+1

i+2

i+3

这种方法的优点是内存利用率高，因为所有元素都直接存储在主数组中，没有额外的指针开销，这也有利于CPU缓存的利用。但缺点是容易出现聚集（Clustering）现象，即连续的已占用槽位会形成一个“块”，导致后续的插入和查找都需要更长的探测序列，从而降低性能。为了缓解聚集问题，还有二次探测（步长是探测次数的平方）或双重散列（使用第二个哈希函数来确定步长）等更复杂的探测策略。

虽然Python的字典在概念上使用了开放寻址，但其具体实现（尤其是在CPython 3.6及更高版本中）更为精妙。它将哈希值、键和值存储在一个紧凑的“entries”数组中，而索引数组则存储指向这些entry的指针或索引。当发生冲突时，它会通过一个精心设计的探测序列（并非简单的线性或二次）来寻找下一个可用的索引，并利用一个特殊的“dummy”值来标记已删除的槽位，以确保查找的正确性。这种设计在保证性能的同时，也显著提升了内存效率。

阿里云-虚拟数字人

阿里云-虚拟数字人是什么？ ...

2

查看详情

字典何时会进行扩容（Rehashing），这会带来什么影响？

字典的扩容（Rehashing）是一个幕后英雄，它确保了字典在不断增长的情况下，依然能够保持高效的平均O(1)操作时间。这个过程的触发点，通常是当字典中的元素数量达到一定阈值时，也就是所谓的负载因子（Load Factor）超过了预设值。负载因子是已存储的键值对数量与字典内部总槽位数量的比例。当这个比例过高，意味着哈希冲突的概率增加，查找和插入的效率就会开始下降，因为需要进行更多的探测才能找到空位或目标元素。

一旦触发扩容，字典会执行以下步骤：

1. 创建新表： 它会分配一个新的、更大的内部存储空间（通常是当前大小的2倍或4倍，以2的幂次增长）。
2. 重新哈希并插入： 字典会遍历旧表中所有的键值对，对每个键重新计算哈希值（因为新的表大小会影响哈希值取模后的索引），然后将它们插入到新的表中。

这个过程听起来很耗时，确实，在扩容发生的那一刻，它的时间复杂度是O(N)，其中N是字典中元素的数量。这意味着，如果你在一个循环中频繁地向一个字典添加元素，偶尔会遇到一次显著的性能停顿。然而，从整体来看，由于扩容操作发生的频率相对较低，并且每次扩容后都能提供更大的空间来容纳更多元素，所以从长远来看，每次插入操作的均摊时间复杂度依然是O(1)。

扩容带来的影响是多方面的：

• 性能暂时下降： 扩容瞬间会消耗CPU和内存资源，可能导致程序出现微小的卡顿。
• 内存使用增加： 在扩容过程中，新旧两张表会同时存在于内存中，直到旧表被垃圾回收，这会暂时增加内存峰值。
• 性能恢复与提升： 扩容完成后，由于有了更多的空闲槽位，哈希冲突的概率降低，字典的查找和插入性能会恢复到最佳状态，甚至比扩容前更优。

因此，虽然扩容是一个成本较高的操作，但它是维持字典高性能的关键机制。理解这一点，可以帮助我们在设计数据结构时，对字典的性能特性有更准确的预期，尤其是在处理大量数据插入的场景下。

哪些对象可以作为字典的键，为什么？

要成为字典的键，一个对象必须满足一个核心条件：它是可哈希的（hashable）。这意味着该对象在生命周期内，其哈希值必须保持不变，并且它需要支持相等性比较。具体来说，可哈希对象必须满足以下两个条件：

1. 拥有

   __hash__()

   登录后复制
   方法： 这个方法必须返回一个整数哈希值。重要的是，如果两个对象被认为是相等的（即

   obj1 == obj2

   登录后复制
   为True），那么它们的哈希值也必须相等（即

   hash(obj1) == hash(obj2)

   登录后复制
   为True）。这是哈希表正确工作的基石。
2. 拥有

   __eq__()

   登录后复制
   方法： 用于判断两个对象是否相等。

为什么哈希值必须不变？ 这是因为字典在查找或存储键时，会先计算键的哈希值来确定其在内部数组中的位置。如果一个对象的哈希值在它作为字典键之后发生了变化，那么当你再次尝试用这个键去查找时，字典会计算出一个新的哈希值，从而定位到错误的（或根本不存在的）位置，导致找不到原本存储的值。这就像你把一本书放在了图书馆的某个位置，但书上的“定位码”自己变了，你再去查原来的码就找不到了。

基于这个原则，我们可以总结出哪些Python对象是可哈希的，哪些不是：

可哈希的对象（可以作为字典的键）：

• 数字类型：

  int

  登录后复制
  ,

  float

  登录后复制
  ,

  complex

  登录后复制
  。它们的数值是不可变的。
• 字符串：

  str

  登录后复制
  。字符串内容创建后就不能改变。
• 元组：

  tuple

  登录后复制
  。只要元组中的所有元素都是可哈希的，那么这个元组就是可哈希的。因为元组本身是不可变的。
• 不可变集合：

  frozenset

  登录后复制
  。这是集合的不可变版本。
• 自定义类的实例： 如果你没有重写

  __hash__

  登录后复制
  和

  __eq__

  登录后复制
  方法，默认情况下，实例是可哈希的（基于其内存地址）。如果你重写了

  __eq__

  登录后复制
  ，那么通常也需要重写

  __hash__

  登录后复制
  ，并确保其满足上述一致性原则。

不可哈希的对象（不能作为字典的键）：

• 列表：

  list

  登录后复制
  。列表是可变的，你可以添加、删除或修改元素，这会导致其哈希值不稳定。
• 字典：

  dict

  登录后复制
  。字典本身也是可变的。
• 集合：

  set

  登录后复制
  。集合是可变的。
• 自定义类的实例： 如果你重写了

  __eq__

  登录后复制
  方法但没有重写

  __hash__

  登录后复制
  方法，Python会默认将该实例视为不可哈希的，除非你显式地将

  __hash__

  登录后复制
  设置为

  None

  登录后复制
  。

理解可哈希性对于正确使用字典至关重要。它确保了字典作为一种高效的键值存储机制，能够始终准确地定位和检索数据。

以上就是字典（Dict）的底层实现原理是什么？的详细内容，更多请关注php中文网其它相关文章！