If we store n keys in a hash table of size m = n² using a hash function h randomly chosen from a universal class of hash functions, then the probability of there being any collisions is less than 1/2.

Proof There are pairs of keys that may collide; each pair collides with probability 1/m if h is chosen at random from a universal family ℋ of hash functions. Let X be a random variable that counts the number of collisions. When m = n², the expected number of collisions is

(Note that this analysis is similar to the analysis of the birthday paradox in Section 5.4.1.) Applying Markov's inequality (C.29), Pr{X ≥ t} ≤ E[X] /t, with t = 1 completes the proof.

If we store n keys in a hash table of size m = n using a hash function h randomly chosen from a universal class of hash functions, then

where n_j is the number of keys hashing to slot j.

Proof We start with the following identity, which holds for any nonnegative integer a:

(11.6)

We have

To evaluate the summation , we observe that it is just the total number of collisions. By the properties of universal hashing, the expected value of this summation is at most

since m = n. Thus,

If we store n keys in a hash table of size m = n using a hash function h randomly chosen from a universal class of hash functions and we set the size of each secondary hash table to for j = 0, 1, ..., m - 1, then the expected amount of storage required for all secondary hash tables in a perfect hashing scheme is less than 2n.

Proof Since for j = 0, 1, ..., m - 1, Theorem 11.10 gives

(11.7)

which completes the proof.

If we store n keys in a hash table of size m = n using a hash function h randomly chosen from a universal class of hash functions and we set the size of each secondary hash table to for j = 0, 1, ..., m - 1, then the probability that the total storage used for secondary hash tables exceeds 4n is less than 1/2.

Proof Again we apply Markov's inequality (C.29), Pr {X ≥ t} ≤ E [X] /t, this time to inequality (11.7), with and t = 4n:

Suppose that we insert n keys into a hash table of size m using open addressing and uniform hashing. Let p(n, m) be the probability that no collisions occur. Show that p(n, m) ≤ e^-n(n-1)/2m. (Hint: See equation (3.11).) Argue that when n exceeds , the probability of avoiding collisions goes rapidly to zero.

A hash table of size m is used to store n items, with n ≤ m/2. Open addressing is used for collision resolution.

1. Assuming uniform hashing, show that for i = 1, 2, ..., n, the probability that the ith insertion requires strictly more than k probes is at most 2^-k.

2. Show that for i = 1, 2, ..., n, the probability that the ith insertion requires more than 2 lg n probes is at most 1/n².

Let the random variable X_i denote the number of probes required by the ith insertion. You have shown in part (b) that Pr {X_i > 2lg n} ≤ 1/n². Let the random variable X = max_1≤i≤n X_i denote the maximum number of probes required by any of the n insertions.

3. Show that Pr{X > 2lg n} ≤ 1/n.

4. Show that the expected length E[X] of the longest probe sequence is O(lg n).

Suppose that we have a hash table with n slots, with collisions resolved by chaining, and suppose that n keys are inserted into the table. Each key is equally likely to be hashed to each slot. Let M be the maximum number of keys in any slot after all the keys have been inserted. Your mission is to prove an O(lg n/lg lg n) upper bound on E[M], the expected value of M.

1. Argue that the probability Q_k that exactly k keys hash to a particular slot is given by

   

2. Let P_k be the probability that M = k, that is, the probability that the slot containing the most keys contains k keys. Show that P_k ≤ nQ_k.

3. Use Stirling's approximation, equation (3.17), to show that Q_k < e^k/k^k.

4. Show that there exists a constant c > 1 such that for k₀ = clg n/ lg lg n. Conclude that P_k < 1/n^2< for k ≥ k₀ = c lg n/ lg lg n.

5. Argue that

   

   Conclude that E[M] = O(lg n/ lg lg n).

Suppose that we are given a key k to search for in a hash table with positions 0, 1, ..., m - 1, and suppose that we have a hash function h mapping the key space into the set {0, 1, ..., m - 1}. The search scheme is as follows.

1. Compute the value i ← h(k), and set j ← 0.

2. Probe in position i for the desired key k. If you find it, or if this position is empty, terminate the search.

3. Set j ← (j + 1) mod m and i ← (i + j) mod m, and return to step 2.

Assume that m is a power of 2.

1. Show that this scheme is an instance of the general "quadratic probing" scheme by exhibiting the appropriate constants c₁ and c₂ for equation (11.5).

2. Prove that this algorithm examines every table position in the worst case.

Let ℋ = {h} be a class of hash functions in which each h maps the universe U of keys to {0, 1, ..., m - 1}. We say that ℋ is k-universal if, for every fixed sequence of k distinct keys 〈x⁽¹⁾, x⁽²⁾, ..., x^(k)〉 and for any h chosen at random from ℋ, the sequence 〈h(x⁽¹⁾), h(x⁽²⁾), ..., h(x^(k))〉 is equally likely to be any of the m^k sequences of length k with elements drawn from {0, 1, ..., m - 1}.

1. Show that if ℋ is 2-universal, then it is universal.

2. Let U be the set of n-tuples of values drawn from Z_p, and let B = Z_p, where p is prime. For any n-tuple a = 〈a₀, a₁, ..., a_n-1〉 of values from Z_p and for any b ∈ Z_p, define the hash function h_a,b : U → B on an input n-tuple x = 〈x₀, x₁, ..., x_n-1〉 from U as

   

   and let ℋ = {h_a,b}. Argue that ℋ is 2-universal.

3. Suppose that Alice and Bob agree secretly on a hash function h_a,b from a 2-universal family ℋ of hash functions. Later, Alice sends a message m to Bob over the Internet, where m ∈ U . She authenticates this message to Bob by also sending an authentication tag t = h_a,b(m), and Bob checks that the pair (m, t) he receives satisfies t = h_a,b(m). Suppose that an adversary intercepts (m, t) en route and tries to fool Bob by replacing the pair with a different pair (m', t'). Argue that the probability that the adversary succeeds in fooling Bob into accepting (m', t') is at most 1/p, no matter how much computing power the adversary has.