[Solved]: Does hashing under the Simple Uniform Hashing Assumption battle worst-case adversaries the same way quick sort does?

Problem Detail: 

One common way for algorithms to battle adversarial inputs is by acting randomly. One popular example is quicksort and choosing pivots randomly (this sort of notions is explained well in section 5.3 in CLRS 3rd edition page 122 where by acting randomly we manage to impose a distribution on our inputs).

With Simple Uniform Hashing (SUHA) we have that the hash function "evenly distributes" the keys in a random fashion across the hash table. This way the average length of a chain is not too long. Is the randomness that we assume inherently exists in this magic hash function the way we battle worst-case inputs? i.e., is this exactly how we ensure that the expected runtime will be small, since our hash function is random and no series of keys is bad? (i.e., a worst case input doesn't exist because the hash function will act randomly and hence, make the expected chain lengths small).

I am not sure if this is right or if this is the right way to think about it, but that's how I think of hash tables, that they are random so no chain can get too long (usually) and hence we perform well.

Asked By : Charlie Parker

Answered By : D.W.

Yes, your understanding is correct. That's exactly the role the hash function plays.

A pair of keys $x,y$ might collide with one hash function, but not with another. For any fixed set of keys, the expected number of collisions is small. Moreover, for any fixed set of keys, the probability of having a large number of collisions is very small. That's why we can say that the average-case running time is good, and why there's only a tiny probability that the running time is high.

To put it another way: Since the adversary doesn't know what hash function we will be using, he can't craft inputs (a set of keys) that will trigger worst-case behavior. The randomization ensures we only need to worry about average-case behavior (the adversary has no way to force us into the kind of situation that would trigger worst-case behavior). And, hash tables have excellent average-case running time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53879

3.2K people like this

 Download Related Notes/Documents