Consider double hashing of the form \(h(k,i)=(h_1(k)+ih_2(k)) \text{mod m}\)…
2019
Consider double hashing of the form
\(h(k,i)=(h_1(k)+ih_2(k)) \text{mod m}\) where
\(h_{1}(k) = \text{k mod m} \ , \ \ h_{2}(k)=1+(\text{k mod n})\) where \(n=m-1\) and \(m=701\) . For \(𝑘=123456\), what is the difference between first and second probes in terms of slots?
- A.
255
- B.
256
- C.
257
- D.
258
Attempted by 126 students.
Show answer & explanation
Correct answer: C
Key calculations:
Given m = 701 and n = m - 1 = 700, and k = 123456.
Compute h1(k) = k mod m = 123456 mod 701 = 80.
Compute k mod n = 123456 mod 700 = 256.
Compute h2(k) = 1 + (k mod n) = 1 + 256 = 257.
Therefore the step (difference between the first and second probes) is h2 = 257 slots.
Answer: 257
A video solution is available for this question — log in and enroll to watch it.