Thumbnail Image
Publication

Analysis of Early-Insertion Standard Coalesced Hashing

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
Collections
Provost Office Published Articles
Distinguished Professors Scholarly Works
Electrical Engineering and Computer Science Scholarly Works
Show all metadata
Files
Thumbnail Image
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
URI
https://hdl.handle.net/1808/7169
DOI
10.1137/0212046
Embedded videos