Dispersing Hash Functions

Rasmus Pagh


A new hashing primitive is introduced: dispersing hash functions. A family
of hash functions F is dispersing if, for any set S of a certain size and random
h in F, the expected value of |S|−|h[S]| is not much larger than the expectancy
if h had been chosen at random from the set of all functions.
We give tight, up to a logarithmic factor, upper and lower bounds on the
size of dispersing families. Such families previously studied, for example
universal families, are significantly larger than the smallest dispersing families,
making them less suitable for derandomization. We present several applications
of dispersing families to derandomization (fast element distinctness, set
inclusion, and static dictionary initialization). Also, a tight relationship
between dispersing families and extractors, which may be of independent interest,
is exhibited.
We also investigate the related issue of program size for hash functions
which are nearly perfect. In particular, we exhibit a dramatic increase in
program size for hash functions more dispersing than a random function.

Full Text:


DOI: http://dx.doi.org/10.7146/brics.v7i36.20171
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.

ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library