Analysis of linear hashing revisited
Ricardo A. Baeza-Yates, Héctor Soza-Pollman · 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. CR Classification: F.2.2, E.5, E.2. Key words: external hashing, linear hashing, analysis of algorithms, optimal bucketing. 1. Introduction External hashing is a very efficient technique used to obtain a fast organization and retrieval of information in big size files whose conten...