14
$\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?
|cite|improve this question
$\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$

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.