Universal classes of hash functions (Extended Abstract)

ABSTRACT

This paper gives an input independent average linear time algorithm for storage and retrieval on keys. The algorithm makes a random choice of hash function from a suitable class of hash functions. Given any sequence of inputs the expected time (averaging over all functions in the class) to store and retrieve elements is linear in the length of the sequence. The number of references to the data base required by the algorithm for any input is extremely close to the theoretical minimum for any possible hash function with randomly distributed inputs. We present three suitable classes of hash functions which also may be evaluated rapidly. The ability to analyze the cost of storage and retrieval without worrying about the distribution of the input allows as corollaries improvements on the bounds of several algorithms.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: John T. Gill, III, Computational complexity of probabilistic Turing machines, Proceedings of the sixth annual ACM symposium on Theory of computing, p.91-95, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803889]
• 3: Eiichi Goto , Yasumasa Kanada, Hashing LEMMAs on time complexities with applications to formula manipulation, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.154-158, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806334]
• 4: F. Gustavson , D. Y. Y. Yun, Arithmetic complexity of unordered sparse polynomials, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.149-153, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806333]
• 5: Knuth, D.E., Sorting and Searching, Addison-Wesley, Reading, Mass. (1973).
• 6: Markowsky, G., private communication.
• 7: Rabin, M.O., Probabilistic algorithms, Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity (1976-to appear).
• 8: Rosenbaum, W.S., and Hilliard, J.J., Multifont OCR postprocessing system. IBM Journal of Research and Development (July 1975).
• 9: Strassen, V., and Solovay, R., A fast Monte-Carlo test for primality, SIAM Journal on Computing (to appear).

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Measurement, Theory