1
$\begingroup$

My question: Is the Simple Uniform Hashing Assumption (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is O(1)?

It says in the Wikipedia article that this assumption implies that the average length of a chain is $\alpha = n / m$, but...

  • ...this is true even without this assumption, right? If the distribution is [4, 0, 0, 0] the average length is still 1.
  • ...this is a probabilistic statement, which is of little use when discussing worst case complexity, no?

It seems to me like a different assumption would be needed. Something like:

The difference between the largest and smallest bucket is bounded by a constant factor.

Maybe this is this implied by SUHA? If so, I don't see how.

$\endgroup$
1
$\begingroup$

I think the answer is no, SUHA does not imply anything regarding worst-case time complexity. The bottom line is that the hashing is still viewed as random, and the keys still unknown. Regardless of how small the probability is for all keys to hash to the same bucket, it's still a theoretical possibility, thus the theoretical worst-case is still O(n).

I think that when discussing hash tables, this is mentioned briefly, regarded as irrelevant in practice and then the discussion moves on to expected run time complexity, and we're in O(1) land.

With the assumption mentioned in the question...

The difference between the largest and smallest bucket is bounded by a constant factor.

...(which is strictly stronger than SUHA) it can indeed be shown that the worst-case run time complexity is O(1). This assumption implies that even the largest bucket is within a constant factor of the load factor limit. This in turn means all linked lists are bounded by a constant and we get O(1) as worst case.

This assumption however is somewhat unreasonable. While it's quite probable that it holds true for any descent hash function and non-pathological set of keys, how would one guarantee such property? One would have to push this assumption further down and make constraints on what keys are allowed to be stored in the hash table and so on. This is what makes it unreasonable in a sense.

$\endgroup$
0
$\begingroup$

Not only is SUHA insufficient to show that the largest bucket has size $O(\alpha)$, but if $m = n$, then there is a high probability that for any particular set of keys, the longest chain has length $\Theta(\lg n / \lg \lg n)$. There is a proof of this in CLRS and many proofs available in lecture notes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.