Introduction to Algorithms, Third Edition

universal hashing
, can yield provably
good performance on average, no matter which keys the adversary chooses.
In universal hashing, at the beginning of execution we select the hash function
at random from a carefully designed class of functions. As in the case of quick-
sort, randomization guarantees that no single input will always evoke worst-case
behavior. Because we randomly select the hash function, the algorithm can be-
have differently on each execution, even for the same input, guaranteeing good
average-case performance for any input. Returning to the example of a compiler’s
symbol table, we find that the programmer’s choice of identifiers cannot now cause
consistently poor hashing performance. Poor performance occurs only when the
compiler chooses a random hash function that causes the set of identifiers to hash
poorly, but the probability of this situation occurring is small and is the same for
any set of identifiers of the same size.
Let
H
be a finite collection of hash functions that map a given universe
U
of
keys into the range
f
0; 1; : : : ; m
1
g
. Such a collection is said to be
universal
if for each pair of distinct keys
k; l
2
U
, the number of hash functions
h
2
H
for which
h.k/
D
h.l/
is at most
j
H
j
=m
. In other words, with a hash function
randomly chosen from
H
, the chance of a collision between distinct keys
k
and
l
is no more than the chance
1=m
of a collision if
h.k/
and
h.l/
were randomly and
independently chosen from the set
f
0; 1; : : : ; m
1
g
.
The following theorem shows that a universal class of hash functions gives good
average-case behavior. Recall that
n
i
denotes the length of list
T Œi 
.