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. 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. On the other hand, linear probing, a simpler form of open addressing where the step size is always one, requires 5-independence. It can be guaranteed to work in constant expected time per operation with a 5-independent hash function, and there exist 4-independent hash functions for which it takes logarithmic time per operation. For Cuckoo hashing the required k-independence is not known as of 2021. In 2009 it was shown that -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 to have other properties sufficient for Cuckoo hashing. A third approach from 2014 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. Other Applications Kane, Nelson and David Woodruff improved the Flajolet–Martin algorithm for the Distinct Elements Problem in 2010. To give an approximation to the correct answer, they need a -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 -independent hash function as was proven by Piotr Indyk in 1999 References Further reading Hash functions Search algorithms Error detection and correction