Closed Hashing is Computable and Optimally Randomizable with Universal Hash Functions

Abstract

We have shown that in double hashing, a universal family of hash functions, that with high probability provides (c)log(n)-wise independence, will give optimal performance for any fixed load bound below 1. The notion of double hashing is generalized to include almost any reasonable probe scheme. Similarly, linear probing incurs no loss of performance when such hash functions are used. These optimality results apply to the expected [r]-th moment of the probe count, for any fixed [r]. Our proof technique analyzed local and global hashing interactions separately, and used analytic tools to measure complicated but weakly correlated events in terms of simpler independent processes. Bundling and thinning techniques were used to eliminate (spurious) combinatorial explosions from more nave counting formulations. Surely these methods can be applied to other probabilistic process that exhibit weak correlation or that might only be supported by a source of limited randomness.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1995
Accession Number
AD1020223

Entities

People

  • Alan Siegel
  • Jeanette P. Schmidt

Organizations

  • Courant Institute of Mathematical Sciences, NYU

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Explosions
  • Probability

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Mathematical Modeling and Probability Theory.