Python字典底层实现_dict哈希结构解析

Python字典底层基于动态哈希表，采用开放寻址法与稀疏数组实现高效查找；通过dk_size、dk_usable、dk_nentries管理容量与状态；键哈希经位运算映射索引；冲突时用扰动线性探查；删除置DKIX_DUMMY标记以复用空间；超阈值触发2倍扩容与重哈希。Python字典的底层实现依赖于一个动态调整大小的哈希表结构，其核心是名为_dict的C语言结构体。该结构通过开放寻址法处理哈希冲突，并采用稀疏数组与探查序列协同工作以维持高效查找。以下是对其哈希结构关键组件的逐层解析：一、哈希表内存布局与核心字段每个字典对象在C层对应一个PyDictObject结构，其中包含指向PyDictKeysObject的指针，后者封装了哈希表的实际存储区域。该结构维护dk_indices数组（存储索引偏移）和可选的dk_entries数组（存储键值对），二者共同构成稀疏哈希表。1、dk_size字段记录当前哈希表的总槽数（必须为2的幂次）。2、dk_usable字段表示当前可用于插入的空槽数量，用于触发扩容阈值判断。立即学习“Python免费学习笔记（深入）”；3、dk_nentries字段精确统计已插入的有效键值对数量，不计入伪删除标记。二、键哈希计算与索引映射机制Python对任意键对象调用PyObject_Hash()获取64位哈希值，随后截取低log2(dk_size)位作为初始桶索引。该设计确保索引落在合法范围内，且利用位运算替代取模提升性能。1、字符串键使用SipHash算法生成哈希值，抵抗哈希碰撞攻击。2、整数键的哈希值为其自身（负数经掩码处理后保持唯一性）。3、若键类型未定义__hash__方法或返回NotImplemented，则抛出TypeError。三、开放寻址与探查序列生成当目标桶已被占用时，字典不采用链地址法，而是执行线性探查变体：以初始索引为起点，按固定步长递增偏移，直至找到空槽或命中已存在键。探查步长由哈希值高位参与计算，降低聚集概率。1、首次探查位置为hash & (dk_size - 1)。2、后续位置按(index + perturb) & (dk_size - 1)迭代，其中perturb每次右移5位并与原哈希异或更新。3、探查终止条件为遇到空槽（DKIX_EMPTY）或匹配键对象（通过PyObject_RichCompareBool验证相等性）。四、伪删除标记与空间复用策略删除操作不真正清空槽位，而是写入DKIX_DUMMY标记。该标记在查找时被跳过，但在插入时可被复用，避免因连续删除导致探查链断裂。此机制保障了哈希表在频繁增删场景下的稳定性。1、执行del d[key]时，定位键所在槽位并置为DKIX_DUMMY。2、插入新键值对时，探查过程将DKIX_DUMMY视为可用位置优先填充。3、当dk_usable降至阈值以下（通常为总槽数的1/3），触发重哈希重建整个表。五、动态扩容与重哈希流程当有效条目数超过槽数的2/3时，字典启动扩容。新表大小设为原大小的2倍（最小为8），所有现存键值对依据新尺寸重新计算哈希索引并插入，伪删除标记在此过程中被彻底清除。1、分配新dk_indices数组，长度为原值两倍且为2的幂。2、遍历旧表中所有非空且非伪删除的条目，调用新哈希函数计算位置。3、将键值对按新索引顺序写入dk_entries，同步更新dk_indices指向关系。4、释放旧内存块，将dk_indices指针切换至新数组地址。