Python字典的底层实现：为什么Python3.7+字典是有序的

在Python 3.7之前，字典是无序的，遍历字典的顺序取决于键的哈希值和碰撞情况。从Python 3.7开始，字典不仅变得有序，而且内存占用减少了20%-25%。这一变化的核心在于底层实现从“稀疏数组”转变为“紧凑数组”。理解这一机制，需要从Python如何存储键值对说起。

1. 核心机制：双数组结构

在Python 3.7及以后的版本中，字典的底层由两个独立的数组组成：indices（索引数组）和 entries（数据数组）。这种设计将“哈希位置”与“实际数据”分离开来。

• indices 数组：这是一个稀疏数组，用于存储哈希值映射到的索引位置。它的长度通常是2的整数次幂。未使用的位置填充为 -1。
• entries 数组：这是一个紧凑数组，按插入顺序依次存储实际的键值对数据（哈希值、键、值）。

这种分离使得数据可以连续存储，从而自然保留了插入顺序。

2. 数据插入流程：如何保持有序

当我们向字典中插入一个键值对时，Python会执行一系列操作来计算位置并存储数据。

假设我们要执行 d["username"] = "admin"。

1. 计算 键的哈希值。Python调用 hash("username") 得到一个整数。
2. 计算 索引位置。使用掩码运算确定在 indices 数组中的位置。公式为：
   $$ index = hash \pmod{size} $$
   或者在底层实现中通常使用位运算：
   $$ index = hash \ \& \ (size - 1) $$
   其中 size 是 indices 数组的长度。
3. 探测 可用位置。如果计算出的 index 位置已被占用（即发生了哈希冲突），Python会线性探测下一个位置（index + 1），直到找到为 -1 的空槽位。
4. 记录 插入位置。在 entries 数组的末尾追加当前的数据 [hash, key, value]。假设这是插入的第1个元素，它在 entries 中的索引是 0。
5. 建立 映射关系。将 entries 的索引 0 填入步骤3中找到的 indices 数组的位置。

此时，entries 数组按插入顺序增长，而 indices 数组负责通过哈希值指向 entries 中的具体位置。

为了更直观地理解这种映射关系，请参考下方的结构图。假设 indices 大小为8，当前插入了两个键值对。

3. 数据查找流程：利用索引定位

查找一个键（例如读取 d["username"]）时，Python利用 indices 数组快速定位，无需遍历整个数据表。

1. 重复 计算哈希和索引的过程。对键 "username" 执行相同的哈希和掩码运算，得到目标 index。
2. 检查 indices[index] 的值。
   • 如果值为 -1，说明键不存在。
   • 如果值不为 -1，该值即为数据在 entries 数组中的索引（例如 0）。
3. 跳转 到 entries[0]。
4. 验证 哈希值和键是否匹配。虽然哈希碰撞概率很低，但为了安全，Python会再次对比 entries[0] 中的哈希值和键本身。
5. 返回 对应的值。

这一过程将查找的时间复杂度维持在平均 $O(1)$。

4. 为什么遍历是有序的

当我们使用 for key in d: 遍历字典时，Python的底层实现发生了变化。

• 旧版实现：遍历时需要跳过 indices 数组中的空位，顺序是混乱的。
• 新版实现：遍历器直接忽略 indices 数组，而是线性地从头到尾扫描 entries 数组。

因为 entries 数组是严格按照插入顺序追加数据的，所以遍历结果自然也是有序的。这种设计在遍历性能上也有显著提升，因为CPU对连续内存（entries）的读取效率远高于跳跃内存（旧版的稀疏表）。

5. 新旧实现对比

下表总结了Python 3.6之前与3.7+版本字典实现的核心区别。

6. 删除操作的特殊处理：伪删除

为了保证 entries 数组的紧凑性和插入顺序的完整性，Python在删除元素时采用了“伪删除”策略。

1. 定位 目标键值对在 indices 和 entries 中的位置。
2. 标记 entries 中对应位置的槽位为“ Dummy ”（虚拟状态）。
3. 清除 indices 中对应的索引值，将其设为 -1（或特定的标记值）。

注意：数据并没有从 entries 数组中物理移除，因为那样会破坏后续元素的索引顺序。但在遍历时，迭代器会自动跳过这些被标记为 Dummy 的槽位。只有当字典进行扩容（Resize）时，这些真正无用的数据才会被彻底清理。