k-independent hashing

The goal of hashing is usually to map keys from some large domain (universe) ${\displaystyle U}$ into a smaller range, such as ${\displaystyle m}$ bins (labelled ${\displaystyle [m]=\{0,\dots ,m-1\}}$). In the analysis of randomized algorithms and data structures, it is often desirable for the hash codes of various keys to "behave randomly". For instance, if the hash code of each key were an independent random choice in ${\displaystyle [m]}$, the number of keys per bin could be analyzed using the Chernoff bound. A deterministic hash function cannot offer any such guarantee in an adversarial setting, as the adversary may choose the keys to be the precisely the preimage of a bin. Furthermore, a deterministic hash function does not allow for rehashing: sometimes the input data turns out to be bad for the hash function (e.g. there are too many collisions), so one would like to change the hash function.

The solution to these problems is to pick a function randomly from a large family of hash functions. The randomness in choosing the hash function can be used to guarantee some desired random behavior of the hash codes of any keys of interest. The first definition along these lines was universal hashing, which guarantees a low collision probability for any two designated keys. The concept of ${\displaystyle k}$-independent hashing, introduced by Wegman and Carter in 1981,[2] strengthens the guarantees of random behavior to families of ${\displaystyle k}$ designated keys, and adds a guarantee on the uniform distribution of hash codes.

The strictest definition, introduced by Wegman and Carter[2] under the name "strongly universal${\displaystyle _{k}}$ hash family", is the following. A family of hash functions ${\displaystyle H=\{h:U\to [m]\}}$ is ${\displaystyle k}$-independent if for any ${\displaystyle k}$ distinct keys ${\displaystyle (x_{1},\dots ,x_{k})\in U^{k}}$ and any ${\displaystyle k}$ hash codes (not necessarily distinct) ${\displaystyle (y_{1},\dots ,y_{k})\in [m]^{k}}$, we have:

${\displaystyle \Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]=m^{-k}}$

This definition is equivalent to the following two conditions:

1. for any fixed ${\displaystyle x\in U}$, as ${\displaystyle h}$ is drawn randomly from ${\displaystyle H}$, ${\displaystyle h(x)}$ is uniformly distributed in ${\displaystyle [m]}$.
2. for any fixed, distinct keys ${\displaystyle x_{1},\dots ,x_{k}\in U}$, as ${\displaystyle h}$ is drawn randomly from ${\displaystyle H}$, ${\displaystyle h(x_{1}),\dots ,h(x_{k})}$ are independent random variables.

Often it is inconvenient to achieve the perfect joint probability of ${\displaystyle m^{-k}}$ due to rounding issues. Following,[3] one may define a ${\displaystyle (\mu ,k)}$-independent family to satisfy:

${\displaystyle \forall }$ distinct ${\displaystyle (x_{1},\dots ,x_{k})\in U^{k}}$ and ${\displaystyle \forall (y_{1},\dots ,y_{k})\in [m]^{k}}$, ${\displaystyle ~~\Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]\leq \mu /m^{k}}$

Observe that, even if ${\displaystyle \mu }$ is close to 1, ${\displaystyle h(x_{i})}$ are no longer independent random variables, which is often a problem in the analysis of randomized algorithms. Therefore, a more common alternative to dealing with rounding issues is to prove that the hash family is close in statistical distance to a ${\displaystyle k}$-independent family, which allows black-box use of the independence properties.

The notion of k-independence can be used to differentiate between different collision resolution in hashtables, according to the level of independence required to guarantee constant expected time per operation.

For instance, hash chaining takes constant expected time even with a 2-independent family of hash functions, because the expected time to perform a search for a given key is bounded by the expected number of collisions that key is involved in. By linearity of expectation, this expected number equals the sum, over all other keys in the hash table, of the probability that the given key and the other key collide. Because the terms of this sum only involve probabilistic events involving two keys, 2-independence is sufficient to ensure that this sum has the same value that it would for a truly random hash function.[2]

Double hashing is another method of hashing that requires a low degree of independence. It is a form of open addressing that uses two hash functions: one to determine the start of a probe sequence, and the other to determine the step size between positions in the probe sequence. As long as both of these are 2-independent, this method gives constant expected time per operation.[8]

On the other hand, linear probing, a simpler form of open addressing where the step size is always one can be guaranteed to work in constant expected time per operation with a 5-independent hash function,[9] and there exist 4-independent hash functions for which it takes logarithmic time per operation.[10]

For Cuckoo hashing the required k-independence is not known as of 2021. In 2009 it was shown[11] that ${\displaystyle O(\log n)}$-independence suffices, and at least 6-independence is needed. Another approach is to use Tabulation hashing, which is not 6-independent, but was shown in 2012[12] to have other properties sufficient for Cuckoo hashing. A third approach from 2014[13] is to slightly modify the cuckoo hashtable with a so-called stash, which makes it possible to use nothing more than 2-independent hash functions.

Kane, Nelson and David Woodruff improved the Flajolet–Martin algorithm for the Distinct Elements Problem in 2010.[14] To give an ${\displaystyle \varepsilon }$ approximation to the correct answer, they need a ${\displaystyle {\tfrac {\log 1/\varepsilon }{\log \log 1/\varepsilon }}}$-independent hash function.

The Count sketch algorithm for dimensionality reduction requires two hash functions, one 2-independent and one 4-independent.

The Karloff–Zwick algorithm for the MAX-3SAT problem can be implemented with 3-independent random variables.

The MinHash algorithm can be implemented using a ${\displaystyle \log {\tfrac {1}{\epsilon }}}$-independent hash function as was proven by Piotr Indyk in 1999[15]

• Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. Cambridge University Press. p. 221. ISBN 978-0-521-47465-8.