Linear Hashing

  • Noga Alon
  • Martin Dietzfelbinger
  • Peter Bro Miltersen
  • Erez Petrank
  • Gábor Tardos

Abstract

Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F. We study how good H is as a class of hash functions, namely we consider hashing a set S of size
n into a range having the same cardinality n by a randomly chosen function from H and look at the expected size of the largest hash bucket. H is a universal class of hash functions for any finite field, but
with respect to our measure different fields behave differently.
Published
1997-01-16
How to Cite
Alon, N., Dietzfelbinger, M., Miltersen, P., Petrank, E., & Tardos, G. (1997). Linear Hashing. BRICS Report Series, 4(16). https://doi.org/10.7146/brics.v4i16.18808