散列表真的可以是 O (1)吗？

小开

哈希是固定大小-查找适当的哈希桶是一个固定的成本操作。这意味着它是 O (1)。

计算哈希并不一定是一个特别昂贵的操作-我们在这里不讨论加密哈希函数。但那是附带的。散列函数计算本身并不依赖于元素的 N数目; 虽然它可能依赖于元素中数据的大小，但这不是 N所指的。因此散列的计算不依赖于 N，也是 O (1)。

小开

最佳答案

这里有两个变量，m 和 n，其中 m 是输入的长度，n 是散列中的项目数。

O (1)查找性能声明至少有两个假设:

您的对象可以在 O (1)时间内相等。
将会有一些散列冲突。

如果对象的大小是可变的，并且相等性检查需要查看所有位，那么性能将变为 O (m)。然而散列函数不一定是 O (m)-它可以是 O (1)。与加密哈希不同，字典中使用的哈希函数不必查看输入中的每个位，以便计算哈希。实现只能查看固定数量的位。

对于足够多的条目，条目的数量将变得大于可能的哈希数量，然后你会得到冲突，导致性能上升超过 O (1) ，例如对于一个简单的链表遍历 O (n)(或 O (n * m) ，如果两个假设都是错误的)。

在实践中，尽管 O (1)声称在技术上是错误的，但对于许多现实世界的情况，特别是上述假设成立的情况，差不多是正确的。

小开

您必须计算散列，因此对于正在查找的数据的大小，顺序是 O (n)。在做 O (n)工作之后，查找可能是 O (1) ，但在我看来仍然是 O (n)。

什么？对单个元素进行哈希处理需要固定的时间。为什么会有别的原因呢？如果你要插入 n元素，那么是的，你必须计算 n散列，这需要线性时间... ... 要查找一个元素，你要计算一个单一的散列，然后找到合适的桶。您不需要重新计算哈希表中已经存在的所有内容的哈希值。

除非你有一个完美的哈希表或者一个大的哈希表，否则每个桶可能会有几个条目，所以它在某个时候会转变成一个小的线性搜索。

不一定。桶不一定是列表或数组，它们可以是任何容器类型，比如平衡的 BST。这意味着 O(log n)最坏的情况。但是这就是为什么选择一个好的散列函数以避免在一个桶中放入太多元素是非常重要的。正如 KennyTM 指出的，平均来说，你仍然可以得到 O(1)的时间，即使偶尔你不得不挖通一个桶。

哈希表的优缺点当然是空间复杂性。你在用空间交换时间，这似乎是计算机科学中常见的情况。

您在其他注释中提到使用字符串作为键。你担心计算一个字符串的散列所花费的时间，因为它由几个字符组成？正如其他人再次指出的那样，计算散列并不一定需要查看所有的字符，不过如果您这样做，可能会产生更好的散列。在这种情况下，如果键中平均有 m字符，并且您使用所有这些字符来计算散列，那么我想您是对的，查找将使用 O(m)。如果 m >> n那么你可能有一个问题。这种情况下，你最好还是用 BST。或者选择一个更便宜的散列函数。

小开

只有当表中的键数不变且有其他一些假设时，散列才是 O (1)。但在这种情况下，它具有优势。

如果密钥具有 n 位表示形式，散列函数可以使用其中的1、2、 ... n 位。考虑使用1位的散列函数。评估结果肯定是 O (1)。但是您只是将密钥空间划分为2。所以您要将多达2 ^ (n-1)个键映射到同一个 bin 中。使用 BST 搜索这需要多达 n-1个步骤来找到一个特定的关键，如果几乎满了。

您可以扩展它来查看如果散列函数使用 K 位，则 bin 大小为2 ^ (n-k)。

所以 K 位散列函数 = = > 不超过2 ^ K 有效箱 = = > 最多2 ^ (n-K) n 位键每个箱 = = > (n-K)步(BST)来解决冲突。实际上，大多数散列函数的“有效性”要低得多，需要/使用比 K 位更多的位才能产生2 ^ k 个容器。因此，即便如此，这也是乐观的。

