时间复杂度在哈希分离链和开放的解决 [英] Time complexity for separate chaining and open addressing in hashing

问题描述

有关使用具有N键和M列表（地址）分离链哈希表，它的时间复杂度为：

For a hash table using separate chaining with N keys and M lists(addresses), its time complexity is:

Insert: O(1)

Search: O(N/M)

Remove: O(N/M)

以上应该是对的，我想。

The above should be right I think.

不过，我觉得不舒服分析的时间复杂度为开放式解决。比方说，客座率仍是N / M，有人可以提供一些线索如何处理它的时间复杂度，也许还有两种实现一点比较..谢谢！

But I don't feel comfortable analyzing time complexity for open addressing. Let's say the load factor is still N/M, can someone shed some light how to approach its time complexity and maybe also a little comparison of the two implementations.. Thanks!

编辑：我在线性探测这里特别感兴趣

I'm particularly interested in linear probing here.

推荐答案

的线性探测分析实际上的基本的比它最初看起来要复杂的多。 经典的分析线性探测工程（非常不现实）假设用于桌子对面的元素分布的哈希函数的行为就像一个完全随机的作用下。不幸的是，这真的是一个不公平的假设，使大多数散列函数，因为大多数散列函数分布在一个合理的非随机的方式元素。要选择一个哈希函数用于线性探测具有约束你上面给（预期）的时候，你通常需要选择一个类型的散列函数叫做 5两相互独立的哈希函数的。这种分析并不简单，但如果你很好奇，你可能要检查出纸的线性探测恒独立性，。本文还不会与您使用的是弱类型的哈希函数的说明为什么约束上面的时间也不会在这种情况下举行的假设线性探测哈希表的分析。

The analysis of linear probing is actually substantially more complicated than it might initially appear to be. The "classical" analysis of linear probing works under the (very unrealistic) assumption that the hash function used to distribute elements across the table behaves like a totally random function. Unfortunately, this really isn't a fair assumption to make for most hash functions, since most hash functions distribute elements in a reasonably non-random way. To pick a hash function for use in linear probing that has the (expected) time bound you gave above, you typically need to pick a type of hash function called a 5-wise independent hash function. This analysis is not simple, but if you're curious you might want to check out the paper "Linear Probing with Constant Independence,". This paper also does an analysis of linear probing hash tables with the assumption that you're using a weaker type of hash function to show why the above time bound won't hold in that case.

希望这有助于！

这篇关于时间复杂度在哈希分离链和开放的解决的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！