Analysis of Uniform Hashing

Umform hashing or random probing is often used as a theoretical model of certain types of hashing schemes based on open addressmg, and, m pamcular, of double hashing. Earlier analyses of umform hashing are extended here to multlrecord buckets. Three different situations are analysed: initial loadmg assuming uniform access frequencies, frequency loading assuming nonuniform access frequencies, and the dynamic behavior when msertions and deletions occur. Stmple "closed" formulas cannot be found, but numerical results are readily computed. For larger bucket sizes the retrieval performance is signdicanfly better than that of linear probing and separate chaining Hence double hashing and similar techniques are competmve alternatives also for organizing externally stored files.