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 评论区
22- northisup
Raymond Hettinger 有一场非常精彩的演讲，讲述了 Python 的 dict 多年来是如何不断进化的。所以这篇帖子超级有趣，最终很可能会让内置的 dict 变得更好。
这场演讲的启示是：如果你遵循语言惯用法，就能随着语言的进步而受益。
- juancn
这通常适用于所有常见的哈希表实现（当对象没有定义顺序时；如果定义了顺序，你可以获得 O(1) 的平均情况和 O(log N) 的最坏情况），与语言无关。
O(1) 指的是预期的平均情况，而这通常成立。
没错，O(N^2) 在理论上是可能的，但除非你正在防御某种拒绝服务攻击，否则在实践中这很少重要。
不过，如果你能预估一个合理的哈希表初始大小，就可以避免很多重新哈希带来的开销。
- aadyachinubhai
这就是为什么我在定义类时喜欢使用 __slots__。与 dict 不同，__slots__ 是一个元组，所以用它来存储类属性要快得多。