Consider a hash table of size m = 100 and the hash function h(k) = floor (m(kA…
2015
Consider a hash table of size m = 100 and the hash function h(k) = floor (m(kA mod 1)) for \(A=\frac{ (\sqrt{5}-1)}{2} = 0.618033\). Compute the location to which the key k = 123456 is placed in hash table.
- A.
77
- B.
82
- C.
88
- D.
89
Attempted by 306 students.
Show answer & explanation
Correct answer: C
Key formula: h(k) = floor(m × fractional_part(k × A)).
Given A = (√5 − 1)/2 ≈ 0.618033 and table size m = 100.
Compute k × A: 123456 × 0.618033 ≈ 76299.882048.
Take the fractional part: fractional_part(k × A) ≈ 0.882048.
Multiply by m: 100 × 0.882048 = 88.2048.
Apply floor: floor(88.2048) = 88.
Therefore the key 123456 is placed at index 88 in the hash table.