Question

Suppose we are given \(n\) keys, \(m\) hash table slots, and two simple uniform hash functions \(h_1\) and \(h_2\). Further suppose our hashing scheme uses \(h_1\) for the odd keys and \(h_2\) for the even keys. What is the expected number of keys in a slot?

• A. \( \frac{m}{n} \)
• B. \( \frac{n}{m} \)
• C. \( \frac{2n}{m} \)
• D. \( \frac{n}{2m} \)

Hint:

In hashing schemes with uniform distribution, the expected number of keys per slot is simply the total number of keys divided by the number of slots.

Answer 1

The Correct Option is B

In this hashing scheme, the \(n\) keys are uniformly distributed across \(m\) hash table slots, with keys being assigned to different hash functions based on their parity. Each hash function \(h_1\) and \(h_2\) independently maps keys to hash slots. This results in a uniform distribution of keys across the hash slots.
Thus, the expected number of keys per slot is the total number of keys divided by the number of slots, which is \( \frac{n}{m} \). Hence, the expected number of keys in a slot is \( \frac{n}{m} \), which corresponds to (B).