Consider a hash table of size m = 10000, and the hash function h(K) = floor…
2025
Consider a hash table of size m = 10000, and the hash function h(K) = floor (m(KA mod 1)) for A = (√5 – 1)/2. The key 123456 is mapped to location ______.
- A.
46
- B.
41
- C.
43
- D.
48
Attempted by 5 students.
Show answer & explanation
Correct answer: B
Concept: The multiplicative (Fibonacci) hashing method computes an index by multiplying the key by an irrational constant A in the interval (0, 1) — conventionally A = (√5 − 1)/2, the golden-ratio conjugate — keeping only the fractional part of k·A, then scaling that fraction up to the table size m and taking the floor: h(k) = floor(m·(k·A mod 1)). This spreads keys near-uniformly across the table regardless of patterns in k.
Application: For m = 10000, A = (√5 − 1)/2 ≈ 0.61803398875, and k = 123456:
Compute k·A = 123456 × 0.61803398875 ≈ 76300.0041151.
Take the fractional part: 76300.0041151 mod 1 = 0.0041151.
Scale by the table size: 10000 × 0.0041151 = 41.151.
Floor to the nearest integer below: floor(41.151) = 41.
Cross-check: The scaled value 41.151 sits comfortably inside the interval (41, 42), well away from an integer boundary, so recomputing A to even more decimal places (0.6180339887498949) still leaves the fractional part at 0.0041151 and the same floor of 41 — the result is stable.
Result: So, h(123456) = 41.