您可以这样看待它——您将需要 ~ n 个步骤，以便能够在最坏的情况下唯一地区分一对 n 位的键。真的没有办法绕过这个信息理论的限制，哈希表与否。

但是，这不是如何/当您使用哈希表！

复杂性分析假设对于 n 位键，表中可能有 O (2 ^ n)键(例如，所有可能键的1/4)。但是大多数情况下(如果不是全部的话) ，我们使用哈希表时，表中的 n 位键的数量是恒定的。如果你只想要表中有一个固定数量的键，比如说 C 是你的最大值，那么你可以形成一个包含 O (C)容器的哈希表，这样可以保证预期的常量冲突(使用一个好的哈希函数) ; 还有一个哈希函数，使用 ~ logC 表示密钥中 n 个比特。那么每个查询都是 O (logC) = O (1)。这就是人们声称“ hash 表访问是 O (1)”/的方式

这里有几个陷阱——首先，说你不需要所有的比特可能只是一个计费技巧。首先，您不能真正地将键值传递给散列函数，因为那将在内存中移动 n 位，即 O (n)。所以你需要做的是，例如，引用传递。但是您仍然需要将它存储在已经是 O (n)操作的地方; 您只是不需要将它计入哈希; 您的整个计算任务无法避免这一点。其次，进行哈希处理，查找 bin，并找到多于1个键; 成本取决于解析方法——如果进行基于比较(BST 或 List)的比较，将有 O (n)操作(回忆键为 n 位) ; 如果进行第二个哈希，那么，如果第二个哈希发生冲突，也会出现同样的问题。所以 O (1)不是100% 保证的，除非你没有冲突(你可以通过拥有一个比键更多容器的表来提高机会，但是仍然)。

在这种情况下，考虑另一种选择，例如 BST。有 C 键，所以一个平衡的 BST 在深度上是 O (logC) ，所以搜索采用 O (logC)步骤。然而，在这种情况下，比较将是一个 O (n)操作... ... 因此，在这种情况下，散列似乎是一个更好的选择。

小开

有两个设置下，您可以得到 O (1)最坏的情况下的时间。

如果您的设置是静态的，那么 FKS 散列将得到您最坏的情况 O (1)保证。但正如你所说，你的设置不是静态的。
如果使用 Cuckoo 散列，则查询和删除为 < em > O (1) 最坏的情况，但插入只是预期的 O (1)。如果对插入的总数有一个上限，并将表大小设置为大约25% ，那么 Cuckoo 散列就可以很好地工作。

从给你复制

小开

