15
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – D.W. Jan 4 '17 at 5:54
  • $\begingroup$ 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. $\endgroup$ – jbapple Jan 4 '17 at 8:04
1
$\begingroup$

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:

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.