Python 字典为什么查得快？3 个实验看懂哈希表底层

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

Python 字典为什么查得快？3 个实验看懂哈希表底层，别再只会 type() 了

系列：Python 底层设计逻辑｜类型：原理拆解型｜分发：CSDN / 博客园 / 腾讯云
字数：约 1600 字

结论先行：dict 查得快，不是因为它"会找"，而是因为它"会算"——用键的哈希值直接算出该去哪个槽位拿数据，理论上一步到位，和字典里存了多少个键几乎无关。但这份快是有代价的：键必须可哈希、查找实际是 O(1) 平均而非最坏、还白放着约三分之一的内存。这三个坑，用三个实验看清楚。

1. 先建立直觉：dict 不是"表"，是"带传送门的格子间"

列表查一个值，得从第 0 个开始比，最坏翻到底——O(n)。字典不干这事：

d = {'name': '张三', 'age': 18}
d['age'] # 不是遍历，是 hash('age') → 算出槽位 → 直接取

每个键进来，先算 hash(key)，再按槽位数量取模，落进对应的格子。查找同理：算一次哈希，去对应格子拿。格子数远大于元素数时，一步就中。

2. 实验一：10 万个键，dict 和 list 差多少

import time

N = 100000
lst = list(range(N))
dct = {i: i for i in range(N)}
target = N – 1 # 查最后一个，list 的最坏情况

t0 = time.perf_counter()
_ = target in lst
t1 = time.perf_counter()
_ = target in dct
t2 = time.perf_counter()

print(f'list: {(t1–t0)*1000:.3f} ms')
print(f'dict: {(t2–t1)*1000:.3f} ms')

典型输出：list 要几百毫秒，dict 只要几微秒——差 2~3 个数量级。把 N 再放大 10 倍，dict 的时间几乎不变，list 线性变长。 这一条就是"哈希表 O(1)"的体感。

3. 实验二：哈希冲突是常态，不是事故

槽位总比键少，冲突必然发生。CPython 用开放寻址（探测下一个空槽）解决：

# 构造一批"爱打架"的键：哈希值对 8 同余
keys = [i for i in range(64) if hash(i) % 8 == 0]
d = {k: k for k in keys}
print(len(d)) # 8 个键全在，查找依然正确

为什么重要：冲突不丢数据，但会让查找从"一步"变成"探几步"。键太集中（或有人恶意构造碰撞键）时，dict 会退化成慢查找——这也是为什么 PYTHONHASHSEED 默认随机化：让攻击者算不出你的字符串哈希。

4. 实验三：为什么 list 不能做键

d = {}
d[[1, 2]] = 'x' # TypeError: unhashable type: 'list'
d[(1, 2)] = 'x' # tuple 可以
print(d) # {(1, 2): 'x'}

为什么翻车：list 内容能改，改了哈希就变了——今天算出的槽位在 A，明天值一改槽位算到 B，字典就永远找不到它了。所以 Python 要求键可哈希：hash() 能算、且对象生命周期内哈希不变（不可变）。tuple 元素全不可变时才可哈希：([1],) 照样报错。

5. 两个反直觉点

① dict 有序且"记性"在键上：Python 3.7+ dict 保序，但这是实现细节顺带的福利，别依赖它做业务逻辑。

② 空 dict 不省多少，装满才扩容：dict 元素超过容量的 2/3 会触发扩容（重新哈希全部键，一次性 O(n)）。所以预分配大字典没有意义——扩容均摊下来仍是 O(1)。

6. dict vs set vs list（选型对照）

对照结论：按 key 取值 → dict；只问"在不在" → set；要顺序、要索引 → list。别用 list 做"存在性检查"，数据一上万就是灾难。

下一篇预告见创作页，关注不迷路。