On Risks of Using Cuckoo Hashing with Simple Universal Hash Classes

Cuckoo hashing, introduced by Pagh and Rodler 10, is a dynamic dictionary data structure for storing a set S of n keys from a universe U, with constant lookup time and amortized expected constant insertion time. For the analysis, space (2+∊)n and Ω(log n)-wise independence of the hash functions is sufficient. In experiments mentioned in 10, several weaker hash classes worked well; however, a certain simple multiplicative hash family worked badly. In this paper, we prove that the failure probability is high when cuckoo hashing is run with the multiplicative class or with the very common class of linear hash functions over a prime field, even if space 4n is provided. The key set S is fully random, but it must be relatively dense in the universe U of all keys (like |S| ≥ |U|11/12). The bad behavior and the fact that this effect depends on the density of S in U can also be observed in experiments. The result transfers to larger universes if the keys are chosen from a suitable smaller domain. Viewed from a different perspective, our result illustrates that care must be taken when applying a recent result of Mitzenmacher and Vadhan (12, SODA 2008) proving good behavior of universal hash classes in combination with key sets that have some entropy. Their result is applicable to cuckoo hashing. A technical hypothesis in 12, namely the assumption that either the “collision probability” or the “maximum probability” is small, translates into the condition that |S| is relatively small in comparison to |U|. Our result shows that the result from 12 on 2-universal classes ceases to hold if |S|/|U| is not small enough, even for very common 2-universal hash classes and fully random key sets.