企业官网建设流程全解析

Python 字典的无序与有序——Hash 表到底怎么存你的 Key

📖文章简介：Python 字典是使用频率最高的数据结构之一，但大多数人对它的认知停留在"key-value 存取"。本文从 hash 表原理讲起，逐步推导到 Python 字典的底层实现：哈希函数 → 哈希碰撞 → 开放寻址法 → 负载因子与扩容。重点讨论 Python 3.6+ 字典"有序"的实现原理——实际上是"紧凑存储 + 索引表"的设计带来的副作用，而非真正的有序数据结构。穿插真实场景：为什么用dict代替OrderedDict做 LRU 缓存时要小心、字典在多线程环境下的读写安全边界。读完你对字典的理解将从"会用"升级到"知道它怎么存的"。

🎬 个人主页：源码骑士

❄专栏传送门：《Android开发基础》《python基础课程》

⭐️热衷从源码视角拆解技术底层原理，将复杂架构讲得通俗易懂

🎬 源码骑士的简介：
5年Android Framework系统开发经验，曾主导多项系统级性能优化专项
技术栈覆盖Android系统全链路（Binder/Handler/AMS/WMS/启动流程）及Java后端全家桶（Spring + MyBatis + Redis + Oracle）
累计产出原创技术文章100+篇，文章以源码拆解为特色，被读者评价为"看一篇胜过啃一周文档"

导入语

字典——你在 Python 里用的最多的数据结构，没有之一。但你真的理解它怎么存数据吗？

我面试过一个人，他简历上写"熟练使用 Python 字典"，我问"Python 3.6 之后字典是有序的还是无序的"，他犹豫了半天，说"无序的，因为字典基于 hash"。我接着问"但为什么 Python 3.7 官方把’字典保持插入顺序’写进了语言规范？"，他答不上来。

这个问题我早年也没有关注细节。早年在 Python 3.5 里字典确实是"不保证顺序"的，后来某个项目需要按插入顺序遍历字典，同事给了个OrderedDict——我也不知道为什么需要这个。后来看到一篇 CPython 源码分析的帖子，"字典重构"时才恍然大悟：Python 3.6 用了一种叫"紧凑存储"的设计，保持插入顺序只是它的副效应。

1 ~> 字典的本质——不是数组，是 Hash 表

1.1 为什么字典查找是 O(1)

数组按下标访问是 O(1)——因为知道下标就能直接计算内存地址：基地址 + 下标 × 元素大小。

字典的"key"怎么变成下标？靠哈希函数：

key="张三"hash_value=hash(key)# 把字符串映射成一个整数index=hash_value%table_size# 取模 → 得到槽位下标

整个魔术字就是"取模"——不管 key 是什么类型，hash()都能输出一个唯一整数，取模后落到固定范围内的某个槽位上。所以字典查找接近 O(1)。

1.2 但是：哈希碰撞

两个不同的 key，hash()之后取模落到同一个槽位怎么办？这叫做"哈希碰撞"。

2 ~> Python 如何解决哈希碰撞——开放寻址法

常见的做法有"链地址法"（每个槽位挂一个链表，碰撞了往里挂），但Python 用的是开放寻址法——

碰撞了就在哈希表里接着往后找，直到找到空槽位。具体做法是：

index=hash(key)% size 如果 slots[index]已经被占用： 向后循环探测 index=(index + perturb)% size 直到找到空槽位

这个设计意味着：字典的每个槽位不是只存一个 key，而是存(key, value, hash)三元组，Python 内部用一个叫PyDictKeyEntry的结构维护。

3 ~> Python 3.6 之前的字典——无序的根源

Python 3.5 及之前，字典的存储结构是一个稀疏表：

[槽位0][槽位1][槽位2][槽位3][槽位4][槽位5]...[槽位7]空(k1,v1)空(k2,v2)空(k3,v3)空

你遍历的时候，挨个扫描槽位，跳过空的，输出非空的。遍历顺序 = 槽位顺序 = 哈希槽的分布，跟你的插入顺序完全无关。这就是字典无序的根本原因。

