dict 为什么突然变得有序了？一文讲透哈希表与紧凑字典设计

「Python 进阶之路」系列 Day26写在前面Python 3.7 之后dict遍历顺序被正式写进语言规范一定是按插入顺序。很多人只记住了这个结论但没搞清楚背后的实现原理——这可不是简单加个记录顺序的标记就完事而是 CPython 团队重新设计了整个哈希表的存储结构。模块六常用数据结构与标准库进阶从这里开篇把dict的底层实现讲透。一、是什么哈希表与哈希冲突dict底层是一张哈希表hash table对每个 key 调用hash()算出一个哈希值再用这个哈希值映射到一个槽位slot把 key-value 对存进对应槽位——这样查找时不需要逐个比较直接算出槽位就能定位平均时间复杂度是 O(1)比列表线性查找的 O(n) 快得多。哈希冲突hash collision不同的 key 可能算出同一个槽位。Python 用**开放寻址法open addressing**解决冲突——发生冲突时按一套扰动探测规则去找下一个候选槽位直到找到空位或者找到真正匹配的 key不是像链地址法那样在同一个槽位挂一条链表。二、为什么3.7之后dict变得有序了紧凑字典设计Python 3.6 引入、3.7 起正式写进语言规范dict保证按插入顺序遍历。这背后是 Raymond Hettinger 提出的**紧凑字典compact dict**实现把哈希表和实际存储数据拆成了两层结构一张稀疏的哈希表每个槽位只存一个整数索引指向下面数组里的位置不直接存键值对一个紧凑的数组按插入顺序依次追加真正的键值对数据紧凑数组按插入顺序存储稀疏哈希表只存索引槽位0指向索引1槽位2指向索引0槽位3指向索引20号 c 存的是31号 a 存的是12号 b 存的是2这个设计一举两得旧实现里哈希表数组本身直接存键值对为了控制哈希冲突概率必须预留大量空槽位负载因子通常控制在 2/3 左右这些空位全是浪费的内存新设计里哈希表只存索引这一个整数比存完整键值对省了不少内存而真正的数据全部按插入顺序追加进那个紧凑数组遍历这个数组自然就是插入顺序——省内存和保持顺序是同一次架构调整顺带解决的两个问题。三、怎么用1. hash()与不可哈希类型print(hash(apple)hash(apple))# True同一个字符串哈希值相同print(hash(1)hash(1.0)hash(True))# True —— 1 1.0 TruePython约定相等的对象必须哈希值相同可变对象不能做 key因为可变对象的内容可能变化但哈希值必须保持不变否则存进去之后就再也找不到了这个矛盾导致 Python 干脆把可变类型设计成不可哈希{[1,2]:value}# TypeError: unhashable type: listhash([1,2])# TypeError: unhashable type: listhash((1,2))# -3550055125485641917 —— tuple 可以哈希前提是内部元素也都可哈希2. dict保持插入顺序d{}d[c]3d[a]1d[b]2print(list(d.keys()))# [c, a, b] —— 按插入顺序不是按key排序deld[a]d[a]100# 重新插入print(list(d.keys()))# [c, b, a] —— a被删除后重新插入跑到了最后面dict.keys()/values()/items()拿到的都是保持顺序的视图可以放心用zip()配对d2{x:1,y:2,z:3}fork,vinzip(d2.keys(),d2.values()):print(k,v)# x 1 / y 2 / z 3顺序完全一致3. 阶梯式扩容importsys d3{}print(sys.getsizeof(d3))# 64 bytes空dictforiinrange(20):d3[i]iprint(sys.getsizeof(d3))实测观察到的变化空dict: 64 bytes 插入第1个元素后: 224 bytes第一次扩容 插入第6个元素后: 352 bytes第二次扩容 插入第11个元素后: 632 bytes第三次扩容内存占用不是随着元素数量线性平滑增长的而是攒到某个负载阈值就整体扩容一次——这也是为什么如果提前知道要插入多少元素用dict.fromkeys()或者一次性构造往往比逐个d[k] v增量插入更高效能减少扩容次数。4. 哈希冲突不会导致数据出错classBadHash:def__init__(self,value):self.valuevaluedef__hash__(self):return1# 故意让所有实例哈希值都一样制造哈希冲突def__eq__(self,other):returnisinstance(other,BadHash)andself.valueother.value a,b,cBadHash(A),BadHash(B),BadHash(C)print(hash(a)hash(b)hash(c))# True三个对象哈希值故意设成一样d4{}d4[a]value_ad4[b]value_bd4[c]value_cprint(d4[a],d4[b],d4[c])# value_a value_b value_c —— 依然能正确区分print(len(d4))# 3 —— 三个不同key确实都被正确存了进去没有互相覆盖哈希冲突不会导致数据错乱或丢失只会让存取这几个冲突的 key 时多做几次探测比较依赖__eq__做最终判断性能会打折扣但正确性完全不受影响——这也是为什么自定义类的__hash__和__eq__必须配合一致哈希值相同只是候选__eq__才是最终确认是不是同一个 key的依据。四、面试追问Q1dict 底层是怎么实现的哈希表对 key 调用hash()算出槽位实现平均 O(1) 的查找/插入/删除Python 3.6 用紧凑字典设计把稀疏的哈希表只存索引和紧凑的数据数组按插入顺序存储拆成两层结构。Q2为什么 dict 的 key 必须是可哈希的因为 key 需要通过hash()计算槽位才能定位可变对象的内容可能变化但哈希值必须保持不变这个矛盾导致 Python 把 list、dict 等可变类型设计成不可哈希无法作为 key。Q3Python 3.7 之后为什么 dict 变得有序了紧凑字典设计把真正的键值对数据存进一个按插入顺序追加的紧凑数组哈希表本身只存指向这个数组的索引遍历数组自然就是插入顺序。这个改动同时也省了内存——不再需要在哈希表里给键值对预留大量空槽位。Q4哈希冲突是怎么解决的Python 用开放寻址法发生冲突时按一套探测规则去找下一个候选槽位直到找到空位或者通过__eq__确认是同一个 key哈希冲突不影响正确性只会增加一点探测开销。Q5dict 的查找/插入/删除时间复杂度是多少为什么平均情况下都是 O(1)因为通过哈希值可以直接算出或很快探测到目标槽位不需要遍历最坏情况大量哈希冲突会退化但 Python 的哈希算法和扩容策略让这种情况在正常使用中很少发生。下一篇预告Day27 讲set的应用场景与去重原理——set底层和dict是近亲今天讲的哈希表知识大部分能直接复用。