由网友(握不住的沙，那就扬了它)分享简介：为什么我总是看到不同的运行复杂性的一个哈希表这些功能呢？ Why do I keep seeing different runtime complexities for these functions on a hash table? 在维基，搜索和删除是O（n）的（我认为哈希表的一点是要有恒定的查找有啥点，如果搜...

为什么我总是看到不同的运行复杂性的一个哈希表这些功能呢？

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

在维基，搜索和删除是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） 平均摊销 情况的复杂性，但是是从患有O（N） 最坏的情况下时间复杂度。 [我想这就是你的困惑是]

Hash tables are O(1) average and amortized case complexity, however is 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:

如果过多的元素被散列到相同的密钥：看这里面的关键可能需要 O（N）时间 一旦一个哈希表已通过其负载均衡 - 它有老调重弹[创建一个新的更大的表，并重新插入每个元素表。 If too many elements were hashed into the same key: looking inside this key may take O(n) time. 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].

不过，据说是 O（1）平均摊销情况，因为：

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

这是非常罕见的，许多项目将被散列到同一个键[如果你选择了一个很好的散列函数，并没有太大的负载均衡。 的老调重弹的操作，这是 O（N），最多可以在发生N / 2 OPS，这些都是假设 O（1）：因此，当你每次运总结的平均时间，你会得到：（N * O（1）+ O （N））/ N）= O（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. 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)

请注意由于换汤不换药的问题 - 那些需要低延迟一个实时的应用程序和应用程序 - 不应该使用哈希表作为它们的数据结构

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问题哈希表：缓存 另外一个问题，你可能会看到大的哈希表的性能损失是由于缓存性能。 哈希表坏缓存性能遭受，从而为大集合 - 访问时间可能需要更长的时间，因为你需要重新加载从内存返回到缓存表中的相关部分。

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.