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不用拉链法（不建链表），而是采用开放寻址 + 伪随机探测：
- 初始位置冲突后，按固定公式跳转下一个试探位置：
i = (i * 5 + perturb) & mask -
perturb是初始哈希值右移后的扰动项，避免探测路径重复 - 一直试到找到空槽，或命中已存在的相同键
字典怎么自动变大变小
哈希表不能一直塞满，否则冲突概率飙升，性能急剧下降。Python设定了严格扩容阈值：
立即学习“Python免费学习笔记（深入）”；
- 当已用槽位数 ≥ 总槽数 × 2/3 时，触发扩容
- 新容量选最小的、≥ 当前所需槽数×4 的 2 的幂（例如从8→32，而非8→16）
- 扩容后所有键值对要重新计算哈希、重新散列，是个耗时操作，所以应避免频繁增删导致反复扩容
键值对实际存在哪儿
现代CPython（3.6+）使用“分离式哈希表”结构：
-
ma_keys指向一个紧凑的键数组（含哈希值、键引用） -
ma_values是二级指针，指向值对象数组（仅在有值需单独管理时启用） - 这种设计让迭代顺序与插入顺序一致（即保持有序），且内存更局部化，缓存友好
