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 ______.

  1. A.

    46

  2. B.

    41

  3. C.

    43

  4. D.

    48

Attempted by 299 students.

Show answer & explanation

Correct answer: B

Key formula: h(K) = floor(m * frac(K * A)) where A = (sqrt(5) - 1)/2

  1. Evaluate A approximately: A = (sqrt(5) - 1)/2 β‰ˆ 0.6180339887498948.

  2. Compute K * A: 123456 * 0.6180339887498948 β‰ˆ 76300.00411512.

  3. Take the fractional part: frac(123456 * A) β‰ˆ 0.00411512.

  4. Multiply by m = 10000: 10000 * 0.00411512 β‰ˆ 41.150.

  5. Apply floor: floor(41.150) = 41. Therefore the key 123456 is mapped to location 41.

Explore the full course: Coding For Placement