| x (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Consider the set H of all linear (or ane) transformations between two vector spaces over a nite eld 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 nite eld, but with respect to our measure dierent elds behave dierently. If the nite eld F has n elements then there is a bad set S F 2 of size n with expected maximal bucket size | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||