LCS Publication Details
Publication Title: OPTIMAL ARRANGEMENT OF KEYS IN A HASH TABLE
Publication Author: Rivest, Ronald L.
Additional Authors:
LCS Document Number: MIT-LCS-TM-073
Publication Date: 7-1-1976
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
When open addressing is used to resolve collisions in a hash table, a given set of keys may be arranged in many ways; typically this depends on the order in which the keys are inserted. We show that arrangements minimizing either the average or worst-case number of probes required to retrieve any key in the table can be found using an algorithm for the assignment problem.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.