# Does hashing under the Simple Uniform Hashing Assumption battle worst-case adversaries the same way quick sort does?

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.

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.
• @aioobe, yes, that's right. An attacker can create an input that has a $1/2^{128}$ chance of causing something bad to happen. Fortunately, an event of probability $1/2^{128}$ can be ignored for all engineering purposes -- that's smaller than the chance of a cosmic ray causing a bit-flip error in memory. (This is a sense in which worst-case complexity can be misleading or unhelpful in practice. Schemes with bad worst-case complexity can still be useful if the probability of encountering the worst case is sufficiently small and can't be triggered by an adversary.) – D.W. Jun 17 '19 at 1:56