An exact probability model for finite hash tables

Author

Ramakrishna, M.V.

Author_Institution

Dept. of Comput. Sci., Michigan State Univ., East Lansing, MI, USA

fYear

1988

fDate

1-5 Feb 1988

Firstpage

362

Lastpage

368

Abstract

The author presents an exact probability model for finite hash tables and applies the model to solve a few problems in the analysis of hashing techniques. The model enables exact computation of table sufficiency index, a parameter useful in the design of small hash tables. The author also presents an exact analysis of the expected length of the longest probe sequence in hashing with separate chaining, and successful search length in infinite uniform hashing giving explicit expressions. It appears that the model can be extended to analyze other hashing schemes such as bounded disorder index method, and to problems in robust data structures, etc

Keywords

data structures; file organisation; probability; table lookup; bounded disorder index method; exact computation; exact probability model; expected length; explicit expressions; finite hash tables; hashing techniques; infinite uniform hashing; longest probe sequence; robust data structures; separate chaining; successful search length; table sufficiency index; Computer science; Explosions; Mathematical model; Organizing; Performance analysis; Probes;

fLanguage

English

Publisher

ieee

Conference_Titel

Data Engineering, 1988. Proceedings. Fourth International Conference on

Conference_Location

Los Angeles, CA

Print_ISBN

0-8186-0827-7

Type

conf

DOI

10.1109/ICDE.1988.105480

Filename

105480