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字段表示当前可用于插入的空槽数量，用于触发扩容阈值判断。
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指针切换至新数组地址。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
