<p>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.</p>

CC BY-SA 3.0
2016-05-05T00:27:14.963Z
2016-05-05T00:27:14.963Z
David Eppstein
<p>I've been reading over two papers recently. The first, <a href="http://people.seas.harvard.edu/~salil/research/streamhash-soda.pdf">"Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream"</a> 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, <a href="http://people.csail.mit.edu/mip/papers/kwise-lb/kwise-lb.pdf">"On the $k$-Independence Required for Linear Probing and Minwise Independence"</a> gives strong lower bounds on the expected cost of linear probing lookups assuming different strengths of hash functions.</p>

<p>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)$.</p>

<p>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.</p>

<p>How can both of these statements be true at the same time?</p>

CC BY-SA 3.0
2016-05-04T17:56:03.100Z
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.
David Eppstein
CC BY-SA 3.0
2016-05-05T00:18:54.147Z
@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. :-)
templatetypedef
<ds.data-structures><lower-bounds><hash-function>
Two papers give contradictory bounds on linear probing. How do I resolve the disparity?
templatetypedef
# Two papers give contradictory bounds on linear probing. How do I resolve the disparity?

(Asked by: username_0 on 2016-05-04)

I've been reading over two papers recently. The first, ["Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream"](http://people.seas.harvard.edu/~salil/research/streamhash-soda.pdf) 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"](http://people.csail.mit.edu/mip/papers/kwise-lb/kwise-lb.pdf) 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?

**Tags:** ds.data-structures, lower-bounds, hash-function
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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. :-)  

---

## 1 answers

### Answer by username_1 on 2016-05-05. Score: 9 | Accepted answer

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.


---

