Python 的 dict 和 set 性能竟非 O(1)
Python sets and dictionaries can have quadratic-time performance
Python 开发者常认为 dict 和 set 是 O(1) 常数时间操作，但现实并非如此。Daniel Lemire 通过实验证明，当数据量增大或遭遇哈希碰撞时，这些结构可能退化为二次方时间复杂度。即便在理想情况下，随着数据从 CPU 缓存溢出到内存甚至磁盘，访问速度也会显著下降。文章还对比了 fastconstmap 库，展示在特定场景下，专用数据结构能比标准 dict 快出十倍。这提醒我们，理论模型虽有用，却不完全等同于现实，开发者需警惕认知偏差，关注实际性能表现。
说哈希表是 O(1) 或常数时间，只是一种模型；它可能成立，甚至经常成立，但这并非现实。
HN 评论区
63- amiga386
我怀疑这里面有猫腻。
import timeit
def test(M,n):
values = [i * M for i in range(1, n + 1)]
s = set(values)
sum(v in s for v in values)
M = (1 << 61) - 1
for n in [1000, 2000, 4000, 8000, 16000]:
print(f"M=2^61-1, {n=:5d} ->", timeit.timeit(lambda: test(M,n), number=3))
for n in [1000, 2000, 4000, 8000, 16000]:
print(f"M=1, {n=:5d} ->", timeit.timeit(lambda: test(1,n), number=3))
神奇的是，当你不再使用大整数（BIGINTS）作为集合成员，而改用普通整数时，这种二次方级的性能爆炸就消失了。
M=2^61-1, n= 1000 -> 0.13144792200182565
M=2^61-1, n= 2000 -> 0.48016051898594014
M=2^61-1, n= 4000 -> 2.058760045998497
M=2^61-1, n= 8000 -> 7.843778470996767
M=2^61-1, n=16000 -> 40.01485426299041
M=1, n= 1000 -> 0.000748768012272194
M=1, n= 2000 -> 0.0015750699967611581
M=1, n= 4000 -> 0.003037029004190117
M=1, n= 8000 -> 0.006664915999863297
M=1, n=16000 -> 0.012693285010755062
运行时间主要消耗在对大整数进行哈希、将候选大整数与参考大整数进行比较以及大整数求和上。此外还有一些集合查找操作。
- northisup
Raymond Hettinger 曾做过一场非常精彩的演讲，讲述了 Python 的 dict 在过去几年中取得了多大的进步。所以这篇文章非常有趣，最终很可能会让内置的 dict 变得更好。
这场演讲的启示是：如果你遵循语言惯用法，就能随着语言的进步而受益。
- juancn
这通常适用于所有常见的哈希表实现（当对象没有定义顺序时；如果有定义顺序，你可以获得 O(1) 的平均情况和 O(log N) 的最坏情况），无论使用什么语言。
O(1) 指的是预期的平均情况，这通常成立。
是的，O(N^2) 在理论上是可能的，但除非你正在防御某种拒绝服务攻击，否则在实践中这很少重要。
不过，如果你能估算出一个合理的哈希表初始大小，就可以避免大量重哈希带来的开销。
- brudgers
但我们能创建一个真正常数时间的哈希表吗？不能。随着你数据结构的增长，它需要访问越来越慢的内存。
在足够大以至于值得关注的规模下，一切都被 IO 主导。由于 IO 很慢，在任何值得关注的规模下，性能都取决于针对数据细节来定制实现 {0}。
工程是艰苦的工作，不是幼稚的数学。
[0] 数据可能是任意的，但绝非随机。正是“非随机”才使其成为数据。
- ok123456
大多数算法分析都没有纳入内存层次结构。我不确定这篇文章的重点是什么。
如果你真的对此感到担忧，那就计算一下你机器的经验屋顶线（empirical roofline）。
另外，如果重点是要指出内存层次结构的问题，那这就不是“二次方性能”。算法在溢出后行为并没有改变，只是成本变大了而已。