Data Structures, Algorithms, & Applications in C++
Chapter 10, Exercise 23

For this exercise we need to use the linear open addressing performance equations:


S_n = 1/2[1 + 1/(1 - alpha)]

U_n = 1/2[1 + 1/(1 - alpha)²]

where alpha is the loading density n/b. When the hash funstion is division, the divisor D equals the number of buckets b.

(a): Since S_n = 1/2[1 + 1/(1 - alpha)] <= 3, 1 - alpha >= 0.2.
Also, since U_n = 1/2[1 + 1/(1 - alpha)²] <= 20, 1 - alpha >= sqrt(1/39).
So 1 - alpha >= max{0.2, sqrt(1/39)} = 0.2.
Hence n/b = alpha <= 0.8 and so D = b >= n/0.8 = 50/0.8 = 62.5.

Since D should be a prime or should have no prime divisors less than 20, we choose D = 67, which is a prime number.
(b): Since S_n = 1/2[1 + 1/(1 - alpha)] <= 5, 1 - alpha >= 1/9.
Also, since U_n = 1/2[1 + 1/(1 - alpha)²] <= 60, 1 - alpha >= sqrt(1/119).
So 1 - alpha >= max{1/9, sqrt(1/119)} = 1/9.
Hence n/b = alpha <= 8/9 and so D = b >= 9n/8 = 9*500/8 = 562.5.

Since D should be a prime or should have no prime divisors less than 20, we choose D = 563, which is a prime number.
(c): Since S_n = 1/2[1 + 1/(1 - alpha)] <= 2, 1 - alpha >= 1/3.
Also, since U_n = 1/2[1 + 1/(1 - alpha)²] <= 10, 1 - alpha >= sqrt(1/19).
So 1 - alpha >= max{1/3, sqrt(1/19)} = 1/3.
Hence n/b = alpha <= 2/3 and so D = b >= 3n/2 = 3*10/2 = 15.

Since D should be a prime or should have no prime divisors less than 20, we choose D = 17, which is a prime number.