An exact probability model for finite hash tables
- 6 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 362-368
- https://doi.org/10.1109/icde.1988.105480
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
This publication has 12 references indexed in Scilit:
- File organization using composite perfect hashingACM Transactions on Database Systems, 1989
- Computing the probability of hash table/urn overflowCommunications in Statistics - Theory and Methods, 1987
- A probability model for overflow sufficiency in small hash tablesCommunications of the ACM, 1985
- External perfect hashingPublished by Association for Computing Machinery (ACM) ,1985
- The analysis of linear probing sort by the use of a new mathematical transformJournal of Algorithms, 1984
- Analysis of Uniform HashingJournal of the ACM, 1983
- Analysis of the Search Performance of Coalesced HashingJournal of the ACM, 1983
- Expected Worst-case Performance of Hash FilesThe Computer Journal, 1982
- Expected Length of the Longest Probe Sequence in Hash Code SearchingJournal of the ACM, 1981
- Perfect hashing functionsCommunications of the ACM, 1977