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 the given hashing scheme, there are \( n \) keys and \( m \) hash table slots. Keys are divided based on parity (even/odd) and mapped using two hash functions \( h_1 \) and \( h_2 \). Both hash functions are assumed to distribute keys uniformly and independently over the \( m \) slots.

Key observation:
Even though two different hash functions are used, the overall placement of keys across the hash table remains uniform because: - Each key is assigned to exactly one slot. - All slots are equally likely to receive any given key.

Expected number of keys per slot:
The expected load of a slot is given by: \[ \text{Expected keys per slot} = \frac{\text{Total number of keys}}{\text{Total number of slots}} = \frac{n}{m} \] This expectation does not change due to the use of multiple hash functions, as long as the distribution remains uniform.

Final Answer:
The expected number of keys in a hash table slot is: \[ \boxed{\frac{n}{m}} \] which corresponds to Option (B).