Consider the formula for evaluating the number of hash table comparisons:
$ c=1 / 2^{(1+1 /(1-L))} $, where c = the number of comparisons and L = the load factor.
Given that a hash table of size 100,000 contains 20,000 items, how many comparisons are expected in a linear probe for an item?
A) .5
B) .625
C) 1.125
D) 3

Question

Quizplus · Accepted Answer

The load factor $L$ is calculated as the number of items in the hash table divided by the size of the hash table. In this case, $L = 20,000 / 100,000 = 0.2$. Substituting $L = 0.2$ into the formula $c = 1 / 2^{(1+1/(1-L))}$ gives $c = 1 / 2^{(1+1/(1-0.2))} = 1 / 2^{(1+1/0.8)} = 1 / 2^{(1+1.25)} = 1 / 2^{2.25} \approx 1.125$.

Consider the Formula for Evaluating the Number of Hash Table c=1/2(1+1/(1−L)) c=1 / 2^{(1+1 /(1-L))} c=1/2(1+1/(1−L))

Consider the Formula for Evaluating the Number of Hash Table $c=1 / 2^{(1+1 /(1-L))}$