<p>Today you should probably use Tabulation hashing for Linear Probing.</p>
<p>In <a href="https://people.csail.mit.edu/mip/papers/charhash/charhash.pdf" rel="nofollow noreferrer">The Power of Simple Tabulation Hashing</a>
by Mihai Pătrașcu and Mikkel Thorup, this is shown to have at least the same guarantees as 5 independent hashing. Later work shows that it gives you better concentration (worst case bounds) as well.</p>
<p>Tabulation hashing is also a lot faster than even heavily optimized 5-independent polynomial hashing.
If you see the benchmarks at <a href="https://github.com/rurban/smhasher" rel="nofollow noreferrer">https://github.com/rurban/smhasher</a> you'll notice that tabulation is one of the fastest hash functions, while degree 4 polynomials are more than 4 times slower on short keys.</p>
<p>Regarding timing attacks, you should rehash if you think an adverserry has learned too much about your random seed. You can detect this statistically by measuring if events are taking longer than they should within high probability bounds.
E.g., with simple tabulation (Theorem 21), if the load factor is <span class="math-container">$\alpha$</span>, you never expect to see size <span class="math-container">$|I|$</span> intervals with more than <span class="math-container">$\alpha|I| + \sqrt{\alpha|I|} (\log n)^c$</span> elements. So if you do, you should rehash. Since this only happens with probability <span class="math-container">$1/n^2$</span> or so by chance, it doesn't affect your expected running time.</p>

CC BY-SA 4.0
2020-09-21T18:10:57.750Z
2020-09-21T18:10:57.750Z
Thomas Ahle
<p>One potential issue is when reading from a hash table, the elements should not be read in the order of the slots if all hash tables use the same hash function. This is because those elements, in that order, can cause the insert procedure on a smaller hash table with the same hash function to go quadratic, assuming that the max fill factor is over $1/2$. See:</p>

<ul>
<li><a href="https://issues.cloudera.org/browse/IMPALA-2653" rel="nofollow noreferrer">https://issues.cloudera.org/browse/IMPALA-2653</a></li>
<li><a href="https://github.com/rust-lang/rust/issues/36481" rel="nofollow noreferrer">https://github.com/rust-lang/rust/issues/36481</a></li>
</ul>

CC BY-SA 3.0
2017-01-02T02:26:31.613Z
2017-01-02T02:26:31.613Z
jbapple
<p>In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. (Sufficiency: <a href="http://www.itu.dk/people/pagh/papers/linear-jour.pdf">"Linear probing with constant independence", Pagh et al.</a>, necessity: <a href="http://people.csail.mit.edu/mip/papers/kwise-lb/kwise-lb.pdf">"On the k-Independence Required by Linear Probing and Minwise Independence", Pătraşcu and Thorup</a>)</p>

<p>It is my understanding that the fastest known 5-independent families use tabulation. Picking a function from such a family may be expensive, so I would like to minimize the number of times I do so while still preventing algorithmic complexity attacks as described in Crosby and Wallach's <a href="http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/">"Denial of Service via Algorithmic Complexity Attacks"</a>. I'm less worried about timing attacks (i.e. adversaries with stopwatches). What are the consequences of reusing the same function:</p>

<ol>
<li>When growing a hash table that is too full?</li>
<li>When shrinking a hash table that is not full enough?</li>
<li>When rebuilding a hash table that has too many "deleted" bits set?</li>
<li>In $k$ different hash tables that may contain some keys in common?</li>
<li>In $k$ different hash tables that contain no keys in common?</li>
</ol>

CC BY-SA 3.0
2017-01-04T05:54:15.190Z
If this is a question about practice... a plausible pragmatic approach is to use a cryptographic hash function, with a random secret included in the input, instead of using a scheme based on tabulation.  Then there's less pressure to reuse the same hash function; you can use a different secret for each hash table (and change the secret and rehash everything, when shrinking/growing/rebuilding the hash table).
D.W.
CC BY-SA 3.0
2017-01-04T08:04:41.940Z
I think even fast cryptographic hash functions on short input like SipHash-2-4 are pretty slow compared even compared to 5-independent families using polynomials.
jbapple
<ds.data-structures><hash-function><randomized-algorithms><security>
Reusing 5-independent hash functions for linear probing
jbapple
# Reusing 5-independent hash functions for linear probing

(Asked by: username_0 on 2011-09-08)

In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. (Sufficiency: ["Linear probing with constant independence", Pagh et al.](http://www.itu.dk/people/pagh/papers/linear-jour.pdf), necessity: ["On the k-Independence Required by Linear Probing and Minwise Independence", Pătraşcu and Thorup](http://people.csail.mit.edu/mip/papers/kwise-lb/kwise-lb.pdf))

It is my understanding that the fastest known 5-independent families use tabulation. Picking a function from such a family may be expensive, so I would like to minimize the number of times I do so while still preventing algorithmic complexity attacks as described in Crosby and Wallach's ["Denial of Service via Algorithmic Complexity Attacks"](http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/). I'm less worried about timing attacks (i.e. adversaries with stopwatches). What are the consequences of reusing the same function:

1. When growing a hash table that is too full?
2. When shrinking a hash table that is not full enough?
3. When rebuilding a hash table that has too many "deleted" bits set?
4. In $k$ different hash tables that may contain some keys in common?
5. In $k$ different hash tables that contain no keys in common?

**Tags:** ds.data-structures, hash-function, randomized-algorithms, security

> **Comments:**
> **username_1**: If this is a question about practice... a plausible pragmatic approach is to use a cryptographic hash function, with a random secret included in the input, instead of using a scheme based on tabulation.  Then there's less pressure to reuse the same hash function; you can use a different secret for each hash table (and change the secret and rehash everything, when shrinking/growing/rebuilding the hash table).  
> **username_0**: I think even fast cryptographic hash functions on short input like SipHash-2-4 are pretty slow compared even compared to 5-independent families using polynomials.  

---

## 2 answers

### Answer by username_2 on 2020-09-21. Score: 1

Today you should probably use Tabulation hashing for Linear Probing.

In [The Power of Simple Tabulation Hashing](https://people.csail.mit.edu/mip/papers/charhash/charhash.pdf)
by Mihai Pătrașcu and Mikkel Thorup, this is shown to have at least the same guarantees as 5 independent hashing. Later work shows that it gives you better concentration (worst case bounds) as well.

Tabulation hashing is also a lot faster than even heavily optimized 5-independent polynomial hashing.
If you see the benchmarks at <https://github.com/rurban/smhasher> you'll notice that tabulation is one of the fastest hash functions, while degree 4 polynomials are more than 4 times slower on short keys.

Regarding timing attacks, you should rehash if you think an adverserry has learned too much about your random seed. You can detect this statistically by measuring if events are taking longer than they should within high probability bounds.
E.g., with simple tabulation (Theorem 21), if the load factor is $\alpha$, you never expect to see size $|I|$ intervals with more than $\alpha|I| + \sqrt{\alpha|I|} (\log n)^c$ elements. So if you do, you should rehash. Since this only happens with probability $1/n^2$ or so by chance, it doesn't affect your expected running time.


---

### Answer by username_0 on 2017-01-02. Score: 1

One potential issue is when reading from a hash table, the elements should not be read in the order of the slots if all hash tables use the same hash function. This is because those elements, in that order, can cause the insert procedure on a smaller hash table with the same hash function to go quadratic, assuming that the max fill factor is over $1/2$. See:

* <https://issues.cloudera.org/browse/IMPALA-2653>
* <https://github.com/rust-lang/rust/issues/36481>


---

