3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But it's still only a probabilistic argument, right? Strictly speaking the SUHA does not say anything about worst case complexity, or have I misunderstood something? $\endgroup$ – aioobe Jun 16 at 22:47
  • $\begingroup$ @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.) $\endgroup$ – D.W. Jun 17 at 1:56

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.