Optimum Algorithms for a Model of Direct Chaining

View/ Open
Issue Date
1985-05Author
Vitter, Jeffrey Scott
Chen, Wen-Chin
Publisher
Society for Industrial and Applied Mathematics
Type
Article
Article Version
Scholarly/refereed, publisher version
Metadata
Show full item recordAbstract
Direct chaining is a popular and efficient class of hashing algorithms. In this paper we study
optimum algorithms among direct chaining methods, under the restrictions that the records in the hash table are not moved after they are inserted, that for each chain the relative ordering of the records in the chain does not change after more insertions, and that only one link field is used per table slot. The varied-insertion coalesced hashing method (VICH), which is proposed and analyzed in [CV84], is conjectured to be optimum
among all direct chaining algorithms in this class. We give strong evidence in favor of the conjecture by showing that VICH is optimum under fairly general conditions.
Collections
Citation
J. S. Vitter and W.-C. Chen. “Optimum Algorithms for a Model of Direct Chaining,” SIAM Journal on Computing, 14(2), May 1985, 490–499. http://dx.doi.org/10.1137/0214036
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.