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 defin...

Full description

Saved in:
Bibliographic Details
Published in:Communications of the ACM 1985-10, Vol.28 (10), p.1068-1075
Main Authors: NORTON, R. M, YEAGER, D. P
Format: Magazinearticle
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Memory and file management (including protection and security)
Memory organisation. Data processing
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0001-0782
1557-7317
DOI:10.1145/4372.4377