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 占位）。

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

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

下载

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

扩容与重哈希（resize）机制

当装载因子（used / size）超过阈值（默认 2/3），字典触发扩容：

• 新表大小取不小于原 size × 2 的最小 2 的幂（如 8→16，16→32）
• 所有有效键值对重新计算哈希、重新探测插入新表（rehash）
• 删除标记（-2）项在 resize 时被彻底丢弃，不进入新表
• 注意：popitem() 默认弹出最后插入项，依赖 entries 的顺序性，不是按哈希顺序

键的不可变性与哈希稳定性

字典能正确工作，根本前提是键对象的哈希值在其生命周期内不变：

• 字符串、数字、元组（仅含不可变元素）天然满足；列表、字典、集合等可变类型禁止作为键
• 若自定义类作键，必须正确定义 __hash__ 和 __eq__，且 __hash__ 返回值不能随实例状态改变
• 一旦键被修改导致哈希变化，原字典中将无法再通过该键查到对应值（表现为“丢失”，实为哈希定位错位）

理解这套机制，有助于写出更高效的字典操作代码，比如避免频繁增删导致反复 resize，或合理选择键类型防止哈希碰撞激增。它不是黑盒，而是一套精巧平衡了速度、内存与顺序语义的工程实现。