4 ~> Python 3.6+ 的紧凑存储——为什么又有序了

Python 3.6 引入了一个重要的字典内部表示重构（PEP 468 和 bpo-27350）。新设计将字典拆为两部分：

① 索引表（indices）：一个紧凑的稀疏数组，存的是"去数据表的位置"
② 数据表（entries）：一个紧凑的密集数组，存的是真正的(key, value)对，按插入顺序排列

插入"张三"→ 数据表:[("张三",28)]插入"李四"→ 数据表:[("张三",28),("李四",22)]插入"王五"→ 数据表:[("张三",28),("李四",22),("王五",30)]

遍历字典时，直接按数据表的顺序输出——而数据表是按插入顺序追加的——所以遍历自然就是插入顺序。

这就是那个"副作用"：紧凑存储的本意是为了省内存（减少稀疏浪费），但设计顺便让字典记住了插入顺序。Python 3.7 官方干脆把这个行为写进了语言规范——"字典保持插入顺序"成了强制要求。

5 ~> 扩容——什么时候字典会变慢

当字典的负载因子超过约 2/3 时，Python 会扩容：

1. 分配一块更大的内存（通常是当前容量的 2 倍）
2. 把所有 key 重新 hash 到新的哈希表中（rehash）
3. 旧哈希表被释放

# 你可以用 sys.getsizeof 看到字典大小的跳变importsys d={}print(sys.getsizeof(d))# 初始 72 字节（Python 3.8）foriinrange(100):d[i]=iprint(sys.getsizeof(d))# 现在大概 4700+ 字节

如果你提前知道要插入几百个 key-value，用dict.fromkeys()直接分配好初始容量能避免反复 rehash：

# 预先分配keys=range(1000)d=dict.fromkeys(keys)

不过日常代码不用太纠结这个，只有处理海量插入时才有意义。

6 ~> Python 字典的使用限制

6.1 Key 必须可哈希

只有不可变类型才能做 key。因为 key 变了，hash 值也会变，Python 就找不回原来的槽位。

# ✅ 可哈希d={1:"一","key":"value",(1,2):"元组"}# ❌ 不可哈希d={[1,2]:"列表"}# TypeError: unhashable type: 'list'

6.2 字典遍历中不能修改大小

d={"a":1,"b":2}forkind:deld[k]# RuntimeError: dictionary changed size during iteration

上一篇文章详细拆了这个问题。安全的做法是用列表推导式构造新字典，或者先收集要删的 key 再统一删除。

思考 && 总结

1. 字典底层是哈希表 + 开放寻址法。key 通过hash()计算槽位，碰撞后向后探测。查询、插入、删除都接近 O(1)。
2. "有序"是紧凑存储的副产品。Python 3.6+ 将字典拆为"索引表 + 数据表"，数据表按插入顺序追加，遍历自然就是插入顺序。这不是主动设计的有序性，但 Python 3.7 把它写入了语言规范。
3. 负载因子超 2/3 时扩容。扩容是新建更大的表 + rehash 所有 key。预知数据量大时，一次性插入比逐步追加更高效。
4. Key 必须可哈希（不可变）。因为 key 变了 hash 就变，字典找不到原来的槽位。

结尾

各位小伙伴，本文到此全部结束，感谢阅读！

源码骑士 — Python 全栈 & 系统架构

👀关注：跟博主一起从源码视角深耕底层原理，见证每一次成长

❤️点赞：让优质内容被更多人看见，让知识传递更有力量

⭐收藏：把核心知识点存好在菜鸟仓，随用随查

💬评论：分享你的经验或疑问，评论区一起交流避坑

🔄一键四连：不要忘记给博主"一键四连"哦！今日源码拆解达成！

🗡️寄语：技术之路，同行的人会让前路更有方向

结语：字典讲完了，接下来是一个让很多同学"会写但不知道为什么这样写"的话题——装饰器。我们下篇见。一键四连别忘了！