Linear Hashing


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



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.




How to Cite

Alon, N., Dietzfelbinger, M., Miltersen, P. B., Petrank, E., & Tardos, G. (1997). Linear Hashing. BRICS Report Series, 4(16).