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 setting 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.

--Authors’ Abstract

The hashing techniques here are particularly suited to situations in which it is important that records, once inserted into a table, not be moved to other locations. The algorithms discussed are quite simple and are well described in the paper. The results of the analysis are also clearly described and readily understood. The analysis itself is very lengthy and requires concentrated and prolonged study to be understood.

It is interesting that this extended analysis establishes that the original method [1], invented in 1959, performs about as well as the subsequent refinements, when an appropriately sized cellar is provided.