Double Hashing is Computable and Randomizable with Universal Hash Functions

Abstract

Universal has functions that exhibit c log n-wise independence are shown to give a performance in double hashing and virtually any reasonable generalization of double hashing that has an expected probe count of (1)/1-alpha + epsilon for the insertion of the alpha-th item into a table of size n, for any fixed alpha less than 1 and epsilon greater than 0. This performance is within epsilon of optimal. These results are derived from a novel formulation that overestimates the expected probe count by underestimating the presence of partial items already inserted into the hash table, and from a sharp analysis of the underlying stochastic structures formed by colliding items.

Open PDF

Document Details

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

Entities

People

  • Alan Siegel
  • Jeanette P. Schmidt

Organizations

  • Courant Institute of Mathematical Sciences, NYU

Tags

DTIC Thesaurus Topics

  • Digital Information
  • Geometry
  • Hash Tables
  • Mathematics
  • Three Dimensional

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Computer Vision.
  • Graph Algorithms and Convex Optimization.
  • Regression Analysis.