哈希表运行时复杂性(插入,搜索和删除)

Question

为什么我一直在哈希表上看到这些函数的不同运行时复杂性？

在wiki上,搜索和删除是O(n)(我认为哈希表的要点是持续查找,所以如果搜索是O(n)则重点是什么).

在不久前的一些课程笔记中,我看到了很多复杂性,具体取决于某些细节,包括所有O(1).如果我可以获得所有O(1),为什么要使用任何其他实现？

如果我在C++或Java等语言中使用标准哈希表,那么我可以期待时间复杂度是多少？

Answer 1

哈希表是O(1) 平均值和摊销的案例复杂性,但是它遇到了O(n) 最坏的案例时间复杂性.[我认为这是你的困惑]

O(n)由于两个原因,散列表的时间复杂度最差:

1. 如果将太多元素分解到同一个密钥中:查看此密钥可能需要一些O(n)时间.
2. 一旦哈希表通过其负载平衡 - 它必须重新散列[创建一个新的更大的表,并将每个元素重新插入到表中].

但是,据说是O(1)平均和摊销的情况,因为:

1. 非常罕见的是,许多项目将被散列到相同的密钥[如果您选择了良好的散列函数并且没有太大的负载平衡.
2. reshsh操作O(n)最多可以在n/2ops 之后发生,这些操作都是假定的O(1):因此当你将每个操作的平均时间相加时,你会得到:(n*O(1) + O(n)) / n) = O(1)

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

编辑:哈希表的另一个问题:缓存
您可能会在大型哈希表中看到性能损失的另一个问题是缓存性能.散列表遭遇缓存性能不佳,因此对于大型集合 - 访问时间可能需要更长时间,因为您需要将表的相关部分从内存重新加载到缓存中.

Answer 2

理想情况下,哈希表是O(1).问题是如果两个键不相等,但它们会导致相同的散列.

例如,想象一下字符串"这是最好的时候它是最糟糕的时期"和"绿鸡蛋和火腿"都导致哈希值123.

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

因此,在使用哈希表时,使用具有非常好的哈希函数的密钥非常重要,该哈希函数既快又不会导致不同对象的重复值.

合理？

Answer 3

一些哈希表(布谷鸟哈希)保证了O(1)查找

Answer 4

也许您正在考虑空间复杂度？即 O(n)。其他复杂性与哈希表条目的预期相同。随着桶数的增加，搜索复杂度接近 O(1)。如果在最坏的情况下哈希表中只有一个桶，那么搜索复杂度为 O(n)。

编辑以回应评论 我认为说 O(1) 是平均情况是不正确的。它确实是（如维基百科页面所说）O(1+n/k)，其中 K 是哈希表大小。如果 K 足够大，那么结果实际上是 O(1)。但假设 K 为 10，N 为 100。在这种情况下，每个桶将平均有 10 个条目，因此搜索时间绝对不是 O(1)；它是对多达 10 个条目的线性搜索。