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）影响哈希一致性