Discussion
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?
Answer: B
The expected number of keys in a slot is \(\frac{n}{m}\).
Simple uniform hashing means each key lands in any given slot with probability \(\frac{1}{m}\), whichever of the two functions hashes it. Using \(h_{1}\) for odd keys and \(h_{2}\) for even keys does not change that probability, so by linearity of expectation a slot receives
\[ n \cdot \frac{1}{m} = \frac{n}{m} \]
keys on average. Equivalently, if half the keys are odd, each half contributes \(\frac{n}{2m}\), and the two halves add to \(\frac{n}{m}\). \(\frac{n}{2m}\) counts only one half, \(\frac{2n}{m}\) double-counts, and \(\frac{m}{n}\) is the reciprocal of the load factor.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development