Python字典是基于开放寻址法和动态哈希表实现的高效结构，平均时间复杂度O(1)，依赖哈希函数、冲突处理与内存布局；键须不可变并实现__hash__和__eq__；采用扰动探测解决冲突；负载超2/3时扩容，删除不缩容但空槽过多时可能缩容。
Python字典（dict）不是简单的键值对容器，而是一个基于开放寻址法（open addressing）和动态哈希表（hash table）实现的高效数据结构。它的平均时间复杂度为 O(1) 的查找、插入和删除，核心依赖于哈希函数、冲突处理机制与内存布局设计。
哈希计算与索引映射
当向字典插入一个键（key）时，Python 首先调用该对象的 __hash__() 方法获取一个整数哈希值（必须是不可变类型，否则抛出 TypeError）。这个哈希值会被映射到哈希表的一个具体槽位（bucket）上：
- 实际索引 =
hash(key) & (table_size - 1)（前提是table_size是 2 的幂，便于位运算优化） - 该设计避免了取模（
%）运算开销，提升性能 - 若键是自定义类，需同时实现
__hash__和__eq__，否则可能引发逻辑错误或哈希冲突误判
开放寻址与探测序列
Python 不使用链地址法（如 Java HashMap 的拉链），而是采用开放寻址 + 伪随机探测（perturb-based probing）来解决哈希冲突：
- 当目标槽位已被占用，解释器会按特定规则“跳转”到下一个候选位置，直到找到空槽或匹配键
- 探测公式为：
j = ((5*j) + 1) + perturb，其中perturb初始为hash >> 5，每次迭代右移 5 位 - 这种扰动策略能有效打散聚集，降低长探测链概率，比线性/二次探测更均匀
动态扩容与空间利用率控制
字典在插入过程中持续监控负载因子（used / size）。一旦超过阈值（CPython 中为 2/3），就会触发扩容：
立即学习“Python免费学习笔记（深入）”；
- 新表大小为原大小的 2–4 倍（取决于当前容量，小表翻倍，大表略激进）
- 所有已有键值对被重新哈希、插入新表，带来一次性开销（但摊还后仍为 O(1)）
- 删除操作不立即缩容，但若空槽过多（
fill / size ），后续插入可能触发缩容 - 可通过
sys.getsizeof(d)查看当前内存占用，观察扩容前后变化
性能关键点与实用建议
理解底层有助于写出更高效的字典操作代码：
- 优先使用内置不可变类型（
str,int,tuple）作键，它们的哈希计算快且稳定 - 避免频繁增删导致反复扩容缩容；若已知大致规模，可用
dict.fromkeys(keys, default)或预分配（虽无直接 API，但可先批量插入占位） - 大量只读场景下，考虑
types.MappingProxyType封装，获得不可变视图，减少意外修改开销 - 调试哈希行为？可打印
hash(x)和id(x)对比，注意字符串等小对象存在驻留（interning）影响哈希一致性
