目录一、引言为什么Python字典这么快二、哈希表是什么先搞懂这个才能懂字典2.1 从数组到哈希表一个思考过程2.2 哈希函数把任意东西变成数字2.3 哈希冲突当两个键指向同一个位置三、走进源码PyDictObject到底是什么3.1 CPython中字典的核心结构3.2 小字典优化为什么新建的字典不直接分配大内存四、字典的紧凑存储模型Python 3.64.1 从传统设计到紧凑设计4.2 键值分离的设计思想4.3 为什么紧凑设计更快更省内存五、字典操作的核心流程从源码看细节5.1 哈希计算从键到数字5.2 查找流程lookdict函数是怎么工作的5.3 冲突处理Python的伪随机探测算法5.4 插入操作当键不存在时5.5 删除操作为什么被删除的槽位还在六、动态扩容与负载因子6.1 什么时候扩容6.2 扩容的过程重哈希Rehash6.3 为什么Python选择2/3作为阈值七、字典的内存占用到底有多大7.1 一个空字典占多少内存7.2 随着元素增加内存如何增长7.3 紧凑字典的内存优势八、字典的性能优化与注意事项8.1 选择合适的键类型8.2 预分配容量8.3 小心哈希攻击8.4 字典 vs 其他映射类型九、常见面试题一、引言为什么Python字典这么快在Python开发中我们几乎每天都要和字典打交道。配置信息、数据缓存、对象属性……到处都有它的身影。但你有没有好奇过为什么字典查找一个键的速度几乎不受字典大小的影响无论是10个键还是1000万个键my_dict[key]的执行时间几乎是恒定的——这就是O(1)时间复杂度的魅力。这个奇迹的背后藏着一个叫做哈希表Hash Table的数据结构。Python的字典正是哈希表的一个经典实现。本文将带你一步步深入CPython的源码从最基础的概念开始揭秘字典的内部工作原理。二、哈希表是什么先搞懂这个才能懂字典2.1 从数组到哈希表一个思考过程想象你有一个数组列表要从中找出某个特定的元素。如果不知道它在哪个位置你只能挨个检查——这就是O(n)的时间复杂度在数据量大的时候会非常慢。现在如果我们能有一种魔法给定一个键就能直接算出它应该存放在数组的哪个位置那查找不就变成O(1)了吗这个魔法就是哈希函数。2.2 哈希函数把任意东西变成数字哈希函数的作用很简单把任意类型的输入比如字符串、数字、元组转换成一个固定范围内的整数。python # Python中内置的hash函数 print(hash(hello)) # 比如输出-1004758382858577792 print(hash(42)) # 输出42整数hash就是它本身 print(hash((1, 2, 3))) # 元组也可以哈希这个整数就是键的指纹。有了这个指纹我们就可以把它映射到数组的某个位置。2.3 哈希冲突当两个键指向同一个位置世界上不存在完美的哈希函数。不同的键有可能算出相同的哈希值或者虽然哈希值不同但对数组大小取模后落到了同一个位置。这种情况叫做哈希冲突。举个例子假设数组只有8个位置hash(apple) % 8 3hash(orange) % 8 3那么苹果和橙子就会争夺同一个位置。怎么解决呢不同语言有不同策略。Java的HashMap用的是链地址法每个位置放一个链表而Python字典用的是开放寻址法发生冲突就去找下一个空位置。开放寻址法的直观理解想象你在一个停车场找车位。你想停的位置车位3已经被占了你不会掉头离开整个停车场而是继续往前开找到下一个空位停下。这就是开放寻址——冲突了没关系继续往下找。三、走进源码PyDictObject到底是什么3.1 CPython中字典的核心结构在CPython源码中字典的实现位于Objects/dictobject.c文件中。核心结构体PyDictObject包含以下重要成员typedef struct _dictobject PyDictObject; struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; // 字典中已存储的键值对数量 Py_ssize_t ma_used; // 散列表中已被使用的槽位数量 Py_ssize_t ma_mask; // 散列表的掩码用于计算索引位置 PyDictEntry *ma_table; // 散列表的槽位数组 PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; // 小型字典的默认数组 };各个字段的含义ma_fill 字典中有效键值对的数量不含已被删除的ma_used 哈希表中已被占用的槽位数量包括被标记删除的ma_mask 掩码值等于size - 1用于快速计算索引ma_table指向哈希表数组的指针ma_smalltable 小型字典的默认数组大小通常为83.2 小字典优化为什么新建的字典不直接分配大内存你可能会注意到PyDictObject里有两个表ma_table和ma_smalltable。原因很简单Python代码中有大量的小字典。如果一个字典只有两三个键值对却直接分配一个大型哈希表内存浪费会非常严重。所以Python做了一个聪明的优化当字典的键值对数量少于PyDict_MINSIZE默认是8时ma_table直接指向ma_smalltable使用预先分配的8个槽位。只有当字典中的元素数量超过这个阈值时才会动态分配更大的内存空间。python # 新建的空字典底层只有8个槽位的小数组 d {} d[a] 1 # 仍然在这个小数组内 # 当键值对数量超过阈值后才会扩容 for i in range(10): d[fkey{i}] i # 某个时刻会触发扩容这就像你买了一个小盒子装日常杂物等东西多到装不下了再换大箱子——既省钱又高效。四、字典的紧凑存储模型Python 3.64.1 从传统设计到紧凑设计在Python 3.5及之前版本字典的存储方式比较直接一个哈希数组直接存储键值对。这种设计的缺点是内存利用率低——为了减少冲突哈希表需要保持稀疏大量槽位是空的。Python 3.6引入了一个革命性的改变紧凑哈希表Compact Hash Table。从Python 3.7开始这一设计成为正式标准还意外地让字典变得有序保持插入顺序。4.2 键值分离的设计思想紧凑字典的核心思想可以用一句话概括把找位置和存数据分开。具体来说字典内部维护了两个数组1. indices数组索引数组大小是2的幂每个元素是一个整数指向entries数组中的位置或者用特殊值标记空槽-1和已删除槽-2。2. entries数组条目数组按插入顺序存储键值对每个entry包含me_hash哈希值、me_key键和me_value值。4.3 为什么紧凑设计更快更省内存这种设计带来三大好处1. 内存更省indices数组可以使用更小的整数类型如int8、int16、int32根据字典大小自适应选择大大减少了内存占用。2. 迭代更快遍历字典时只需要线性扫描entries数组跳过空槽即可。由于entries是连续存储的CPU缓存命中率极高。3. 天然有序entries数组按插入顺序排列因此dict.keys()、dict.values()、dict.items()的返回顺序就是插入顺序——这个特性从Python 3.7开始正式成为语言规范。python # Python 3.7 字典保持插入顺序 d {} d[banana] 3 d[apple] 2 d[orange] 1 print(list(d.keys())) # [banana, apple, orange] —— 保持插入顺序五、字典操作的核心流程从源码看细节5.1 哈希计算从键到数字当执行d[key] value时Python的第一步是计算键的哈希值hash_value PyObject_Hash(key)Python内置的不可变类型str、int、tuple等都实现了__hash__()方法。对于自定义类的实例如果该实例是可哈希的实现了__hash__和__eq__方法也可以作为字典的键。注意列表、字典、集合是不可哈希的因为它们是可变的。如果把列表作为字典的键Python会抛出 TypeError: unhashable type: list。5.2 查找流程lookdict函数是怎么工作的查找是字典最核心的操作插入和删除都依赖它。Python 3.6的查找流程如下1. 计算哈希值 h hash(key)2. 计算初始索引 i h (size - 1) —size是2的幂位运算代替取模3. 查看 indices[i]如果 indices[i] -1该位置从未使用过键不存在 → 返回未找到如果 indices[i] -2该位置曾被使用后删除继续探测如果 indices[i] 0去 entries[indices[i]] 取 entry4. 比对哈希值和键是否匹配如果 entry.me_hash h 且 entry.me_key key 或 key相等找到返回结果否则继续探测下一个位置5.3 冲突处理Python的伪随机探测算法当初始位置已经被占用时Python不会简单地1线性探测而是采用一种更聪明的伪随机探测算法j (5*j) 1 perturb perturb 5其中perturb初始化为哈希值右移5位每次迭代后继续右移。这个算法在源码中的注释被称为perturb策略它的优点是让探测序列看起来像随机的有效避免聚集问题——即多个冲突的键挤在一起形成长链。5.4 插入操作当键不存在时插入一个新键值对的流程如下1. 通过lookdict查找键是否存在。2. 如果键已存在直接覆盖me_value。3. 如果键不存在找到一个空闲槽位indices中为-1或-2的位置在entries数组末尾追加一个新的entry将indices[i]指向该entry的索引更新ma_used计数5.5 删除操作为什么被删除的槽位还在删除一个键时Python并不会立即把该位置清空并回收内存。相反它会把indices中对应的位置标记为-2DELETED即伪空位。为什么不直接清空呢——因为开放寻址的查找链不能断。想象一下你在停车场找车位沿着一条路径找到了一个空位。但如果有人把某个中间车位彻底移除了标记为空后面的人沿着同一条路径可能会误以为后面也没有车位了。所以删除操作只能打一个暂不可用的标记而不能把位置真正清空。python # 底层表现删除元素后字典大小可能没有变小 d dict.fromkeys(range(1000)) import sys print(sys.getsizeof(d)) # 某个较大的值 for i in range(500): del d[i] print(sys.getsizeof(d)) # 大小没有减少只是内部标记为DELETED这就是为什么频繁增删字典不会立即释放内存——那些被标记为DELETED的槽位会一直占用空间直到字典触发扩容或缩容时才会被清理。六、动态扩容与负载因子6.1 什么时候扩容字典不会无限地在一个固定大小的哈希表里塞东西。当槽位被占用的比例太高时哈希冲突的概率会急剧上升性能会下降。Python字典使用一个指标叫负载因子used / size已使用槽位数 / 总槽位数。当负载因子达到约2/3时字典就会触发扩容。python # 观察字典何时扩容 d {} for i in range(20): d[i] i print(f元素数量: {len(d)}, 底层大小: {len(d.keys().__sizeof__()? 实际无法直接获取)})6.2 扩容的过程重哈希Rehash扩容的过程可以理解为搬家1. 计算新的大小通常是原大小的2倍对于小字典可能是4倍并且新大小保持为2的幂。2. 分配新的indices数组和entries数组。3. 遍历旧的entries数组中的所有有效键值对对每个键重新计算哈希值根据新的大小重新计算索引位置插入到新表中4. 释放旧的数组内存扩容的瞬间时间复杂度是O(n)。但由于这种操作不是每次插入都发生从长期来看每次插入的平均成本仍然是O(1)——这就是摊还分析的威力。6.3 为什么Python选择2/3作为阈值这是一个时间与空间的权衡阈值太高比如0.9空间利用率高但哈希冲突严重查找速度下降。阈值太低比如0.3冲突少、查找快但内存浪费严重。2/3是一个经过大量实践检验的平衡点既保证了较好的空间利用率又维持了接近O(1)的查找性能。七、字典的内存占用到底有多大7.1 一个空字典占多少内存python import sys empty_dict {} print(sys.getsizeof(empty_dict)) # 在64位Python上输出通常是72字节这72字节包含了PyDictObject结构本身以及预先分配的小型数组ma_smalltable8个槽位。7.2 随着元素增加内存如何增长字典的内存增长不是线性的而是阶梯式的——只有达到负载因子阈值时才会触发扩容每次扩容后容量翻倍。python import sys def dict_memory_usage(n): d {} for i in range(n): d[i] i return sys.getsizeof(d) for size in [0, 10, 50, 100, 500, 1000, 5000]: print(f{size}个元素: {dict_memory_usage(size)} 字节)7.3 紧凑字典的内存优势与Python 3.5及之前版本相比紧凑字典的内存占用减少了约20%-25%同时遍历速度提高了约10%-15%。这是因为1. entries数组连续紧凑没有空槽浪费2. indices数组可以根据字典大小选择最小的整数类型3. 更好的缓存局部性八、字典的性能优化与注意事项8.1 选择合适的键类型字符串是最快的键类型。Python对字符串哈希有专门优化而且字符串在解释器内部有驻留机制interning可以加速比较操作。python # 推荐用字符串作键 d[user_name] Alice # 可以但稍慢用元组作键 d[(user, name)] Alice # 避免用自定义对象作键除非必须 class User: def __init__(self, name): self.name name # 必须实现 __hash__ 和 __eq__8.2 预分配容量如果你事先知道字典要存储大量元素可以提前用某种方式预分配。虽然没有直接的reserve()方法但可以这样python # 方法1一次性创建足够大的字典 keys list(range(10000)) values [0] * 10000 d dict(zip(keys, values)) # 方法2让字典先扩容到目标大小 d {} for i in range(10000): d[i] None # 先填充占位 # 然后再替换实际值这可以避免多次扩容带来的重复开销。8.3 小心哈希攻击如果攻击者能控制字典的键并故意构造大量哈希值相同的键会导致所有键落入同一个槽位查找复杂度从O(1)退化到O(n)——这就是哈希冲突攻击或哈希洪水攻击。Python从3.3版本开始引入了哈希随机化机制每次启动解释器时使用随机种子来生成字符串的哈希值使得攻击者无法预测哈希冲突模式。8.4 字典 vs 其他映射类型类型适用场景优点缺点dict通用场景最快、最灵活内存占用相对较大defaultdict需要默认值代码简洁略慢于普通dictOrderedDict需要额外顺序操作支持move_to_end等Python 3.7 普通dict已有序Counter计数统计专门的API仅适用于计数场景types.MappingProxyType只读字典视图防止意外修改不能修改九、常见面试题问1Python字典的底层数据结构是什么答Python字典底层是哈希表但在Python 3.6之后采用了紧凑哈希表的设计。它由两个核心数组组成indices数组用于哈希索引查找entries数组按插入顺序紧凑存储键值对。这种设计既保证了O(1)的查找性能又实现了内存高效和插入有序。问2字典的键有什么要求答字典的键必须是可哈希的即键必须实现__hash__()和__eq__()方法并且在生命周期内哈希值保持不变。Python内置的不可变类型str、int、tuple等都是可哈希的而可变类型list、dict、set则不可哈希。自定义类的实例默认是可哈希的基于对象ID但如果重写了__eq__通常也需要重写__hash__来保持一致。问3字典的查找时间复杂度真的是O(1)吗答平均情况下是O(1)最坏情况下是O(n)。得益于好的哈希函数和冲突处理机制实际运行中绝大多数操作都是O(1)。但在极端情况下比如所有键的哈希值都相同查找会退化成线性扫描。不过Python有哈希随机化和自动扩容机制来避免这种情况。问4为什么Python 3.7的字典是有序的答因为紧凑哈希表的设计中entries数组是按插入顺序存储键值对的。遍历字典时实际上是线性扫描entries数组所以顺序自然就是插入顺序。这个特性从Python 3.6开始作为实现细节存在3.7正式成为语言规范。问5字典和列表哪个更快什么时候用字典什么时候用列表答如果需要通过键key来查找值字典更快O(1) vs 列表的O(n)如果需要通过位置index来访问列表更快直接内存偏移如果只是顺序存储数据列表更省内存。原则需要快速查找用字典需要顺序遍历用列表。