Universal Hashing - Mathematical Guarantees

Mathematical Guarantees

For any fixed set of keys, using a universal family guarantees the following properties.

1. For any fixed in, the expected number of keys in the bin is . When implementing hash tables by chaining, this number is proportional to the expected running time of an operation involving the key (for example a query, insertion or deletion).
2. The expected number of pairs of keys in with that collide is bounded above by, which is of order . When the number of bins, is, the expected number of collisions is . When hashing into bins, there are no collisions at all with probability at least a half.
3. The expected number of keys in bins with at least keys in them is bounded above by . Thus, if the capacity of each bin is capped to three times the average size, the total number of keys in overflowing bins is at most . This only holds with a hash family whose collision probability is bounded above by . If a weaker definition is used, bounding it by, this result is no longer true.

As the above guarantees hold for any fixed set, they hold if the data set is chosen by an adversary. However, the adversary has to make this choice before (or independent of) the algorithm's random choice of a hash function. If the adversary can observe the random choice of the algorithm, randomness serves no purpose, and the situation is the same as deterministic hashing.

The second and third guarantee are typically used in conjunction with rehashing. For instance, a randomized algorithm may be prepared to handle some number of collisions. If it observes too many collisions, it chooses another random from the family and repeats. Universality guarantees that the number of repetitions is a geometric random variable.