Loading...
Analysis of Early-Insertion Standard Coalesced Hashing
Chen, Wen-Chin Vitter, Jeffrey Scott
Chen, Wen-Chin
Vitter, Jeffrey Scott
Citations
Altmetric:
Abstract
This 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.
Description
Date
1983
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
Files
Loading...
Vitter_1983.pdf
Adobe PDF, 1.02 MB
Research Projects
Organizational Units
Journal Issue
Keywords
Algorithm analysis, Hashing, Coalesced hashing, Early-insertion, Data structures, Average-case
Citation
J. 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/0212046