| x (2007) | |||||||||||||
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. If the finite field F has n elements then there is a bad set S ae F 2 of size n with expected maximal bucket size\Omega\Gamma n | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||