Python中的集合和字典可能具有二次方时间性能

# Python集合与字典可能存在二次时间性能 来源：https://lemire.me/blog/2026/09/03/python-sets-and-dictionaries-can-have-quadratic-time-performance/ 在Python中，`dict`数据结构是标准的键值结构。例如，你可以将姓名列表存储为键，将对应的电话号码存储为值。Valentin Ignatev在X平台上发表了一篇有趣的帖子： [](https://lemire.me/blog/wp-content/uploads/2026/09/xpost.webp) 人们普遍认为，严格来说，`dict`数据结构及其配套的集合数据结构是O(1)的，这意味着随着数据结构规模的增大，插入或查询键值所需的时间保持不变。 让我们来检验一下这个说法。 哈希函数是一种将对象（如字符串、整数等）映射为整数值的函数。我们通常期望哈希函数表现得像随机函数，尽管它在当前程序执行中必须始终将同一对象映射到相同的整数。基于哈希函数，我们构建哈希表： 1. 创建一个桶数组。 2. 给定一个对象，应用哈希函数将其映射到一个桶。 3. 将对象存储在该桶中。当桶已被占用时，使用其他技巧（例如使用附近的桶）。 如果一切顺利，哈希表中的访问和插入操作几乎都是常数时间完成的，这意味着它们所花费的时间与哈希表的大小无关。 这在许多情况下可能近乎真实。然而，从形式上讲并非如此。有许多理由可以说明这个结论是错误的。例如，如果你的数据结构增长，可能需要重新分配内存，这通常需要与数据结构大小成比例的时间。但我们还面临碰撞问题。当两个对象具有相同的哈希值时，就会发生碰撞。使用哈希表时，我们假设碰撞并不常见。但通过精心选择对象，制造大量碰撞并不困难。 在Python中，`set`和`dict`都是哈希表。我可以“轻松”地让我的Python版本崩溃： `` M = (1 << 61) - 1 values = [i * M for i in range(1, n + 1)] s = set(values) # 插入操作 count = sum(v in s for v in values) # 检查操作 `` 如果插入和检查都是常数时间操作，那么整个构建和检查过程应该需要线性时间。我在Apple M4 Max上使用Python 3.14运行了此代码，报告了三次运行的中位数。 n 时间 1000 4.8 ms 2000 15.5 ms 4000 65.5 ms 8000 257 ms 16000 1072 ms 每次*n*翻倍，时间大约翻四倍。这是二次时间，而非线性时间。成员检查的行为也类似：当*n* = 16000时，耗时1066毫秒。当元素数量达到十万时，构建集合需要45秒。 但是，我们能创建一个真正常数时间的哈希表吗？不能。随着数据结构大小的增长，它需要访问逐渐变慢的内存。如果你有一个小哈希表，它可以驻留在CPU缓存中，速度很快。当它达到MB级别时，数据结构往往存储在RAM中，速度就慢得多。最终，你必须将其存储在磁盘上，速度更慢。依此类推。 换句话说，说哈希表是O(1)或常数时间，这是一种模型。它可能是真实的，甚至常常如此，但这并非现实。模型是极好的教学工具：它们呈现了一个你可以快速掌握的简化模型。但模型也会在我们的思维方式中引入偏见。 例如，即使你已经读过我关于dict数据结构变慢的段落，你可能仍然不相信。你也可能相信它通常是你能使用的最快方法。 让我们考虑另一个实际案例。假设你有一个从字符串到整数的大映射，它只构建一次然后只被查询。这是常见情况：单词到标识符的字典、国家代码查找表、特征名称表。 fastconstmap (https://pypi.org/project/fastconstmap/) 库可以从 `dict[str, int]` 构建一个不可变的映射。当你的键是预先已知时，它非常适用。 我构建了一个从一百万个随机16字符字符串到整数的映射，然后以打乱的顺序查找每个键。使用`dict`时，我编写了显而易见的循环： `` total = 0 for k in probes: total += d[k] `` 使用fastconstmap时，我一次性请求所有键，将值写入我拥有的缓冲区，这样每个键都不会分配Python对象： `` out = array("Q", bytes(8 * n)) cm.get_many_into(probes, out) `` 我对`dict`很宽容。我在查找中重用了相同的字符串对象，而Python字符串在第一次计算时会缓存其哈希值。因此，`dict`根本不需要支付哈希计算的代价，而fastconstmap每次都会对每个键进行哈希计算。以下是结果，以每个键的纳秒为单位。 n dict get\_many\_into 1000 21.8 4.3 10000 31.9 4.8 100000 48.1 5.2 1000000 201.9 11.8 `dict`并非常数时间。随着映射增长，每个键的耗时从22纳秒增加到202纳秒，增加了9倍，这并非因为算法改变或碰撞。这是因为一百万个键、它们的字符串对象和整数对象每个键大约占用116字节，因此查找操作无法命中缓存。fastconstmap版本每个键只需要9字节：它能在缓存中保留更长时间。请注意数字如何变化：随着规模增长，dict变慢了10倍。 教训始终如一。某些模型是有用的，但没有一个模型就是现实。要注意认知偏见。 代码已公开。(https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/2026/09/upcoming)