Dispersing Hash Functions

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