Python虚拟机中字典本质上是一个开放寻址哈希表，CPython用indices稀疏索引加entries紧凑存储，查询平均O(1)，3.7以后还保证插入顺序。 下面从底层结构、查找流程、扩容机制、面试场景和内存优化几个角度，把Python字典实现拆开讲清楚。
Python字典底层实现原理是什么？
PyDictObject里有什么
在CPython虚拟机里,一个dict对象对应PyDictObject，核心字段不多：
ma_used：当前键值对数量。ma_keys：指向PyDictKeysObject，真正存放索引和条目。ma_values：普通dict通常为NULL；分离表结构下，实例属性可能把值放在这里。
PyDictKeysObject才是字典的“骨架”，它包含：
dk_indices：稀疏索引数组，每个槽位存的是entry下标加1。dk_entries：紧凑条目数组，按插入顺序连续存放hash、key、value。dk_usable：还能插入多少个元素，接近0时会触发扩容。dk_nentries：已使用的entry数量。
紧凑字典为什么省内存
老式哈希表把key和value直接放在桶里,空桶也要占位，CPython 3.6开始采用紧凑字典，把“索引”和“条目”拆开。
indices数组只存整数，空槽位是0，删除槽位是-1。entries数组只追加有效条目，不浪费空桶。- 遍历字典时直接走
entries，顺序就是插入顺序。
据Python官方文档,3.7起字典插入顺序成为语言规范，这不是排序，只是插入顺序。
查找与插入流程
插入或查询一个键,大致走这几步：
- 调用
hash(key)得到哈希值。 - 用
hash & mask算出indices下标。 - 看
indices[i]：- 0表示空,键不存在。
- -1表示dummy，继续探测。
- 其他值表示entry下标加1。
- 取出对应entry,比较哈希和键是否相等。
- 冲突时用伪随机探测,直到找到空位或dummy位。
插入新键时,entry追加到dk_entries末尾，然后indices指向它，删除键时，entry的key和value置空，indices标成dummy，ma_used减一，dummy不会立刻消失，后续插入可以复用。
CPython字典和哈希表有什么区别？
普通哈希表与CPython的差异
| 对比项 | 普通开放寻址哈希表 | CPython字典 |
|---|---|---|
| 存储方式 | 桶里直接放key/value | indices和entries分离 |
| 空桶浪费 | 较大 | entries紧凑，浪费少 |
| 遍历顺序 | 通常无序 | 7+插入有序 |
| 删除处理 | 墓碑标记 | dummy索引，entry可复用 |
| 哈希计算 | 每次可能重算 | entry缓存哈希值 |
业内专家指出,CPython的紧凑字典是内存和速度折中的经典案例，它没有改变哈希表本质，但把稀疏索引和连续条目组合起来，兼顾了查找和遍历。
为什么这种设计快
indices数组小，容易放进CPU缓存。entries连续，遍历时缓存命中率高。- 哈希值缓存在entry里,比较键时不用反复调用
__hash__。 - 开放寻址没有链表指针跳转,冲突少时速度很稳。
行业共识认为,字典平均O(1)的前提是哈希分布均匀且负载因子受控，如果大量键哈希冲突，最坏会退到O(n)。
Python字典扩容机制是怎么触发的？
触发条件
扩容通常发生在插入新键时,当dk_usable耗尽，或者可用槽位不足，CPython就会调用dictresize。
负载因子接近约三分之二时,哈希冲突概率明显上升，所以字典不会等到完全填满才扩容。
扩容做了什么
扩容不是简单把数组加大,而是一次重建：
- 申请更大的
indices数组，大小通常取2的幂。 - 根据当前
used估算新容量，元素少时扩容倍数大，元素多时倍数收窄。 - 遍历旧
entries，重新计算每个键的索引。 - 把有效条目写进新表,dummy被清理。
- 更新
dk_usable、dk_nentries等字段。
可以用两行命令观察字典大小变化：
import sys
d = {}
print(sys.getsizeof(d))
d.update({i: i for i in range(10)})
print(sys.getsizeof(d))
sys.getsizeof只算字典对象本身，不含键和值对象，想看整体内存，用tracemalloc：
import tracemalloc
tracemalloc.start()
d = {i: i for i in range(100000)}
print(tracemalloc.get_traced_memory())
面试场景下Python字典如何实现？大厂常问点拆解
为什么查询平均O(1)
哈希直接定位索引,冲突少时一次比较就能命中，字典把哈希值缓存在entry里，比较键时先比哈希，再比键对象，减少昂贵操作。
最坏O(n)出现在大量哈希冲突时，比如所有键哈希值相同，探测会退化成线性扫描。
为什么字典键必须可哈希
可哈希要求对象实现__hash__和__eq__，并且哈希值在生命周期内不变。
- list不可哈希,因为可变。
- tuple内所有元素可哈希时,tuple才可哈希。
- 自定义对象默认按id哈希,如果重写
__eq__，通常也要重写__hash__。
有序性怎么来的
7以后,字典保证插入顺序，实现上靠entries数组追加：
- 新键加到
dk_entries末尾。 - 删除键不移动其他entry。
- 删除后再插入同一个键,它会出现在末尾。
所以字典的有序是插入顺序,不是按key排序。
Python字典内存优化场景：从10万条数据说起
观测工具与操作路径
国内开发者常在生产环境里关心字典内存,先量再优：
sys.getsizeof(d)：看字典对象本身。tracemalloc：看整体分配峰值。pympler.asizeof：第三方工具，可看深层大小。
命令示例：
python -c "import sys; d={i:i for i in range(100000)}; print(sys.getsizeof(d))"
python -c "import tracemalloc; tracemalloc.start(); d={i:i for i in range(100000)}; print(tracemalloc.get_traced_memory())"
优化手段
- 实例属性多时用
__slots__，避免每个实例都带一个字典。 - 数据类可用
dataclass(slots=True)。 - 大字典尽量统一键类型,减少哈希和比较开销。
- 删除大量键后,如果dummy过多，可以重建：
d = dict(d)。 - 只查不改的场景,考虑
frozenset或数组结构。
系统学习Python字典底层实现,培训班价格从几百到上千不等，但核心逻辑完全可以用源码和上述命令自己验证。
Python虚拟机中字典实现常见问题Q&A
Python字典是有序的吗？
7及以后,字典保证插入顺序，3.6的CPython实现也有序，但当时还没写进语言规范，删除再插入的键会排到末尾。
为什么不能用list做字典键？
list是可变对象,没有稳定的哈希值，哈希表依赖哈希值定位，如果键变了，查找就会失效，可以用tuple或frozenset代替。
删除键后内存会立刻下降吗？
通常不会,删除键只是把indices标成dummy，把entry的key和value置空，ma_used减少，真正释放内存要等扩容或重建字典，可以执行d = dict(d)触发一次重建，清理dummy和无效条目。
Python字典的快来自哈希定位、紧凑entries和动态扩容的配合；3.7以后的有序只是插入顺序，不是排序。 理解这套结构，面试和性能优化都会更有底。