TY - JOUR
AU - Noga Alon
AU - Martin Dietzfelbinger
AU - Peter Miltersen
AU - Erez Petrank
AU - GĂˇbor Tardos
PY - 1997/01/16
Y2 - 2019/10/15
TI - Linear Hashing
JF - BRICS Report Series
JA - BRICS
VL - 4
IS - 16
SE - Articles
DO - 10.7146/brics.v4i16.18808
UR - https://tidsskrift.dk/brics/article/view/18808
AB - 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 sizen 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, butwith respect to our measure different fields behave differently.
ER -