文章目录Python 字典的无序与有序——Hash 表到底怎么存你的 Key导入语1 ~ 字典的本质——不是数组是 Hash 表1.1 为什么字典查找是 O(1)1.2 但是哈希碰撞2 ~ Python 如何解决哈希碰撞——开放寻址法3 ~ Python 3.6 之前的字典——无序的根源4 ~ Python 3.6 的紧凑存储——为什么又有序了5 ~ 扩容——什么时候字典会变慢6 ~ Python 字典的使用限制6.1 Key 必须可哈希6.2 字典遍历中不能修改大小思考 总结结尾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_valuehash(key)# 把字符串映射成一个整数indexhash_value%table_size# 取模 → 得到槽位下标整个魔术字就是取模——不管 key 是什么类型hash()都能输出一个唯一整数取模后落到固定范围内的某个槽位上。所以字典查找接近 O(1)。1.2 但是哈希碰撞两个不同的 keyhash()之后取模落到同一个槽位怎么办这叫做哈希碰撞。2 ~ Python 如何解决哈希碰撞——开放寻址法常见的做法有链地址法每个槽位挂一个链表碰撞了往里挂但Python 用的是开放寻址法——碰撞了就在哈希表里接着往后找直到找到空槽位。具体做法是indexhash(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 会扩容分配一块更大的内存通常是当前容量的 2 倍把所有 key 重新 hash 到新的哈希表中rehash旧哈希表被释放# 你可以用 sys.getsizeof 看到字典大小的跳变importsys d{}print(sys.getsizeof(d))# 初始 72 字节Python 3.8foriinrange(100):d[i]iprint(sys.getsizeof(d))# 现在大概 4700 字节如果你提前知道要插入几百个 key-value用dict.fromkeys()直接分配好初始容量能避免反复 rehash# 预先分配keysrange(1000)ddict.fromkeys(keys)不过日常代码不用太纠结这个只有处理海量插入时才有意义。6 ~ Python 字典的使用限制6.1 Key 必须可哈希只有不可变类型才能做 key。因为 key 变了hash 值也会变Python 就找不回原来的槽位。# ✅ 可哈希d{1:一,key:value,(1,2):元组}# ❌ 不可哈希d{[1,2]:列表}# TypeError: unhashable type: list6.2 字典遍历中不能修改大小d{a:1,b:2}forkind:deld[k]# RuntimeError: dictionary changed size during iteration上一篇文章详细拆了这个问题。安全的做法是用列表推导式构造新字典或者先收集要删的 key 再统一删除。思考 总结字典底层是哈希表 开放寻址法。key 通过hash()计算槽位碰撞后向后探测。查询、插入、删除都接近 O(1)。有序是紧凑存储的副产品。Python 3.6 将字典拆为索引表 数据表数据表按插入顺序追加遍历自然就是插入顺序。这不是主动设计的有序性但 Python 3.7 把它写入了语言规范。负载因子超 2/3 时扩容。扩容是新建更大的表 rehash 所有 key。预知数据量大时一次性插入比逐步追加更高效。Key 必须可哈希不可变。因为 key 变了 hash 就变字典找不到原来的槽位。结尾各位小伙伴本文到此全部结束感谢阅读源码骑士 — Python 全栈 系统架构关注跟博主一起从源码视角深耕底层原理见证每一次成长❤️点赞让优质内容被更多人看见让知识传递更有力量⭐收藏把核心知识点存好在菜鸟仓随用随查评论分享你的经验或疑问评论区一起交流避坑一键四连不要忘记给博主一键四连哦今日源码拆解达成️寄语技术之路同行的人会让前路更有方向结语字典讲完了接下来是一个让很多同学会写但不知道为什么这样写的话题——装饰器。我们下篇见。一键四连别忘了
05-Python字典底层原理-Hash表与有序性的真相
发布时间：2026/6/14 0:58:22
文章目录Python 字典的无序与有序——Hash 表到底怎么存你的 Key导入语1 ~ 字典的本质——不是数组是 Hash 表1.1 为什么字典查找是 O(1)1.2 但是哈希碰撞2 ~ Python 如何解决哈希碰撞——开放寻址法3 ~ Python 3.6 之前的字典——无序的根源4 ~ Python 3.6 的紧凑存储——为什么又有序了5 ~ 扩容——什么时候字典会变慢6 ~ Python 字典的使用限制6.1 Key 必须可哈希6.2 字典遍历中不能修改大小思考 总结结尾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_valuehash(key)# 把字符串映射成一个整数indexhash_value%table_size# 取模 → 得到槽位下标整个魔术字就是取模——不管 key 是什么类型hash()都能输出一个唯一整数取模后落到固定范围内的某个槽位上。所以字典查找接近 O(1)。1.2 但是哈希碰撞两个不同的 keyhash()之后取模落到同一个槽位怎么办这叫做哈希碰撞。2 ~ Python 如何解决哈希碰撞——开放寻址法常见的做法有链地址法每个槽位挂一个链表碰撞了往里挂但Python 用的是开放寻址法——碰撞了就在哈希表里接着往后找直到找到空槽位。具体做法是indexhash(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 会扩容分配一块更大的内存通常是当前容量的 2 倍把所有 key 重新 hash 到新的哈希表中rehash旧哈希表被释放# 你可以用 sys.getsizeof 看到字典大小的跳变importsys d{}print(sys.getsizeof(d))# 初始 72 字节Python 3.8foriinrange(100):d[i]iprint(sys.getsizeof(d))# 现在大概 4700 字节如果你提前知道要插入几百个 key-value用dict.fromkeys()直接分配好初始容量能避免反复 rehash# 预先分配keysrange(1000)ddict.fromkeys(keys)不过日常代码不用太纠结这个只有处理海量插入时才有意义。6 ~ Python 字典的使用限制6.1 Key 必须可哈希只有不可变类型才能做 key。因为 key 变了hash 值也会变Python 就找不回原来的槽位。# ✅ 可哈希d{1:一,key:value,(1,2):元组}# ❌ 不可哈希d{[1,2]:列表}# TypeError: unhashable type: list6.2 字典遍历中不能修改大小d{a:1,b:2}forkind:deld[k]# RuntimeError: dictionary changed size during iteration上一篇文章详细拆了这个问题。安全的做法是用列表推导式构造新字典或者先收集要删的 key 再统一删除。思考 总结字典底层是哈希表 开放寻址法。key 通过hash()计算槽位碰撞后向后探测。查询、插入、删除都接近 O(1)。有序是紧凑存储的副产品。Python 3.6 将字典拆为索引表 数据表数据表按插入顺序追加遍历自然就是插入顺序。这不是主动设计的有序性但 Python 3.7 把它写入了语言规范。负载因子超 2/3 时扩容。扩容是新建更大的表 rehash 所有 key。预知数据量大时一次性插入比逐步追加更高效。Key 必须可哈希不可变。因为 key 变了 hash 就变字典找不到原来的槽位。结尾各位小伙伴本文到此全部结束感谢阅读源码骑士 — Python 全栈 系统架构关注跟博主一起从源码视角深耕底层原理见证每一次成长❤️点赞让优质内容被更多人看见让知识传递更有力量⭐收藏把核心知识点存好在菜鸟仓随用随查评论分享你的经验或疑问评论区一起交流避坑一键四连不要忘记给博主一键四连哦今日源码拆解达成️寄语技术之路同行的人会让前路更有方向结语字典讲完了接下来是一个让很多同学会写但不知道为什么这样写的话题——装饰器。我们下篇见。一键四连别忘了
