On aspects of university and performance for closed hashing

ABSTRACT

We consider two hashing models for storing a set S ⊂ {0, 1, 2, …, m - 1} in a table T of size n. The first model uses universal hashing for a partially loaded table. A set of hash functions is universal if, for any the input set, a randomly selected function has an efficient expected performance. Universal hash functions originate in [CW79], where they were used for open hashing using chaining. [CW79] poses as an open question whether comparable results can be achieved for any closed hashing schemes. The second model is perfect hashing for a full table. In preprocessing the input set is used to determine a hash function that achieves some desired performance criteria. This model was used among others in [ME82] and [FKS84]. In both models a key problem is to construct a “small” set of functions, which will permit a short description (program) for each function in the set. We show, for the first time, that universal hashing can be successfully used for closed hashing and in particular for double hashing. Specifically, the set of congruential polynomials of &Ogr;(log n) degree is universal for double hashing if the table load is below .75; the program size (or number of random bits generated by the algorithm) is &Ogr;(log log m + log2 n). For perfect hashing, we obtain nearly tight results on the size of oblivious &Ogr;(1)-probe hash functions: Oblivious k-probe hash functions require &OHgr;(n/k2e-k + log log m) bits of description. A probabilistic construction is presented, which shows that oblivious k-probe hash functions, can be specified in &Ogr;(ne-k + log log m) bits, which nearly matches the above lower bound. We give a variation of an &Ogr;(1) time 1-probe (perfect) hash function that can be specified in &Ogr;(n + log log m) bits, which is tight to within a constant factor of the lower bound. In view of the adaptive schemes presented in [FNSS88], these bounds establish a significant gap between oblivious and non-oblivious &Ogr;(1)-probe search.

REFERENCES

• A85: M. Ajtai. "A Lower Bound for Finding Predecessors in Yao's Cell Probe Model," IBM RJ 4867 (51297) 10/3/85, Computer Science.
• BBDOP86: Francine Berman , Mary Ellen Bock , Eric Dittert , Michael J O'Donnell, Collections of functions for perfect hashing, SIAM Journal on Computing, v.15 n.2, p.604-618, May 1986 [doi>10.1137/0215044]
• CW79: J. L. Carter and M. N. Wegman "Universal Classes of Hash Functions," Journal of Computer and System Sciences 18, pp. 143-154 (1979).
• DKMMRT88: M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R.E. Tarjan. "Dynamic Perfect Hashing: Upper and Lower Bounds," 29th Annual Symposium on the Foundations of Computing, 1988, pp. 524-531.
• FN: A. Fiat and M. Naor. Personal communication, 1988.
• FN88: A. Fiat , M. Noar, Implicit O(1) probe search, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.336-344, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73039]
• FNSS88: Amos Fiat , Moni Naor , Jeanette Schmidt , Alan Siegel, Non-oblivious hashing, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.367-376, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62248]
• F: M.L. Fredman. Personal communication, 1988.
• FK84: M.L. Fredman and J. Koml6s. "On The Size Of Separating Systems And Families Of Perfect Hash Functions," SIAM Journal of Algebraic and Discrete Methods, Vo} 5, No. 1, March 1984, pp. 61-68.
• FKS84: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• HK73: J.E. Hopcroft and R.M. Karp. "An n5/2 Algorithm for Maximum Match~ngs in Bipartite Graphs," SIAM Journal on Computing, Vol 2, No. 4, (1973), pp. 225-231.
• JvE86: C T M Jacobs , P van Emde Boas, Two results on tables, Information Processing Letters, v.22 n.1, p.43-48, January 2, 1986 [doi>10.1016/0020-0190(86)90041-4]
• LM88: George Lueker , Mariko Molodowitch, More analysis of double hashing, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.354-359, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62246]
• Ma83: H. G. Mairson. "The Program Complexity of Searching a Table," 24th Symposium on Foundation of Computer Science, November, 1983.
• Ma84: Harry George Mairson, The program complexity of searching a table (data structures, applied combinatorics), 1984
• Me82: K. Mehlhorn. "On the Program size of Perfect and Universal Hash functions," Proc. 23rd Ann. Symp. on Foundations of Computer Science, 1982, pp. 170-175.
• Me84: K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, Springer-Verlag, Berlin Heidelberg, 1984.
• SvE84: C. Slot , P. van Emde Boas, On tape versus core an application of space efficient perfect hash functions to the invariance of space, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.391-400, December 1984 [doi>10.1145/800057.808705]
• TY79: Robert Endre Tarjan , Andrew Chi-Chih Yao, Storing a sparse table, Communications of the ACM, v.22 n.11, p.606-611, Nov. 1979 [doi>10.1145/359168.359175]
• WC79: M. N. Wegman and J. L. Carter. "New Classes and Applications of Hash Functions," 20th Annual Symposium on Foundations of Computer Science, October 1979, pp. 175-182.
• Y81: Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

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

General Terms:
Algorithms, Theory