Dynamic hash tables

ABSTRACT

Linear hashing and spiral storage are two dynamic hashing schemes originally designed for external files. This paper shows how to adapt these two methods for hash tables stored in main memory. The necessary data structures and algorithms are described, the expected performance is analyzed mathematically, and actual execution times are obtained and compared with alternative techniques. Linear hashing is found to be both faster and easier to implement than spiral storage. Two alternative techniques are considered: a simple unbalanced binary tree and double hashing with periodic rehashing into a larger table. The retrieval time of linear hashing is similar to double hashing and substantially faster than a binary tree, except for very small trees. The loading times of double hashing (with periodic reorganization), a binary tree, and linear hashing are similar. Overall, linear hashing is a simple and efficient technique for applications where the cardinality of the key set is not known in advance.

REFERENCES

• 1: Carter, L.J. and Wegman, M.L. Universal Classes of Hash Functions, Journal of Computer and System Sciences 18, 1 (1979), 1.43-154.
• 2: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 3: 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
• 4: Larson, P.-A. Dynamic hashing. BIT 18, 2 (1978}, 184--201.
• 5: Larson, P.-,~. Linear hashing with partial expansions. In Proceedings of the 6th Conference on Very Large Databases, (New York, 1980), 224-232.
• 6: Per-Åke Larson, Performance analysis of linear hashing with partial expansions, ACM Transactions on Database Systems (TODS), v.7 n.4, p.566-587, Dec. 1982 [doi>10.1145/319758.319763]
• 7: Per-Åke Larson, Linear hashing with overflow-handling by linear probing, ACM Transactions on Database Systems (TODS), v.10 n.1, p.75-89, March 1985 [doi>10.1145/3148.3324]
• 8: Larson, P.-.~. Dynamic Hash Tables, Technical Report CS-86-21, University of Waterloo, 1986.
• 9: Litwin, W. Linear hashing: A new tool for file and table addressing. In Proceedings of the 6th Conference on Very Large Databases, (New York, 1980}, 212-223.
• 10: G. N.N. Martin, Spiral Storage: Incrementally Augmentable Hash Addressed Storage, University of Warwick, Coventry, UK, 1979
• 11: Mullin, J. K. Spiral storage: Efficient dynamic hashing with constant performance. Comput. J. 28, 3 {1985), 330-334.
• 12: Ramakrishna, M.V. Perfect Hashing for External Files, Technical Report CS-86-25, University of Waterloo, 1986.
• 13: Ramamohanarao, K. and Lloyd, J. K. Dynamic hashing schemes. Comput. J. 25, 4 (1982), 478-485.
• 14: K Ramamohanarao , R Sacks-Davis, Recursive linear hashing, ACM Transactions on Database Systems (TODS), v.9 n.3, p.369-391, Sept. 1984 [doi>10.1145/1270.1285]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Tables**

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

  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, Design, Experimentation, Performance