Reusing 5-independent hash functions for linear probing

Question

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., necessity: "On the k-Independence Required by Linear Probing and Minwise Independence", Pătraşcu and Thorup)

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". 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?

Answer 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

Answer 2

Today you should probably use Tabulation hashing for Linear Probing.

In The Power of Simple Tabulation Hashing 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.