Analysis of Early-Insertion Standard Coalesced Hashing

Chen, Wen-Chin; Vitter, Jeffrey Scott

View/Open

Vitter_1983.pdf (1.016Mb)

Issue Date

1983

Author

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 record

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.

URI

http://hdl.handle.net/1808/7169

DOI

https://doi.org/10.1137/0212046

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

The University of Kansas prohibits discrimination on the basis of race, color, ethnicity, religion, sex, national origin, age, ancestry, disability, status as a veteran, sexual orientation, marital status, parental status, gender identity, gender expression and genetic information in the University’s programs and activities. The following person has been designated to handle inquiries regarding the non-discrimination policies: Director of the Office of Institutional Opportunity and Access, IOA@ku.edu, 1246 W. Campus Road, Room 153A, Lawrence, KS, 66045, (785)864-6414, 711 TTY.