链接哈希表查找的预期最坏情况时间复杂度？ [英] Expected worst-case time complexity of chained hash table lookups?

问题描述

当使用好的散列函数实现哈希表时（其中任何两个元素的概率相互冲突为1 / m，其中m为桶数），众所周知，平均运行时间为查找元素是Θ（1 + alpha），其中α是负载因子。最糟糕的运行时间是O（n），但是，如果所有元素最终都放在同一个数据桶中。

When implementing a hash table using a good hash function (one where the probability of any two elements colliding is 1 / m, where m is the number of buckets), it is well-known that the average-case running time for looking up an element is Θ(1 + α), where α is the load factor. The worst-case running time is O(n), though, if all the elements end up put into the same bucket.

我最近在散列表上做了一些阅读并发现这篇文章，第3页）如果α = 1，预期最坏情况的复杂度为&Theta（log n / log log n）。通过预期的最坏情况复杂性，我的意思是，期望的是，如果元素通过统一散列函数分配，则必须执行的最大工作量。这与实际的最坏情况不同，因为最糟糕的行为（同一个桶中的所有元素）都不太可能实际发生。

I was recently doing some reading on hash tables and found this article which claims (on page 3) that if α = 1, the expected worst-case complexity is Θ(log n / log log n). By "expected worst-case complexity," I mean, on expectation, the maximum amount of work you'll have to do if the elements are distributed by a uniform hash function. This is different from the actual worst-case, since the worst-case behavior (all elements in the same bucket) is extremely unlikely to actually occur.

我的问题是以下 - 作者似乎建议，不同的α可以改变预期的最坏情况下的查找复杂性。有没有人知道一个公式，表或文章，讨论如何改变和alpha;改变预期的最坏情况运行时间？

My question is the following - the author seems to suggest that differing the value of α can change the expected worst-case complexity of a lookup. Does anyone know of a formula, table, or article somewhere that discusses how changing α changes the expected worst-case runtime?

推荐答案

经过一些搜索，我发现本研究论文，全面分析了一整套预期的最坏情况行为不同类型的散列表，包括链接哈希表。作者给出了一个答案，预期长度大约为Γ ^-1 （m），其中m是桶数和γ是 Gamma功能。假设α是一个常数，这是大约ln m / ln ln m。

After some searching, I came across this research paper that gives a complete analysis of the expected worst-case behavior of a whole bunch of different types of hash tables, including chained hash tables. The author gives as an answer that the expected length is approximately Γ^-1(m), where m is the number of buckets and Γ is the Gamma function. Assuming that α is a constant, this is approximately ln m / ln ln m.

希望这有帮助！

这篇关于链接哈希表查找的预期最坏情况时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！