|
|
|
@article{DBLP:journals/tods/ChenV84,
author = {Wen-Chin Chen and
Jeffrey Scott Vitter},
title = {Analysis of New Variants of Coalesced Hashing},
journal = {ACM Trans. Database Syst.},
volume = {9},
number = {4},
year = {1984},
pages = {616-645},
ee = {http://doi.acm.org/10.1145/1994.2205, db/journals/tods/ChenV84.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
The coalesced hashing method has been shown to be very fast for dynamic information storage and retrieval. This paper analyzes in a uniform way the performance of coalesced hashing and its variants, thus settling some open questions in the literature.
In all the variants, the range of the hash function is called the address region, and extra space reserved for storing colliders is called the cellar. We refer to the unmodified method, which was analyzed previously, as late-insertion coalesced hashing. In this paper we analyze late insertion and two new variations called early insertion and varied insertion. When there is no cellar, the early-insertion method is better than late insertion; however, past experience has indicated that it might be worse when there is a cellar. Our analysis confirms that it is worse. The varied-insertion method was introduced as a means of combining the advantages of late insertion and early insertion. This paper shows that varied insertion requires fewer probes per search, on the average, than do the other variants.
Each of these three coalesced hashing methods has a parameter that relates the sizes of the address region and the cellar. Techniques in this paper are designed for tuning the parameter in order to achieve optimum search times. We conclude with a list of open problems.
Copyright © 1984 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.