Description
1. A family H of hash functions from a universe U to {0, . . . , m − 1} is 3-universal if, for all
distinct x1, x2, x3 ∈ U and all y1, y2, y3 ∈ {0, . . . , m − 1},
Probh∈H[h(x1) = y1, h(x2) = y2, and h(x3) = y3] = 1
m3
(a) Prove that any 3-universal family of hash functions is universal.
(b) Prove that if U = {0, . . . , m−1} and m is prime, then the family H = {ha,b,c | a, b, c ∈ U}
is 3-universal, where ha,b,c(x) = ax2 + bx + c mod m.
2. In this question, you will construct a data structure that supports hashing with chaining
using a hash function h chosen from a universal family of hash functions from a universe U
to [1..m] using only a table T of size m to store any set S ⊆ U of size at most m. You may
also use a constant number of additional words of memory.
Each of the m slots of T contains a bit, b, indicating whether or not the slot is storing an
element of S. If the bit is 1, the slot also contains one of the elements, v, of S and a value,
w, in {0, . . . , m}. If not, the slot also contains two values, v and w, each in {0, . . . , m}.
(a) Briefly describe your data structure.
(b) Draw a picture of your data structure for m = 5, the hash function h(x) = (x mod 5)+ 1
and the set S = {2, 7, 8}.
(c) How should T be initialized, assuming that S is initially empty?
(d) For any given x ∈ U, explain how to perform INSERT(x) in O(1) worst-case expected
time. You may assume as a precondition that x 6∈ S.
(e) For any given x ∈ U, explain how to perform DELETE(x) in O(1) worst-case expected
time.
(f) For any given x ∈ U, explain how to perform SEARCH(x) in O(1) worst-case expected
time.
1
