Geek asks and answers

Expected worst time complexity of searching for hash table chains?

When implementing a hash table using a good hash function (where the probability that any two elements collide is 1 / m, where m is the number of buckets), it is well known that the average time to wait for an element to search is & Theta; (1 +?), Where? load factor. In the worst case, the time is O (n), however, if all the elements are ultimately placed in the same bucket.

I recently read hash tables and found this article which claims (on page 3) that if & alpha; = 1, worst difficulty expected - & Theta; (log n / log log n). "Expected Worst Complexity," I mean, as expected, the maximum amount of work that you will have to do if the elements are distributed using a single hash function. This is different from the worst case, as the worst behavior (all elements in the same bucket) is extremely unlikely.

My question is this: the author seems to believe that differs in the value of? can change the expected worst search complexity. Does anyone know a formula, table, or article somewhere that discusses how? changes expected worst-case execution time?

+3
source share
2 answers

After some searching, I came across this research article , which gives a complete analysis of the expected worst-case behavior of a whole group of different types of hash tables, including chained hash tables. The author gives as an answer that the expected length is approximately equal to & gamma; -1 (m), where m is the number of buckets and & gamma; this is a gamma feature . Assuming that? is a constant, this is approximately ln m / ln ln m.

Hope this helps!

+1
source

α Θ(log n / log log n). , α n, . , α = O(n), O(n) ( , -).

, i αi e-α / i!. , m ' m . ( , .) m '- m , 1/m . (, & Beta; 1/m .)

, i! , i i. , , :

αi e-α / i! = 1/m = 1/(n/α) = α/n

:

i log(α) - α - (i log(i) - i + O(log(i)) = log(α) - log(n)
log(n) - α = i log(i) - i - i log(α) + O(log(i))

α, :

log(n) = i log(i) + O(i)

, i k log(n) / log(log(n)) k = Θ(1)? :

log(n) = (k log(n) / log(log(n))) (log(k) + log(log(n)) - log(log(log(n)))) + O(log(log(n)))
       = k (log(n) + o(log(n)) + o(log(n))

, α (1 + o(1)) log(n) / log(log(n))

+3

More articles:


All Articles