Python 字典为什么这么快?一次查找背后的哈希表、扰动函数和开放寻址

简介: Python 字典查找平均 O(1):算一次哈希直接跳到桶位,实测 1 万 key 取值 4.6ms,同规模列表成员判断要 55 秒,差 12000 倍;但哈希全碰撞时慢 2111 倍——用 4 组实验讲透开放寻址、扰动函数和空间换时间。

结论先行:Python 字典查找的平均耗时是 O(1),代价是哈希计算;本文实测 1 万个 key 的取值只要 4.6ms,而同样规模的列表成员判断要跑近 55 秒——差了约 12000 倍。但字典不是无条件快:一旦 key 的哈希值大面积撞桶,性能会断崖式下跌,本文构造全碰撞场景实测慢了 2111 倍。这篇用 4 组实验把「为什么快」和「什么时候不快」一次讲透。


1. 先看一组反常识的实验结果

import timeit, random
N = 1_000_000
d = {
   i: i for i in range(N)}
lst = list(range(N))
keys = [random.randrange(N) for _ in range(10000)]

# dict 取值
t_dict = timeit.timeit(lambda: [d[k] for k in keys], number=1)
# list 成员判断(只跑 200 个,否则跑不完)
t_list = timeit.timeit(lambda: [k in lst for k in keys[:200]], number=1)

实测结果:

操作 次数 耗时 折算每次
dict 取值 10000 次 4.6 ms 0.46 μs
list 成员判断 200 次 1099.8 ms 5.5 ms
list 成员判断(折算) 10000 次 约 55000 ms —

差了四个数量级。列表判断一次要扫半个表,100 万个元素的中位数就是 50 万次比较——55 秒这个数字听起来离谱,但它就是 O(n) 的本来面目。

字典的秘诀只有一句话:算一次哈希,直接跳到桶的位置。 中间的 49.9 万个元素,它一个都没看。

2. 桶里面是什么:开放寻址

CPython 的字典不是「桶里挂链表」(那是 Java HashMap 的做法),而是开放寻址:一张表,每个槽存一个 (hash, key, value) 三元组。

查找过程就三步:

1. h = hash(key)
2. 用 h 的低位定位起始槽位
3. 从该槽位开始线性探测,比对 hash 相等且 key 相等,命中

插入同理:找到第一个空槽放进去。所以哈希相等还不够,最终必须回到 == 比较——这解释了为什么不可哈希的对象(如 list)不能做 key:它连第一步都过不去。

3. 扰动函数:hash 值不能直接用

看一组真实 hash 值:

>>> hash(1)
1
>>> hash('a')
2161380871107616833

hash(1) = 1、hash(2) = 2、hash(3) = 3……如果直接拿小整数当槽位索引,连续整数键会把前 N 个槽位占满,后面的键全部撞在同一区域,开放寻址当场退化成线性扫描。

CPython 的解法是扰动函数:把 hash 值的高位混进低位,让分布更均匀。这也是为什么整数键和字符串键的查找速度有差距(本文实测:2000 个整数键 0.13ms,2000 个字符串键 0.20ms)——字符串要先算哈希,整数直接就是哈希。

4. 一张表看懂:dict / set / list 的定位差异

维度 dict set list
查找复杂度 平均 O(1) 平均 O(1) O(n)
靠什么定位 哈希 + 开放寻址 同 dict(只存 key) 顺序扫描 + ==
10000 次查找(实测) 4.6 ms 3.0 ms 约 55000 ms
key 要求 可哈希 可哈希 无要求
内存(10 万元素实测) 8.2 MB 约 8 MB 0.8 MB

set 和 dict 底层是同一套哈希表代码(set 就是「只有 key 的 dict」),所以二者速度同级。list 省内存但慢,dict 快但费内存——这是一笔明码标价的空间换时间。

5. 什么时候会翻车:全碰撞实测慢 2111 倍

字典的 O(1) 有个前提:哈希分布均匀。如果所有 key 撞进同一个桶,开放寻址就变成了「沿着槽位一个一个问」。

class Collide:
    def __init__(self, v): self.v = v
    def __hash__(self): return 42        # 全部撞同一个桶
    def __eq__(self, o): return isinstance(o, Collide) and self.v == o.v

cd = {
   Collide(i): i for i in range(2000)}

实测 2000 个 key:

场景 2000 次取值耗时
正常整数键 0.13 ms
哈希全为 42 的自定义对象 271.31 ms

慢 2111 倍,O(1) 直接变成 O(n)。 这不是 bug,是哈希表的本性——它赌的就是「哈希值足够散」。Web 框架被 hashDoS 攻击打穿过一轮之后,Python 给字符串哈希加了随机盐(每次进程启动 hash('a') 都可能不同),就是为了让攻击者算不出必撞的输入。

所以自定义 __hash__ 时,让它全返回常量是最省事也最危险的写法。

6. 实用结论

  1. 成员判断、去重、计数,永远优先 dict/set,不要用 in list——本文 12000 倍的差距就是日常代码里最大的性能分水岭之一。
  2. key 优先用字符串或整数:自带稳定的哈希,省一次计算。
  3. 自定义对象做 key,__hash__ 必须分布均匀,全常量等于主动放弃 O(1)。
  4. dict 费内存是设计使然:每个槽要存 hash、key、value 三份信息,10 万元素约 8MB,敏感场景可考虑 __slots__ 类或元组列表替代。

