Computing the probability of hash table/urn overflow
- 1 January 1987
- journal article
- research article
- Published by Taylor & Francis in Communications in Statistics - Theory and Methods
- Vol. 16 (11) , 3343-3353
- https://doi.org/10.1080/03610928708829574
Abstract
We analyze the probability of a random distribution of n balls into m urns of size b resulting in no overflows. This solves the computational problem associated with a classical combinatorial extreme-value distribution. The problem arose during the analysis of a technique, called perfect hashing, for organizing data in computer files. The results and techniques presented can be used to solve several problems in the analysis of hashing techniquesKeywords
This publication has 4 references indexed in Scilit:
- A probability model for overflow sufficiency in small hash tablesCommunications of the ACM, 1985
- Analysis of Uniform HashingJournal of the ACM, 1983
- Combinatorial Chance.Economica, 1962
- Combinatorial extreme value distributionsMathematika, 1959