Consider performing uniform hashing on an open address hash table with load…

Consider performing uniform hashing on an open address hash table with load factor α=nm<1\alpha = \frac{n}{m} < 1 , where 𝑛 elements are stored in the table with 𝑚 slots. The expected number of probes in an unsuccessful search is at most 11−α\frac{1}{1 - \alpha} . Inserting an element in this hash table requires at most ______ probes, on average.

  1. A.

    ln⁡(11−α)\ln\left(\frac{1}{1 - \alpha}\right)

  2. B.

    11−α\frac{1}{1 - \alpha}

  3. C.

    1+α21 + \frac{\alpha}{2}

  4. D.

    11+α\frac{1}{1 + \alpha}

Attempted by 438 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…