6
$\begingroup$

I've been reading over two papers recently. The first, "Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream" proves that, assuming there is sufficient entropy in a data source, weak hash functions end up producing distributions very close to truly uniformly random distributions. The other paper, "On the $k$-Independence Required for Linear Probing and Minwise Independence" gives strong lower bounds on the expected cost of linear probing lookups assuming different strengths of hash functions.

I'm having trouble reconciling the results of these two papers. The first paper proves that using 2-wise independent hash functions, if the entropy of the data source generating the elements of a linear probing hash table is sufficiently high, then the expected cost of a lookup is O(1) (and, more strongly, is equal to the bound assuming totally uniform hashing plus an o(1) term). On the other hand, the second paper proves that there exists a family of 2-universal hash functions for which the expected cost of a lookup in a linear probing hash table is $\Theta(\sqrt n)$.

These statements seem at odds with one another. I suspect that there's some technical condition from one of the two papers that I'm missing that make these bounds not conflict.

How can both of these statements be true at the same time?

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ The first one is for inputs where the keys are already somewhat randomly distributed. The second one is for worst case inputs. So they have different input models and therefore it shouldn't be surprising that they come to different conclusions. $\endgroup$
    – David Eppstein
    May 4, 2016 at 17:56
  • $\begingroup$ @DavidEppstein Ah, you're right. Looks like another way to see this is that it's a quantifier ordering issue - the first one assumes you first choose the hash function and then you choose the data, and the second one assumes you choose the data first and then choose the hash function. Convert that to an answer and I'll accept it. :-) $\endgroup$
    – templatetypedef
    May 5, 2016 at 0:18

1 Answer 1

Reset to default
9
$\begingroup$

The first one is average-case analysis, for sets of keys that are already somewhat randomly distributed (chosen either before or after the choice of hash function but with a probability distribution that is independent of the hash function). The second one is worst-case analysis, for sets of keys that are not random but are instead specially chosen to make the algorithm look bad (chosen before the hash function's random seed is known, for a specific 2-independent hash function that is also chosen to make the rest of the algorithm look bad). So it shouldn't be surprising that with two different input models you get two different results.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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