python字典底层基于哈希表实现，采用紧凑存储（3.6+）、开放寻址与动态扩容机制，要求键不可变且哈希稳定，以保障查找高效、插入有序、内存节约。
Python字典（dict）的底层是基于哈希表（hash table）实现的，其核心结构体在 CPython 源码中叫 PyDictObject，内部维护一个名为 ma_keys 的指针（指向 PyDictKeysObject），而真正存储键值对数据的连续内存块，就是常说的“索引数组 + 哈希表项数组”组合结构——常被简称为 _dict 结构。它不是单一数组，而是通过哈希函数、开放寻址（open addressing）和紧凑存储协同工作的动态哈希表。
哈希计算与索引定位
每次插入或查找键时，Python 先调用该键对象的 __hash__() 方法得到一个整数哈希值（必须不可变），再通过位运算快速映射到表内索引：
- 实际索引 =
hash & (mask)，其中mask = table_size - 1（要求表长恒为 2 的幂，保证位与高效） - 若发生冲突（即目标槽位已被占用），则按固定探测序列（如线性探测的变种：
i = (5*i) + 1 + perturb）寻找下一个空闲位置 -
perturb是从原始 hash 持续右移取低比特参与扰动，避免聚集，提升分布均匀性
紧凑存储结构（compact dict，3.6+ 默认）
CPython 3.6 开始，字典改为“插入有序 + 内存紧凑”设计，底层由两部分组成：
-
索引数组（indices）：长度等于哈希表容量，每个元素是带符号整数，值为
-1（空）、-2（已删除）、或指向 entries 数组的非负下标 - entries 数组（dk_entries）：真实键值对线性排列，顺序与插入顺序严格一致，无空洞
这种分离让迭代性能大幅提升（遍历 entries 即可），且节省内存（旧版稀疏哈希表常有大量 NULL 占位）。
立即学习“Python免费学习笔记（深入）”；
扩容与重哈希（resize）机制
当装载因子（used / size）超过阈值（默认 2/3），字典触发扩容：
- 新表大小取不小于原 size × 2 的最小 2 的幂（如 8→16，16→32）
- 所有有效键值对重新计算哈希、重新探测插入新表（rehash）
- 删除标记（
-2）项在 resize 时被彻底丢弃，不进入新表 - 注意：
popitem()默认弹出最后插入项，依赖 entries 的顺序性，不是按哈希顺序
键的不可变性与哈希稳定性
字典能正确工作，根本前提是键对象的哈希值在其生命周期内不变：
- 字符串、数字、元组（仅含不可变元素）天然满足；列表、字典、集合等可变类型禁止作为键
- 若自定义类作键，必须正确定义
__hash__和__eq__，且__hash__返回值不能随实例状态改变 - 一旦键被修改导致哈希变化，原字典中将无法再通过该键查到对应值（表现为“丢失”，实为哈希定位错位）
理解这套机制，有助于写出更高效的字典操作代码，比如避免频繁增删导致反复 resize，或合理选择键类型防止哈希碰撞激增。它不是黑盒，而是一套精巧平衡了速度、内存与顺序语义的工程实现。
