哈希表运行时复杂度（插入，搜索和删除） [英] Hash table runtime complexity (insert, search and delete)

问题描述

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

Why do I keep seeing different runtime complexities for these functions on a hash table?

在wiki上，搜索和删除是O（n）（我认为哈希表的一点是要进行常量查找，所以如果搜索是O（n） ）。

On wiki, search and delete are O(n) (I thought the point of hash tables was to have constant lookup so what's the point if search is O(n)).

在某些课程笔记之前，根据某些细节（包括所有O（1））的一些细节，我看到了广泛的复杂性。如果我可以得到所有的O（1），为什么要使用任何其他的实现？

In some course notes from a while ago, I see a wide range of complexities depending on certain details including one with all O(1). Why would any other implementation be used if I can get all O(1)?

如果我使用C ++或Java这样的语言使用标准哈希表，我希望时间的复杂度是？

If I'm using standard hash tables in a language like C++ or Java, what can I expect the time complexity to be?

推荐答案

哈希表是 O（1） average和摊销 案例复杂性，但是它的时间复杂度来自 O（n） 最坏情况。 [我认为这是你的困惑]

Hash tables are O(1) average and amortized case complexity, however it suffers from O(n) worst case time complexity. [And I think this is where your confusion is]

哈希表遭受 O（n）最差的时间复杂度由于两个原因：

Hash tables suffer from O(n) worst time complexity due to two reasons:

1. 如果将太多的元素散列到相同的键中：查看此键可能需要 O（n） time。


2. 一旦哈希表通过了它的负载平衡 - 它必须重新创建[创建一个更大的表，并将每个元素重新插入到表中]。

1. If too many elements were hashed into the same key: looking inside this key may take O(n) time.
2. Once a hash table has passed its load balance - it has to rehash [create a new bigger table, and re-insert each element to the table].

但是，据说这是$（$）code平均和摊销案例是因为：

However, it is said to be O(1) average and amortized case because:

1. 很多项目将被哈希到同一个键是非常罕见的[如果你选择了一个好的哈希函数，而你没有太大的负载平衡。


2. rehash操作， O（n）最多可以发生在 n / 2 ops，它们都被假定为 O（1）：因此，当您计算每个op的平均时间时，您得到：（n * O（1）+ O（n））/ n）= O（1）

1. It is very rare that many items will be hashed to the same key [if you chose a good hash function and you don't have too big load balance.
2. The rehash operation, which is O(n), can at most happen after n/2 ops, which are all assumed O(1): Thus when you sum the average time per op, you get : (n*O(1) + O(n)) / n) = O(1)

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

Note because of the rehashing issue - a realtime applications and applications that need low latency - should not use a hash table as their data structure.

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

在大型哈希表中可能会看到性能下降的另一个问题是由于缓存性能。 哈希表遭受恶意缓存性能，因此对于大型收集 - 访问时间可能需要更长时间，因为您需要将表的相关部分从内存重新加载到缓存中。

Annother issue with hash tables: cache
Another issue where you might see a performance loss in large hash tables is due to cache performance. Hash Tables suffer from bad cache performance, and thus for large collection - the access time might take longer, since you need to reload the relevant part of the table from the memory back into the cache.

这篇关于哈希表运行时复杂度（插入，搜索和删除）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！