哈希表运行时复杂度（插入、搜索和删除）

Question

哈希表运行时复杂度（插入、搜索和删除）

algorithmdata-structureshashtime-complexityhashtable

112

我为什么会看到这些哈希表函数的不同运行时间复杂度？

在维基百科上，查找和删除是O(n)（我认为哈希表的目的是具有恒定的查找时间，那么如果查找是O(n)，这还有什么意义呢）。

在以前的一些课程笔记中，我看到了各种不同的复杂度，取决于某些细节，包括一种全都是O(1)的方法。如果我可以得到全部是O(1)，为什么要使用其他实现方法？

如果我在像C++或Java这样的语言中使用标准哈希表，我可以期望时间复杂度是什么？

- user1136342

一个完美的哈希表具有O(1)的查找效率，但为了达到这个效果，在设计表时必须知道数据将会是什么。 - Mooing Duck

3

最坏情况下时间复杂度为O(n)，平均情况下时间复杂度为O(1)。在最坏情况下，可能要插入N个元素，它们都散列到同一个桶中。那么，在这种数据集上进行删除和搜索的时间复杂度也将是O(n)。 - Larry Watanabe

相关："哈希表的时间复杂度" - David Cary

5个回答

27

理想情况下，哈希表的时间复杂度为O(1)。问题在于如果两个键不相等，但它们生成相同的哈希值。

例如，假设字符串"it was the best of times it was the worst of times"和"Green Eggs and Ham"都生成哈希值123。

当插入第一个字符串时，它被放置在桶123中。当插入第二个字符串时，它会看到桶123已经有一个值存在。然后，它会将新值与现有值进行比较，并发现它们不相等。在这种情况下，为该键创建一个数组或链表。此时，检索此值变成了O(n)，因为哈希表需要遍历该桶中的每个值以找到所需的值。

因此，在使用哈希表时，使用具有良好哈希函数的关键字非常重要，该函数既快速又不经常为不同对象生成重复值。

明白吗？

- Mike Christensen

1

由于哈希表需要遍历桶中的每个值，但是该桶并不包含n个项，只有那些散列到特定键的项。 - SamAko

1

注意：在Java 8+中，可以使用平衡树来实现lg(n)的检索，而不是使用链表。 - EntangledLoops

2

@T.Rex：在最坏的情况下，桶中将有n个项目。 - jose

12

一些哈希表（布谷鸟哈希）具有保证的O(1)查找。

- Demi

1

使用动态完美哈希次级数据结构进行链接，可以实现O(1)的高概率。 - Wolfgang Brehm

8

也许你在看空间复杂度？那是O(n)。其他复杂度如预期所在哈希表条目中。随着桶的数量增加，搜索复杂度接近于O(1)。如果在哈希表中最坏情况下只有一个桶，那么搜索复杂度就是O(n)。 根据评论进行编辑我认为说O(1)是平均情况并不正确。实际上，它是（正如维基百科页面所说）O(1+n/k)，其中K是哈希表大小。如果K足够大，则结果有效地为O(1)。但是假设K为10，N为100。在这种情况下，每个桶平均将有10个条目，因此搜索时间绝对不是O(1)；它是通过多达10个条目的线性搜索。

- Mark Wilkins

哦，我只是在看最坏情况。所以明确一下，当人们说O(1)时，他们只是指平均情况吗？ - user1136342

@user1136342：编辑了答案，试图澄清这一点。 - Mark Wilkins

2

通常哈希表的负载均衡是 table_size/8 <= #elements <= table_size/2，因此它会回到 O(1)。但是，如果表的大小是动态的，则仍然存在重新散列问题，这将使最坏情况达到 O(n)。详见我的回答以获取细节和解释。 - amit

2

根据哈希实现的方式，最坏的情况下时间复杂度可以达到O(n)，而在最好的情况下为O(1)（通常情况下，如果你的数据结构不太大，很容易达到）

- jmj

如果你可以实现成O(1)，为什么要让它成为O(n)呢？ - user1136342

好的，我说在最坏的情况下。 - jmj

@JigarJoshi：你能给出一个最坏情况下的O(n)运行时间的例子吗？ - Rachel

2

返回一个单一数字的哈希函数，以便所有条目都在同一个存储桶中。 - jmj

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

哈希表具有O(1)的平均和摊销时间复杂度，但会受到O(n)的最坏情况时间复杂度的影响。[我认为这就是你的困惑所在]

哈希表受到O(n)最坏情况时间复杂度的影响，有两个原因:

如果许多元素被哈希到相同的键中，则查找该键可能需要O(n)的时间。
一旦哈希表已经通过了其负载平衡 - 它必须重新哈希[创建一个新的更大的表，并将每个元素重新插入表中]。

然而，它被认为具有O(1)的平均和摊销情况，因为:

很少有许多条目会哈希到相同的键中[如果您选择了一个好的哈希函数并且没有太大的负载平衡]。
重新哈希操作，它是O(n)，最多可以在n / 2个操作之后发生，这些操作都假定为O(1)：因此当您总结每个操作的平均时间时，您会得到：（n * O(1) + O(n)) / n）= O(1)

请注意，由于重新哈希问题 - 实时应用程序和需要低延迟的应用程序不应使用哈希表作为其数据结构。

编辑：哈希表的另一个问题：缓存。

在大型哈希表中可能会出现性能损失的另一个问题是缓存性能。 哈希表由于缓存性能不佳而受到影响，因此对于大型集合，访问时间可能会更长，因为您需要重新从内存中加载表的相关部分回到缓存中。