Python字典底层是优化的哈希表，通过哈希函数+位运算定位索引，用开放寻址法处理冲突，负载超2/3时扩容至≥4倍的2的幂，CPython 3.6+采用分离式结构保障插入顺序与缓存友好。

Python字典的底层结构是哈希表（Hash Table），它不是简单的数组或链表，而是一套经过高度优化的动态散列系统，核心目标是让查找、插入、删除操作在平均情况下稳定在O(1)时间复杂度。

哈希表怎么把键变成位置

字典靠哈希函数把任意类型的键（如字符串、数字、元组）转换成一个整数——即哈希值；再用这个值对当前哈希桶数组长度取模，得到存储或查找的索引位置。比如桶数组长8，键"hello"算出哈希值为103，则103 % 8 = 7，就存到索引7的位置。

• 哈希函数必须确定：同一键每次调用hash()都返回相同值（不可变类型才允许做键）
• 取模运算保证结果落在合法索引范围内
• 实际实现中不直接用%，而是用位运算（如& (n-1)），要求桶数组长度始终是2的幂，提升效率

冲突发生时怎么处理

不同键可能算出相同哈希值（比如"apple"和"orange"在某些简单哈希下都落桶0），这就叫哈希冲突。Python不用拉链法（不建链表），而是采用开放寻址 + 伪随机探测：

macOS UI 自动化技能包 —— 用 Python 控制你的 Mac

让 macOS 自动化像说话一样简单 —— 用代码控制你的 Mac，无需学习 AppleScript 系统要求 macOS 14+ (Sonoma) Python 3.9+ 需要开启：辅助功能 + 屏幕录制权限

下载

• 初始位置冲突后，按固定公式跳转下一个试探位置：i = (i * 5 + perturb) & mask
• perturb是初始哈希值右移后的扰动项，避免探测路径重复
• 一直试到找到空槽，或命中已存在的相同键

字典怎么自动变大变小

哈希表不能一直塞满，否则冲突概率飙升，性能急剧下降。Python设定了严格扩容阈值：

立即学习“Python免费学习笔记（深入）”；

• 当已用槽位数 ≥ 总槽数 × 2/3 时，触发扩容
• 新容量选最小的、≥ 当前所需槽数×4 的 2 的幂（例如从8→32，而非8→16）
• 扩容后所有键值对要重新计算哈希、重新散列，是个耗时操作，所以应避免频繁增删导致反复扩容

键值对实际存在哪儿

现代CPython（3.6+）使用“分离式哈希表”结构：

• ma_keys 指向一个紧凑的键数组（含哈希值、键引用）
• ma_values 是二级指针，指向值对象数组（仅在有值需单独管理时启用）
• 这种设计让迭代顺序与插入顺序一致（即保持有序），且内存更局部化，缓存友好