Analysis of Early-Insertion Standard Coalesced Hashing

Chen, Wen-ChinVitter, Jeffrey Scott2011-03-162011-03-161983J. S. Vitter and W.-C. Chen. “Analysis of Early-Insertion Standard Coalesced Hashing,” SIAM Journal on Computing, 12(4), November 1983, 667–676. http://dx.doi.org/10.1137/0212046https://hdl.handle.net/1808/7169This paper analyzes the early-insertion standard coalesced hashing method (EISCH), which is a variant of the standard coalesced hashing algorithm (SCH) described in [Knu73], [Vit80] and [Vit82b]. The analysis answers the open problem posed in [Vit80]. The number of probes per successful search in full tables is 5% better with EISCH than with SCH.en-USAlgorithm analysisHashingCoalesced hashingEarly-insertionData structuresAverage-caseAnalysis of Early-Insertion Standard Coalesced HashingArticle10.1137/0212046openAccess