String hashing for linear probing

ABSTRACT

Linear probing is one of the most popular implementations of dynamic hash tables storing all keys in a single array. When we get a key, we first hash it to a location. Next we probe consecutive locations until the key or an empty location is found. At STOC'07, Pagh et al. presented data sets where the standard implementation of 2-universal hashing leads to an expected number of Ω(log n) probes. They also showed that with 5-universal hashing, the expected number of probes is constant. Unfortunately, we do not have 5-universal hashing for, say, variable length strings. When we want to do such complex hashing from a complex domain, the generic standard solution is that we first do collision free hashing (w.h.p.) into a simpler intermediate domain, and second do the complicated hash function on this intermediate domain. Our contribution is that for an expected constant number of linear probes, it is suffices that each key has O(1) expected collisions with the first hash function, as long as the second hash function is 5-universal. This means that the intermediate domain can be n times smaller, and such a smaller intermediate domain typically means that the overall hash function can be made simpler and at least twice as fast. The same doubling of hashing speed for O(1) expected probes follows for most domains bigger than 32-bit integers, e.g., 64-bit integers and fixed length strings. In addition, we study how the overhead from linear probing diminishes as the array gets larger, and what happens if strings are stored directly as intervals of the array. These cases were not considered by Pagh et al.

REFERENCES

• 1: John Black , Shai Halevi , Hugo Krawczyk , Ted Krovetz , Phillip Rogaway, UMAC: Fast and Secure Message Authentication, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.216-233, August 15-19, 1999
• 2: J. R. Black, C. U. Martel, and H. Qi. Graph and hashing algorithms for modern architectures: Design and performance. In Proc. 2nd WAE, pages 37--48, 1998.
• 3: J. Lawrence Carter , Mark N. Wegman, Universal classes of hash functions (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.106-112, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803400]
• 4: Martin Dietzfelbinger, Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes, Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, p.569-580, February 22-24, 1996
• 5: Martin Dietzfelbinger , Joseph Gil , Yossi Matias , Nicholas Pippenger, Polynomial Hash Functions Are Reliable (Extended Abstract), Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.235-246, July 13-17, 1992
• 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: G. L. Heileman and W. Luo. How caching affects hashing. In Proc. 7th ALENEX, pages 141--154, 2005.
• 8: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 9: D. E. Knuth. Notes on "open" addressing, 1963. Unpublished memorandum. Available at http://citeseer.ist.psu.edu/knuth63notes.html.
• 10: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 11: 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
• 12: 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]
• 13: R. Pagh. Personal communication, 2008.
• 14: 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]
• 15: H. Prodinger and W. Szpankowski. Preface for special issue on average case analysis of algorithms). Algorithmica, 22(4):363--365, 1998.
• 16: J. P. Schmidt , A. Siegel, The analysis of closed hashing under limited randomness, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.224-234, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100245]
• 17: A. Siegel , J. Schmidt, Closed Hashing is Computable and Optimally Randomizable with Universal Hash Functions, New York University, New York, NY, 1995
• 18: Bjarne Stroustrup, The C++ Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 19: Mikkel Thorup , Yin Zhang, Tabulation based 4-universal hashing with applications to second moment estimation, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 20: M. Wegman and J. Carter. New hash functions and their use in authentication and set equality. J. Comp. Syst. Sci., 22:265--279, 1981.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms