Python 字典底层哈希表的实现原理是什么？

Python 字典底层就是一张哈希表，从 3.6 开始，用的是更省内存、还能记住插入顺序的紧凑表。

🧱 数据结构：两张表拼成一张“紧凑表”¶

传统哈希表每个槽位存 [hash, key, value]，有很多空槽很浪费。Python 把它拆成了两块：

indices 数组：存的是“索引的索引”，每个槽位放一个整数，指向 entries 数组的位置。
entries 数组：按插入顺序存放实际条目，每个条目 [hash, key, value]。

这样空槽位只占 indices 里一个很小的整数，而 entries 紧凑排列，遍历时天然就是插入顺序。

indices:  [-1, 2, -1, 0, 1, -1, ...]   ← 每个格子存 entry 的编号，-1 表空
entries:  [条目0: hash_a, key_a, val_a,
           条目1: hash_b, key_b, val_b,
           条目2: hash_c, key_c, val_c]

找键 b 时：hash(b) → 与掩码运算 → 索引指向 indices[3] → 值是 1 → 去 entries[1] 取出键值对。

🔍 插入与查找：开放寻址 + 随机探测¶

计算位置：hash(key) & mask，mask = 表大小-1，保证结果不越界。
冲突处理：如果 indices[i] 已被占用，Python 用伪随机探测序列找下一个位置，经典公式：

perturb >>= 5
i = (i*5 + 1 + perturb) & mask

不是简单的线性找下一个，而是跳着找，避免连续堆积。
比较：找到 indices[i] 指向的 entries 条目后，先比 hash 值（快筛），再比 key 对象是否相等（==）。双重检查保证正确性。

📈 扩容：负载超过 2/3 就翻倍¶

字典会跟踪 used / size，当超过 2/3 时：

分配一个新的 indices 数组（大小翻倍）和一个新的 entries 数组。
把所有老条目重新哈希插入新表。
丢弃旧表。

虽然扩容时是 O(n)，但平摊到每次插入依然是 O(1)。

⚠️ 为什么键必须是不可变的¶

因为键的哈希值在插入时就定死了。如果键对象变了，它的哈希值也会变，字典就再也找不到原来的条目了——相当于你自己把门牌号涂改了，包裹永远送不到。

🧠 一个小彩蛋¶

字典在只存字符串键时，内部还有专门的优化路径，能比通用键更快。这也是为什么很多配置、属性传递都用 **kwargs 这种全是字符串键的字典——Python 已经在底层替你想好了。