(全文完)

相关文章
|
4天前
|
Python
Python 的 yield from 到底转发了什么:拆开 send、throw 和那个 return 值
把生成器嵌套委托写对,关键是理解它转发的不止是产出值。本文用本机 CPython 3.13.14 实测 yield from 的 return 值透传、send/throw/close 三向内传、手写 for 循环为何丢掉 StopIteration.value、3.11 起已被移除的 YIELD_FROM 指令与 3.13 的 SEND/END_SEND 组合、PEP 479 的 RuntimeError,并给出与手写循环的八项对照表和七条排错清单
|
19天前
|
缓存 Java Python
Python 的 int 为什么不会溢出?拆开 PyLongObject 和它背后那串变长数组
很多人背过“字典查询是 O(1)”,但为什么是常数?CPython 3.13 实测 dict.get 在 100→10 万规模恒为 0.1 微秒,而 list.index 线性涨到 609 微秒(慢 4743 倍)。本文拆开开放寻址哈希表、扰动函数与 2/3 扩容阈值把 O(1) 钉死,也讲清“创建是 O(n)”这个常被混的点。
|
22天前
|
缓存 编译器 Sentinel
Python 里 is 和 == 到底差在哪?拆开小整数池、字符串驻留与 0ns 身份比较
is 比 == 快不是 Python 偷懒,而是它只比对象身份(指针),0ns 级别;== 要走 __eq__ 还可能触发哈希。但小整数池和字符串驻留会让 is 在「本不该相等」时也返回 True,这是 80% 初学者踩的坑。
|
30天前
|
存储 缓存 编译器
Python 的整数为什么永远不会溢出?拆开大整数对象,看 30 位一节的存储与运算代价
Python 整数不会溢出,靠的是把数字拆成 30 位小节用对象数组存:每个整数至少 28 字节,每多 30 位加 4 字节;加法近似线性、乘法超线性——30 万位乘法是 30 位的 29 万倍;str 转换默认 4300 位护栏,to_bytes 比 str 快约 300 倍。用 9 组实验算清「无限精度」的账单。
|
1月前
|
Python
Python 迭代器和生成器到底啥区别?3 个例子讲透,别再背概念了
迭代器和生成器不是并列关系——生成器是迭代器的一种“偷懒写法”。3 个例子讲透:迭代器是“会挨个吐值的对象”,生成器是用 yield 现写现用的那种,最大区别是它懒,要一个才生一个。
|
1月前
|
Python
Python 装饰器到底是个啥?从 @ 符号到手写一个,5 个例子讲透
装饰器(decorator)本质是一个「接收函数、返回函数」的高阶函数,@log 写在 def foo() 上等价于 foo = log(foo)。本文从最朴素的包装工厂讲起,用 5 个例子把 @ 语法、functools.wraps、带参数装饰器、类装饰器一次讲透。
|
1月前
|
缓存 Python
Python 装饰器把函数"搞丢"了?5 个必踩的坑与完整避坑对照表
装饰器的坑不是"不会写",而是写完原函数被悄悄换掉——名字、文档、签名、身份都可能变。functools.wraps 救得回大部分,救不了全部。5 个坑逐个给复现代码和修法,附完整对照表。
|
1月前
|
Linux iOS开发 Python
Python 虚拟环境到底怎么选?venv / conda / pipenv / poetry 一张对比表 + 9 个真实踩坑
venv、conda、pipenv、poetry 到底怎么选?本文用一张对比表 + 9 个真实踩坑讲清楚:什么时候 venv 就够了、什么时候必须上 poetry、conda 真正解决的是什么问题,以及虚拟环境里最常见的路径与依赖冲突该怎么排查。
|
3天前
|
缓存 安全 Python
Python 的 isinstance 到底查了什么:拆开 __instancecheck__、ABC 缓存和 type 的区别
把类型判断写对,关键是理解 isinstance 会「问类的意见」而不是自己翻 MRO。本文用本机 CPython 3.13.14 实测 metaclass 上重写 __instancecheck__ 才生效、ABCMeta.register 的虚拟子类不进 __mro__、__subclasshook__ 只看方法存在性、伪造 __class__ 能改变 isinstance 结果、普通类与 ABC 路径 20 万次耗时差 4.4 倍,附对照表与七条排错清单
|
8月前
|
人工智能 Linux API
OpenClaw全自动小红书运营实战:从0到1全流程部署、技能配置与内容自动化发布指南
在内容自动化运营场景中,OpenClaw(Clawdbot)凭借高度可扩展的Skill体系与多任务执行能力,可实现从热点追踪、文案创作、封面生成到笔记发布、互动管理的全流程自动化。本文基于2026年最新环境,完整讲解如何通过阿里云轻量服务器或本地Windows11/macOS/Linux部署OpenClaw,安装并配置小红书运营Skill,完成Cookie登录、内容生成、笔记发布、数据监控,并接入阿里云百炼Coding Plan免费大模型与QMD记忆优化系统,实现低成本、7×24小时无人值守小红书运营。全文无营销词汇,所有命令可直接复制,零基础用户也能快速跑通全流程。
3589 9

热门文章

最新文章