Consider a hash table of size \(𝑚=10000\), and the hash function \(h(K) =…
2016
Consider a hash table of size \(𝑚=10000\), and the hash function \(h(K) = floor (m(KA \bmod 1))\) for \(A = ( \sqrt{5} – 1)/2\). The key 123456 is mapped to location ______.
Answer: B. 41 — Key formula: h(K) = floor(m * frac(K * A)) where A = (sqrt(5) - 1)/2 Evaluate A approximately: A = (sqrt(5) - 1)/2 ≈ 0.6180339887498948. Compute K * A: 123456…
- A.
46
- B.
41
- C.
43
- D.
48
Attempted by 369 students.
Show answer & explanation
Correct answer: B
Key formula: h(K) = floor(m * frac(K * A)) where A = (sqrt(5) - 1)/2
Evaluate A approximately: A = (sqrt(5) - 1)/2 ≈ 0.6180339887498948.
Compute K * A: 123456 * 0.6180339887498948 ≈ 76300.00411512.
Take the fractional part: frac(123456 * A) ≈ 0.00411512.
Multiply by m = 10000: 10000 * 0.00411512 ≈ 41.150.
Apply floor: floor(41.150) = 41. Therefore the key 123456 is mapped to location 41.