The analysis of an improved hashing technique

ABSTRACT

We discuss the problem of hashing in a full or nearly full table using open addressing. A scheme for reordering the table as new elements are added is presented. Under the assumption of having a reasonable hash function sequence, it is shown that even with a full table only about 2.13 probes will be required, on the average, to access an element. This scheme has the advantage that the expected time for adding a new element is proportional to that required to determine that an element is not in the table. Attention is then turned to the optimal reordering scheme (which is a maximum flow problem) and the minimax problem of arranging the table so as to minimize the length of the longest probe sequence to find any element. A unified algorithm is presented for both of these as well as the first method suggested. A number of simulation results are reported, the most interesting being an indication that the optimal reordering scheme will lead to an average of about 1.83 probes per search in a full table.

REFERENCES

• 1: Richard P. Brent, Reducing the retrieval time of scatter storage techniques, Communications of the ACM, v.16 n.2, p.105-109, Feb. 1973 [doi>10.1145/361952.361964]
• 2: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 3: Gonnet, G.H., Interpolation and Interpolation Hash Searching, University of Waterloo, Computer Science Dept. Research Report 76-02.
• 4: Guibas, L.J., "The Analysis of Hashing Algorithms that Exhibit k-ary Clustering," Proc. 17th Annual IEEE-FOCS Symp., Houston, Texas, Oct. 1976, pp. 183-196.
• 5: Leo J. Guibas , Endre Szemeredi, The analysis of double hashing(Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.187-191, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803647]
• 6: 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
• 7: Paterson, M.S., "On the Analysis of Hashing Schemes," CMU Conference on Algorithm Analysis, April 1976.
• 8: Peterson, W.W., "Addressing for Random-Access Storage", IBM Journal of Research and Development, 1,4 (April 1957), pp. 130-146.
• 9: Ronald L. Rivest, Optimal Arrangement of Keys in a Hash Table, Journal of the ACM (JACM), v.25 n.2, p.200-209, April 1978 [doi>10.1145/322063.322065]
• 10: Yao, A.C., and F.F. Yao, "The Complexity of Searching an Ordered Random Table", Proc. 17th Annual IEEE-FOCS Symp., Houston, Texas, Oct. 1976, pp. 173-177.

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: Sorting and searching

General Terms:
Algorithms