On risks of using cuckoo hashing with simple universal hash classes

ABSTRACT

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.

REFERENCES

• 1: L. Carter and M. N. Wegman, Universal Classes of Hash Functions, J. Comput. Syst. Sci., 18 (1979), pp. 143--154.
• 2: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 3: M. Mitzenmacher and E. Upfal, Probability and Computing, Cambridge University Press, Cambridge, UK, 2005.
• 4: Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
• 5: D. Zuckerman, Simulating BPP Using a General Weak Random Source, Algorithmica, 16 (1996), pp. 367--391.
• 6: Martin Dietzfelbinger , Torben Hagerup , Jyrki Katajainen , Martti Penttonen, A reliable randomized algorithm for the closest-pair problem, Journal of Algorithms, v.25 n.1, p.19-51, Oct. 1997 [doi>10.1006/jagm.1997.0873]
• 7: Rasmus Pagh , Flemming Friche Rodler, Cuckoo Hashing, Proceedings of the 9th Annual European Symposium on Algorithms, p.121-133, August 28-31, 2001
• 8: Rasmus Pagh, On the cell probe complexity of membership and perfect hashing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.425-432, July 2001, Hersonissos, Greece [doi>10.1145/380752.380836]
• 9: Luc Devroye , Pat Morin, Cuckoo hashing: further analysis, Information Processing Letters, v.86 n.4, p.215-219, 31 May 2003 [doi>10.1016/S0020-0190(02)00500-8]
• 10: Rasmus Pagh , Flemming Friche Rodler, Cuckoo hashing, Journal of Algorithms, v.51 n.2, p.122-144, May 2004 [doi>10.1016/j.jalgor.2003.12.002]
• 11: Anna Pagh , Rasmus Pagh , Milan Ruzic, Linear probing with constant independence, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250839]
• 12: Michael Mitzenmacher , Salil Vadhan, Why simple hash functions work: exploiting the entropy in a data stream, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.746-755, January 20-22, 2008, San Francisco, California
• 13: J. Cohen and D. M. Kane, 6.856 Project: Bounds on the Independence Required for Cuckoo Hashing, http://web.mit.edu/dankane/www/Independence% 20Bounds.pdf.

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES