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指针切换至新数组地址。