Quadratic probing

Question

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)?

Answer 1

Because address space is indexed from 1 to 6. If you get 0 after some modulus operation and you don't have zero as any location. Therefore, 1 is added.

Comments

How can one assume this

f(key) = key % 6+16+1

?

It should be given in question what hash function is being used.. 

---

But in the solution,it is given like that..

But usually when collision occurs,In quadratic probing we  move i² slots from the point of collision..

---

Arjun sir, but quadratic formula is h'(key)=(h(key)+i+i²)mod N. Why we are taking only i². Assume constants multiplier C1 and C2 are 1.