Optimum Algorithms for a Model of Direct Chaining | Zendy

Jeffrey Scott Vitter | Zendy; Wen-Chin Chen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Optimum Algorithms for a Model of Direct Chaining

Author(s) -

Jeffrey Scott Vitter,

Wen-Chin Chen

Publication year - 1985

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/0214036

Subject(s) - chaining , hash table , linear hashing , hash function , algorithm , computer science , class (philosophy) , table (database) , conjecture , dynamic perfect hashing , chain (unit) , consistent hashing , cardinality (data modeling) , perfect hash function , mathematics , discrete mathematics , double hashing , data mining , programming language , artificial intelligence , physics , psychology , astronomy , psychotherapist

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research