AbstractConsider 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., Petrank, E., & Tardos, G. (1997). Linear Hashing. BRICS Report Series, 4(16). https://doi.org/10.7146/brics.v4i16.18808
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.