Open AccessAnalysis of Early-Insertion Standard Coalesced Hashing
Author(s) -
WenChin Chen,
Jeffrey Scott Vitter
Publication year - 1983
Publication title -
siam journal on computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.533
H-Index - 122
eISSN - 1095-7111
pISSN - 0097-5397
DOI - 10.1137/0212046
Subject(s) - hash function , dynamic perfect hashing , consistent hashing , hash table , computer science , universal hashing , linear hashing , algorithm , perfect hash function , double hashing , programming language
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom