Python字典查询为何快：哈希槽位、冲突与不可哈希键实

脚本专家

Python字典查询快的关键，不是它会从头找，而是它会先算。对键执行hash(key)，再按当前槽位数量取模，落到对应槽位；查找时同样算一次哈希，直接去目标槽位取数据。平均复杂度因此是O(1)，和字典里存了多少个键几乎无关。但这个结论有边界：键必须可哈希，冲突会让查找多探几步，最坏情况会退化；字典还会保留约三分之一空闲槽位。下面按原文的三个实验重组说明。

一、先建立定位直觉：dict不是线性表

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

复制代码

每个键进入字典时先算哈希，再按槽位数量取模。格子数远大于元素数时，常见路径是一步命中。这里说的一步是平均意义，不是最坏保证。

二、实验一：10万个键，dict和list差多少

2. import time
3. N = 100000
4. lst = list(range(N))
5. dct = {i: i for i in range(N)}
6. target = N - 1 # 查最后一个，list 的最坏情况
7. t0 = time.perf_counter()
8. _ = target in lst
9. t1 = time.perf_counter()
10. _ = target in dct
11. t2 = time.perf_counter()
12. print(f'list: {(t1-t0)*1000:.3f} ms')
13. print(f'dict: {(t2-t1)*1000:.3f} ms')

复制代码

原文给出的典型输出是：list要几百毫秒，dict只要几微秒，差2~3个数量级。把N再放大10倍，dict的时间几乎不变，list线性变长。复现时具体毫秒数会受机器影响，但趋势应一致。这个实验体现的就是哈希表平均O(1)的体感，也说明list做存在性检查在数据量大时会明显吃亏。

三、实验二：哈希冲突是常态，不是数据丢失
槽位总数通常比键少，冲突必然发生。CPython用开放寻址解决：目标槽位被占用就探测下一个空槽。原文用对8同余的键构造冲突场景：

2. keys = [i for i in range(64) if hash(i) % 8 == 0]
3. d = {k: k for k in keys}
4. print(len(d)) # 8 个键全在，查找依然正确

复制代码

这段代码说明冲突不会让键消失，字典仍能正确查找；代价是查找可能从一步变成探几步。如果键太集中，或者有人恶意构造碰撞键，dict就会退化成慢查找。也正因如此，PYTHONHASHSEED默认随机化，让攻击者算不出字符串哈希。这里的关键不是避免所有冲突，而是理解冲突处理会影响平均路径，安全场景还要考虑碰撞攻击。

四、实验三：list为什么不能做键

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

复制代码

翻车原因是list内容可变，内容一改哈希就可能变化，今天算出的槽位在A，明天值一改槽位算到B，字典就找不到它。Python要求键可哈希：hash()能算，并且对象生命周期内哈希不变，通常意味着不可变。tuple也不是无条件可哈希，只有元素全不可变时才可哈希；([1],)照样报错。排查这类错误时，先看键类型是否可变，再看容器内部元素是否可哈希。

五、两个反直觉点：保序和扩容
第一，Python 3.7+的dict保序是实现细节顺带带来的福利，不要把它当成业务逻辑依赖。第二，空dict并不会省下多少内存，装满才扩容；元素超过容量的2/3会触发扩容，扩容时重新哈希全部键，是一次性O(n)。扩容均摊下来仍是O(1)，所以预分配大字典没有太大意义。理解这一点，能避免把dict当数组做容量规划。

六、dict、set、list怎么选
查找：dict平均O(1)；set平均O(1)；list为O(n)。
键或元素要求：dict要求可哈希；set要求可哈希；list无要求。
存什么：dict存键→值；set存去重的键；list存有序序列。
内存：dict偏高，约三分之一空闲槽；set偏高；list紧凑。
典型场景：按key取值、做缓存、计数用dict；只问在不在、做去重用set；要顺序、要索引处理用list。
结论是：按key取值选dict；只做成员判断选set；需要顺序和索引选list。不要用list做大规模存在性检查，数据一上万就容易变成灾难。

以上内容基于原文的代码逻辑和实验结论改写。复现实验时建议直接运行原文代码，重点观察数量级差异和趋势，不要纠结单次耗时。

热心网友1

这篇总结挺清楚的，把“先算哈希再定位”这个核心讲明白了，也把冲突、可哈希、扩容这些边界条件串起来了。实验部分我最认同的是别盯着单次毫秒数，复现时多跑几轮取中位数，重点看list随N线性增长、dict基本稳定的趋势；list查最后一个确实是刻意放大的最坏情况，拿来对比很直观。实验二用对8同余构造冲突也挺适合观察“键不会丢，但路径会变长”，比抽象讲开放寻址好理解。可哈希那段的排查顺序很实用：先看键类型是否可变，再看容器内部元素是否可哈希，tuple也不是无条件能用。保序别当业务依赖、超过三分之二扩容、预分配大字典意义不大这几个提醒也很实在。最后的选型结论简洁：按key取值用dict，只判断存在或去重用set，要顺序和索引用list，大规模存在性检查别用list。整体是一篇适合新手建立直觉、也适合老手查漏的整理。

热心网友7

这篇整理得很清楚，把“dict 查询快是因为先算哈希再定位”这个核心讲明白了，而且没有停在平均 O(1) 的口号上，后面用冲突、可哈希、扩容和保序把边界也补齐了，读起来比较完整。几个实验的设计也挺直观：十万个键下 list 和 dict 的数量级差异、冲突场景下键不会丢、list 做键直接 TypeError，基本把常见误解都覆盖到了。 我个人觉得最实用的是最后 dict、set、list 的选择部分，尤其是“只做成员判断选 set，不要用 list 做大规模存在性检查”这一点，实际写脚本时很容易踩。复现实验时确实不用太纠结单次毫秒数，重点看趋势和数量级就对了；计时那块如果多次运行取个平均，结果会更稳一些。整体是一篇适合收藏回头查的科普加实践帖。

热心网友1

楼主这篇梳理得很系统，把“为什么快”和“什么时候不快”两头都讲到了，比只丢一句“哈希表O(1)”有用得多。我按自己的经历补几个小点，算是给复现实验的人提个醒。 实验一用单次 perf_counter 计时的话，微秒级的 dict 那一段很容易被调度抖动吃掉，甚至出现负数或数量级乱飘。稳妥点是用 timeit.repeat 跑几轮取最小值，或者把查询放进循环里跑十万次再平均，趋势会稳得多。另外 list 里查最后一个元素确实是最坏路径，如果改成查第一个元素，差距会缩到一两个数量级，这一点在解释给新手听的时候最好点明，否则容易被质疑“我试了没那么夸张”。 实验二那段我建议稍作说明：小整数的 hash 基本就是它本身，所以对 8 同余的键在“槽位恰好是 8”的假设下才会撞在一起；实际 CPython 里 8 个元素建 dict，底层表大小是 8 或 16，具体撞不撞跟实现细节有关，这段更适合当作“冲突会发生但仍能正确查找”的示意，别当成精确的碰撞复现。想让冲突真的发生，可以用重写了 __hash__ 返回常量的类来做，效果更直观，也顺带能演示最坏退化。另外 PYTHONHASHSEED 主要影响 str、bytes 这类，整数哈希不受它控制，这句可以稍微限定一下范围，免得读者以为所有键的哈希都被随机化了。 关于保序，我印象里 3.7 起已经写进语言规范了，不再是纯粹的“实现细节福利”，但