Consider a hashing function that resolves collision by quadratic probing .Assume the address space is indexed from $1$ to $6$. Which of the following locations will never be probed if a collision occurs at position $5$ ?
A). $4$
B). $5$
C). $8$
D). $6$
Ans:
$B$
Ans Explanation:
f(key) = key % $6+1$ $\rightarrow$ it locates from $1$ to $6$ collision
Quadratic probing $\rightarrow$ $(5+1^2) $%$ 6+1 =1$
$\rightarrow$ $(5+2^2) $%$ 6+1 =4$
$\rightarrow$ $(5+3^2) $%$ 6+1 =3$
$\rightarrow$ $(5+4^2) $%$ 6+1 =4$
$\rightarrow$ $(5+5^2) $%$ 6+1 =1$
$\rightarrow$ $(5+6^2) $%$ 6+1 = 6$
$\rightarrow$ $(5+7^2) $%$ 6+1 = 1$
$\rightarrow$ $(5+8^2) $%$ 6+1 = 4$
$\rightarrow$ $(5+9^2) $%$ 6+1 = 3$
so the $5^{th}$ location is never probed
Here why we are adding $1$ to find f(key)?