Analysis of the Search Performance of Coalesced Hashing

An analysis is presented of the coalesced hashing method, m 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.