A probability model for overflow sufficiency in small hash tables

For hash tables in which a strict physical separation exists between primary storage and storage for overflow records, with bucket capacity at least three, a complete probability model is described. A measure of hash table efficiency is introduced, called the table sufficiency index (TSI), and defined as the probability that the overflow space is sufficient assuming that the set of hashed keys has a uniform distribution. The constructed probability model may be used to compute the TSI for hash tables with parameters chosen from a restricted domain. The TSI is advocated as a tool for making decisions about the parameters of small hash tables.

View this article in the ACM Digital Library.