根据这里的讨论，如果 X 是(表中元素 #/箱中元素 #)的上限，那么假设有一个有效的 bin 查找实现，那么更好的答案是 O (log (X))。

小开

DR: 如果您从通用的散列函数家族中随机地选择散列函数，那么散列表保证 O(1)预期的最坏情况时间。预期最坏情况与普通情况不同。

免责声明: 我没有正式证明散列表是 O(1)，因为看看这个来自 Coursera [ 1]的视频。我也不讨论哈希表的 分期付款方面。这与关于散列和碰撞的讨论是正交的。

在其他的回答和评论中，我看到了令人惊讶的大量关于这个话题的混淆，我将在这个长长的回答中尝试纠正其中的一些。

推理最坏的情况

有不同类型的最坏情况分析。到目前为止，大多数答案在这里做的分析是不是最坏的情况，而不是 一般情况[ 2]。普通案件分析更加实用。也许您的算法有一个坏的最坏情况输入，但实际上对于所有其他可能的输入都工作得很好。底线是运行时 取决于数据集。

请考虑散列表的 get方法的以下伪代码。这里我假设我们通过链接来处理冲突，所以表的每个条目都是一个 (key,value)对的链接列表。我们还假设存储桶的数量 m是固定的，但是它是 O(n)，其中 n是输入中的元素数量。

function get(a: Table with m buckets, k: Key being looked up)
bucket <- compute hash(k) modulo m
for each (key,value) in a[bucket]
return value if k == key
return not_found

正如其他答案所指出的，这在平均 O(1)和最坏的情况下 O(n)运行。我们可以在这里通过质疑来勾勒出一个证明。挑战如下:

(1)你把你的哈希表算法给了对手。

对手可以研究它，准备他想要的任何时间。

(3)最后，对手给你一个大小为 n的输入，让你插入到你的表中。

问题是: 对手输入的散列表有多快？

从步骤(1)开始，对手就知道了你的散列函数; 在步骤(2)中，对手可以用相同的 hash modulo m创建一个 n元素的列表，比如随机计算一组元素的散列; 然后在步骤(3)中，他们可以给你这个列表。但是请注意，由于所有 n元素都散列到同一个 bucket 中，因此算法将花费 O(n)时间来遍历该 bucket 中的链表。无论我们重试多少次挑战，对手总是赢，这就是你的算法有多糟糕，最坏的情况 O(n)。

为什么散列是 O (1) ？

在上一个挑战中，让我们感到困惑的是，对手非常了解我们的 hash 函数，并且可以利用这些知识来构造最糟糕的输入。如果不总是使用一个固定的散列函数，而是实际上有一组散列函数 H，算法可以在运行时从中随机选择，会怎么样？如果你好奇的话，H被称为 通用散列函数族[ 3]。好的，我们试着加入一些 随机性。

首先假设我们的散列表也包含一个种子 r，并且在构造时将 r分配给一个随机数。我们分配它一次，然后就修复了那个散列表实例。现在让我们重新审视一下我们的伪代码。

function get(a: Table with m buckets and seed r, k: Key being looked up)
rHash <- H[r]
bucket <- compute rHash(k) modulo m
for each (key,value) in a[bucket]
return value if k == key
return not_found

如果我们再试一次: 从步骤(1)开始，对手可以知道我们在 H中使用的所有哈希函数，但是现在我们使用的特定哈希函数依赖于 r。r的价值对于我们的结构是私有的，敌人不能在运行时检查它，也不能提前预测它，所以他不能炮制一个总是对我们不利的列表。让我们假设在步骤(2)中，对手随机选择 H中的一个函数 hash，然后在 hash modulo m下制作一个 n碰撞列表，并将其发送给步骤(3) ，交叉手指，在运行时 H[r]将与他们选择的 hash相同。

对于对手来说，这是一个严重的赌注，他精心制作的列表在 hash下发生冲突，但在 H中只是任何其他散列函数下的随机输入。如果他赢了这个赌注，我们的运行时间将是最坏的情况下 O(n)一样，但如果他输了，那么我们只是被给予一个随机输入的平均 O(1)的时间。事实上，大多数时候对手都会输，每次 |H|挑战他只赢一次，我们可以让 |H|变得非常大。

将这个结果与之前的算法进行对比，其中对手总是赢得挑战。这里有点手势，但因为 大多数时候的对手将失败，这是真的，对于所有可能的策略，对手可以尝试，这是因为，虽然最坏的情况是 O(n)，预期的最坏情况实际上是 O(1)。

再说一次，这不是一个正式的证明。我们从这个预期的最坏情况分析中得到的保证是，我们的运行时现在是 独立于任何特定的输入。这是一个真正随机的保证，而不是一般的案例分析，我们表明，一个有动机的对手可以很容易地制造不好的输入。

小开

A.该值比哈希表的大小小一个 int 值。因此，该值是它自己的哈希表，所以不存在哈希表。但是如果有的话，它将是 O (1) ，而且仍然是低效的。

在这种情况下，您可以轻松地将键映射到不同的存储桶，因此数组似乎是比散列表更好的数据结构选择。尽管如此，效率低下并不会随着桌子的大小而增加。

(你可能仍然使用哈希表，因为你不相信 int 会随着程序的发展而保持比表大小的状态，你想让代码在关系不存在的情况下有可能重用，或者你只是不想让人们阅读/维护代码不得不浪费精力去理解和维护关系)。

B.您必须计算值的哈希值。在这种情况下，正在查找的数据大小的顺序是 O (n)。在做 O (n)工作之后，查找可能是 O (1) ，但在我看来仍然是 O (n)。

我们需要区分键的大小(例如，以字节为单位)和存储在散列表中的键数的大小。声称哈希表提供 O (1)操作意味着操作 随着键数的增加，< em > (插入/擦除/查找)不会进一步减慢速度从数百到数千到数百万到数十亿(至少不是如果所有的数据都在同样快速的存储器中访问/更新，RAM 或磁盘缓存效应可能发挥作用，但即使是最坏情况下的缓存丢失的成本往往是最好情况下命中的一些常数倍)。

考虑一个电话簿: 你可能在里面有很长的名字，但是不管这本书有100个名字，或者1000万个，平均名字长度将是相当一致的，而且是历史上最糟糕的情况..。

有史以来最长名字的吉尼斯世界纪录是由阿道夫 · 布莱恩(Adolph Blaine)、查尔斯 · 大卫 · 厄尔(David Earl)、弗雷德里克 · 杰拉德 · 休伯特(Frederick Gerald Hubert)、欧文 · 肯尼思 · 劳埃德 · 马丁 · 尼禄 · 保罗 · 昆西 · 谢尔曼 · 托马斯 · 恩卡斯 · 维克多 · 威廉 · 谢尔克斯(William Xerxes)、扬西 · 沃尔夫斯克莱格尔斯坦 ·

... wc告诉我那是215个字符-这不是用力到键长度的上界，但我们不需要担心 非常严重更多。

这适用于大多数现实世界的哈希表: 平均键长度不会随着使用的键数量的增长而增长。也有例外，例如一个键创建例程可能返回嵌入递增整数的字符串，但即使这样，每次你增加一个数量级的键数，你只增加了1个字符的键长，这并不重要。

还可以从固定大小的密钥数据创建散列。例如，微软的 Visual C + + 附带了一个 std::hash<std::string>的标准库实现，它创建了一个散列，其中只包含沿着字符串均匀间隔的10个字节，因此，如果字符串只在其他索引上变化，你就会得到冲突(因此在冲突后搜索方面，实际上非 O (1)行为) ，但是创建散列的时间有一个硬上限。

除非您有一个完美的散列表或大型散列表，否则每个桶可能有几个项目。因此，它在某一点上退化成一个小的线性搜索。

一般来说是这样的，但是哈希表的可怕之处在于，在那些“小型线性搜索”期间访问的键的数量——对于 分开链接碰撞方法来说——是哈希表 载荷系数(键与桶的比率)的函数。

例如，如果负载因子为1.0，那么这些线性搜索的平均长度为1.58，与键的数量无关(参见我的答案就在这里)。对于封闭散列来说，它有点复杂，但是当负载因子不是太高的时候，情况也不是很糟糕。

这在技术上是正确的，因为哈希函数不需要使用键中的所有信息，因此可以是常量时间，并且因为一个足够大的表可以将冲突降低到接近常量时间。

这不是重点。任何类型的关联数据结构有时最终都必须在键的每个部分执行操作(不等式有时可能仅由键的一部分来确定，但是等式通常需要考虑每个位)。至少，它可以散列一次并存储散列值，如果它使用一个足够强大的散列函数-例如64位的 MD5-它可能实际上忽略了两个键散列到同一个值的可能性(我工作的一家公司正是这样做的分布式数据库: 散列生成时间与广域网范围的网络传输相比仍然是微不足道的)。因此，没有太多的理由去纠结处理密钥的成本: 这是存储密钥所固有的，不管数据结构如何，如上所述——并不会随着密钥的增加而变得更糟。

至于足够大的散列表带来的冲突，这也没有抓住问题的关键。对于单独链接，在任何给定的负载因子下，仍然有一个恒定的平均碰撞链长度——当负载因子较高时，碰撞链长度就会更高，而且这种关系是非线性的。SO 用户 Hans 在我的答案也链接在上面上评论说:

以非空桶为条件的平均桶长是衡量效率的较好方法。它是 a/(1-e ^ {-a })[其中 a 是负载因子，e 是2.71828... ]

因此，负载因子 一个人决定了在插入/擦除/查找操作期间必须搜索的碰撞键的平均数量。对于单独的链接，当负载因子较低时，它不仅接近于常数-它是 一直都是常数。对于开放式寻址，虽然你的声明有一些有效性: 一些碰撞元素被重定向到替代桶，然后可以干扰对其他键的操作，所以在更高的负载因子(特别是 > .8或.9)碰撞链长度变得更加显着恶化。

这在实践中是正确的，因为随着时间的推移，只要选择哈希函数和表大小以尽量减少冲突，即使这通常意味着不使用常量时间哈希函数，它也能正常工作。

好吧，表的大小应该导致一个合理的负载因子给予选择关闭散列或分离链接，但也如果散列函数是有点弱，键不是非常随机的，有一个素数桶往往有助于减少冲突也(hash-value % table-size然后包围这样的变化，只有一个高阶位或两个在散列值仍然解决桶散布伪随机跨散列表的不同部分)。

小开

通常 hash()是 O(m)，其中 m是一把钥匙的长度

我的三分钱。

24年前 Sun 发布 jdk 1.2的时候，他们修复了 String.hashCode ()中的一个错误，因此从 jdk1.2开始，哈希不再仅仅基于字符串的一部分计算，而是读取字符串的每一个字符。这种改变是有意的，IHMO 非常明智。

在大多数语言中，建立在哈希工程类似。它处理整个对象来计算哈希，因为键通常很小，而冲突会导致严重的问题。

有许多理论论据证实和否定了 O (1)散列查找开销。他们中的许多人是理性的和有教育意义的。

让我们跳过这个理论，做一些实验代替:

import timeit samples = [tuple("LetsHaveSomeFun!")] # better see for tuples # samples = ["LetsHaveSomeFun!"] # hash for string is much faster. Increase sample size to see for _ in range(25 if isinstance(samples[0], str) else 20): samples.append(samples[-1] * 2) empty = {} for i, s in enumerate(samples): t = timeit.timeit(lambda: s in empty, number=2000) print(f"{i}. For element of length {len(s)} it took {t:0.3f} time to lookup in empty hashmap")

当我运行它时，我得到:

0. For element of length 16 it took 0.000 time to lookup in empty hashmap 1. For element of length 32 it took 0.000 time to lookup in empty hashmap 2. For element of length 64 it took 0.001 time to lookup in empty hashmap 3. For element of length 128 it took 0.001 time to lookup in empty hashmap 4. For element of length 256 it took 0.002 time to lookup in empty hashmap 5. For element of length 512 it took 0.003 time to lookup in empty hashmap 6. For element of length 1024 it took 0.006 time to lookup in empty hashmap 7. For element of length 2048 it took 0.012 time to lookup in empty hashmap 8. For element of length 4096 it took 0.025 time to lookup in empty hashmap 9. For element of length 8192 it took 0.048 time to lookup in empty hashmap 10. For element of length 16384 it took 0.094 time to lookup in empty hashmap 11. For element of length 32768 it took 0.184 time to lookup in empty hashmap 12. For element of length 65536 it took 0.368 time to lookup in empty hashmap 13. For element of length 131072 it took 0.743 time to lookup in empty hashmap 14. For element of length 262144 it took 1.490 time to lookup in empty hashmap 15. For element of length 524288 it took 2.900 time to lookup in empty hashmap 16. For element of length 1048576 it took 5.872 time to lookup in empty hashmap 17. For element of length 2097152 it took 12.003 time to lookup in empty hashmap 18. For element of length 4194304 it took 25.176 time to lookup in empty hashmap 19. For element of length 8388608 it took 50.399 time to lookup in empty hashmap 20. For element of length 16777216 it took 99.281 time to lookup in empty hashmap

很明显，其中 m 是 钥匙的长度。

你可以为其他主流语言做类似的实验，我希望你也能得到类似的结果。