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.