Tuning the coalesced hashing method to obtain optimum performance
- 1 October 1980
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 238-247
- https://doi.org/10.1109/sfcs.1980.48
Abstract
This paper analyzes the coalesced hashing method, in which a portion of memory (called the address region) serves as the range of the hash function while the rest of memory (called the cellar) is devoted solely to storing records that collide when inserted. If the cellar should get full, subsequent colliders must be stored in empty slots in the address region and, thus, may cause later collisions. Varying the relative size of the cellar affects search performance. The main result of this paper expresses the average search times as a function of the number of records and the cellar size, solving the long-standing open problem described in [Knu73, §6.4-43]. We use these formulas to pick the cellar size that leads to optimum search performance and then show that this "tuned" method is competitive with several well-known hashing schemes.Keywords
This publication has 4 references indexed in Scilit:
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- The analysis of double hashingJournal of Computer and System Sciences, 1978
- Handling identifies as internal symbols in language processorsCommunications of the ACM, 1959
- Limiting Distributions in Some Occupancy ProblemsThe Annals of Mathematical Statistics, 1958