传统哈希表(比如上一个系列讲过的 Redis dict)按哈希值把元素扔进桶里,天生不记顺序。Python 的 dict 从 3.6 开始变成"紧凑有序"的:内部拆成两个数组——一个稀疏的哈希表只存"第几个位置",一个紧凑数组按插入顺序真正存着键值对。这一篇本机真实验证了插入顺序在增删之后到底怎么变、真实制造了一批哈希值完全相同的 key 观察冲突处理,顺手挖到了开放寻址探测序列背后一段挺有历史的真实源码注释。
3.6 之前的 Python dict 和大多数语言的哈希表一样,遍历顺序取决于哈希值,和插入顺序毫无关系。
键值对直接存在按哈希值定位的桶里——数组本身既是"查找用的哈希表"又是"存数据的地方"。空间利用率打了折扣(要按哈希表的装载因子留足空桶),遍历顺序也是哈希值决定的,不是插入顺序。
稀疏的哈希表(dk_indices)只存"这个哈希槽对应第几号元素";真正的键值对紧凑地按插入顺序存在另一个数组(dk_entries)里——遍历直接走这个紧凑数组,顺序天然就是插入顺序。
删除一个 key,紧凑数组里对应的位置不会被搬移压缩,只是打上"墓碑"标记——这也是为什么删除再重新插入同一个 key,顺序上它会跑到最后面去,单纯改值则完全不影响顺序。
源码注释里直接画了结构图,连"稀疏哈希表里每个索引用几个字节存"都写清楚了——这是个会随表大小变化的细节,大多数教程不会提。
Objects/dictobject.c · cpython @ v3.14.7, L17 +---------------------+ | dk_refcnt / dk_log2_size / dk_usable / dk_nentries / ... +---------------------+ | dk_indices[] | ← 稀疏哈希表,存的是 dk_entries 里的下标 +---------------------+ | dk_entries[] | ← 紧凑数组,严格按插入顺序存键值对 +---------------------+ dk_indices 每个槽存的是 entries 里的下标,或者 DKIX_EMPTY(-1)、DKIX_DUMMY(-2)。 索引本身的类型随表大小变化: * int8 当 dk_size <= 128 * int16 当 256 <= dk_size <= 2**15 * int32 当 2**16 <= dk_size <= 2**31 * int64 当 dk_size >= 2**32
表小的时候,稀疏哈希表里存的"下标"用 1 个字节就够了(表不超过 128 项),没必要每个槽都花 8 个字节——这是一个真实存在、会随 dict 变大动态调整宽度的内存优化。这套设计最早在 2012 年的一封 python-dev 邮件里提出(源码注释里直接留了链接),PyPy 团队独立发现过类似思路,Python 3.6 正式采纳。
d = {'a': 1, 'b': 2, 'c': 3}
print('初始顺序:', list(d.keys()))
del d['b']
d['b'] = 20
print('删除 b 再重新插入之后:', list(d.keys()))
d2 = {'x': 1, 'y': 2, 'z': 3}
d2['y'] = 99 # 只是改值,没有删除
print('单纯改值(不删除)之后:', list(d2.keys()))
初始顺序: ['a', 'b', 'c']
删除 b 再重新插入之后: ['a', 'c', 'b']
单纯改值(不删除)之后: ['x', 'y', 'z']
完全符合"紧凑数组只追加、删除留墓碑"的模型:改值命中的是已有条目,直接原地更新,位置不变;删除之后重新插入,紧凑数组里那个位置已经废了,新条目只能追加到数组末尾,遍历顺序自然就把它排到最后。
哈希冲突时怎么找下一个候选位置,CPython 用的不是简单的"往后挪一格"(线性探测),而是一个刻意设计过的递推公式。
Objects/dictobject.c · cpython @ v3.14.7, L344 perturb >>= PERTURB_SHIFT; j = (5*j) + 1 + perturb; use j % 2**i as the next table index; /* Selecting a good value for PERTURB_SHIFT is a balancing act... 5 was * "the best" in minimizing total collisions across experiments Tim Peters * ran (on both normal and pathological cases), but 4 and 6 weren't * significantly worse. */
纯粹的 5*j+1 递推本身会按固定顺序扫描——如果哈希值恰好是连续的(很常见,比如小整数做 key),固定扫描顺序反而是好事;但光这样还不够稳,所以每探测一次就把 perturb(初始值是完整的哈希值)右移 5 位混进递推公式,让哈希值的高位也参与进来。这个"右移 5 位"里的 5,是 Tim Peters(Python 核心开发者,也是那句著名的 import this 之父)拿真实数据和病态用例反复实验调出来的——4 和 6 效果也不算差,但 5 是当时试出来最好的。
自定义一个 __hash__,让 2000 个不同的对象全部返回同一个哈希值,看 dict 还能不能正确工作。
2000 个 key 哈希值完全一样,dict 照样能正确区分它们(靠探测到每个槽位之后再用 __eq__ 确认)——但插入慢了 1337 倍,因为每插入一个新 key 都要沿着探测序列走过前面所有已经占用的槽位才能找到空位,退化成了接近 O(N) 每次插入。这就是"好的哈希函数"真正的价值:不是为了"不冲突"(冲突永远可能发生),是为了让探测序列尽量短。
import sys
prev = None
for n in range(30):
d = {i: i for i in range(n)}
s = sys.getsizeof(d)
if s != prev:
print(f'n={n:3d} sys.getsizeof={s}')
prev = s
n= 0 sys.getsizeof=64
n= 1 sys.getsizeof=224
n= 6 sys.getsizeof=352
n= 11 sys.getsizeof=632
n= 22 sys.getsizeof=1168
扩容节点在 n=6、11、22 附近——真实源码里两条规则共同决定了这些数字:
Objects/dictobject.c · L116 / L543 / L590 #define PyDict_MINSIZE 8 #define USABLE_FRACTION(n) (((n) << 1)/3) /* 最多用到 2/3 满 */ #define GROWTH_RATE(d) ((d)->ma_used*3) /* 触发扩容时,新容量按"已用量 * 3"来算 */ /* GROWTH_RATE was set to used*4 up to version 3.2. * GROWTH_RATE was set to used*2 in version 3.3.0 * GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0. */
新 dict 初始容量 8,最多用到三分之二(约 5 个)就要扩容;扩容后的新容量不是简单乘 2,是按"当前已用元素数 × 3"来估算——源码注释里留了这个倍率从 3.2 到现在改了三次的完整历史,现在这版本是为了在"频繁增删"和"纯追加"两种场景之间留出更均衡的余量。
复现前面"a、b、c 插入 → 删除 b 再重插 → 改 a 的值"这个真实场景,表容量设成 8(和真实 PyDict_MINSIZE 一致),用真实的 5*j+1+perturb 探测序列。
探测路径(遇到冲突时走过的槽位)用琥珀色高亮标出;数据经过独立回放校验——最终两个数组的内容,和单纯重放事件日志重新算一遍得到的结果完全一致。