Nordic Journal of Computing Bibliography

Ricardo A. Baeza-Yates and Hector Soza-Pollman. Analysis of Linear Hashing Revisited. Nordic Journal of Computing, 5(1):70-85, Spring 1998.

In this paper we characterize several expansion techniques used for linear hashing and we present how to analyze any linear hashing technique that expands based on local events or that mixes local events and global conditions. As an example we give a very simple randomized expansion technique, which is easy to analyze and implement. Furthermore, we obtain the analysis of the original hashing technique devised by Litwin, which was unsolved until now, comparing it to the later and more widely used version of Larson's. We also analyze one hybrid technique. Among other results, it is shown that the control function used by Litwin does not produce a good storage utilization, matching known experimental data.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; E.5 [Files]; E.2 [Data Storage Representations]

Additional Key Words and Phrases: external hashing, linear hashing, analysis of algorithms, optimal bucketing

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database