Analysis of Early-Insertion Standard Coalesced Hashing

View/ Open
Issue Date
1983Author
Chen, Wen-Chin
Vitter, Jeffrey Scott
Publisher
Society for Industrial and Applied Mathematics
Type
Article
Article Version
Scholarly/refereed, publisher version
Metadata
Show full item recordAbstract
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.
Collections
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
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.