Suppose we are given \(n \) keys, \(m \) hash table slots, and two simple…
2022
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}\)
Attempted by 415 students.
Show answer & explanation
Correct answer: B
Key idea: each key, regardless of using the first or second hash function, is mapped uniformly at random to one of the m slots.
Reasoning using linearity of expectation:
For a fixed slot, define an indicator variable for each key: 1 if the key hashes to that slot, 0 otherwise.
Each indicator has expected value 1/m because the hash functions are uniform.
Summing the expectations over all n keys gives the expected number of keys in the slot: n * (1/m) = n/m.
Note: Using separate hash functions for odd and even keys does not change the per-key probability of landing in a given slot, so it does not affect this expectation.
A video solution is available for this question — log in and enroll to watch it.