Test by Bikram | Algorithms | Test 2 | Question: 29

Question

The given input sequence is $\{ 111, 333 , 243, 199, 234, 279, 119 \}$ and the hash table is of size $10$ with hash function $h(k) = k \mod 10$. When hash table uses quadratic probing with $h'(k)=  h(k) + c_1 * i + c_2 * i^2, c_1 = 0, c_2 = 1$, the total number of collisions happening while mapping the given input sequence are __________.

Answer 1

0	279
1	111
2
3	333
4	243
5	234
6
7
8	119
9	199

insert 111, 333 does not have any collision

insert 243 have one collision at index 3

insert 199 does not have any collision

insert 234 have one collision at index 4

insert 279 have one collision at index 9

insert 119 have three collision at index 9,0,3 

Comments

@Bikram sir,

In linear probing:   h'k = ( h(k) + c * i )     By default c=1.  In gate questions they do not mention it too.

Quad probing:  h'k= ( h(k) + c1 * i + c2 * i^2 )    Nothing is mentioned about c1 or c2 in this question.
It is never asked it GATE too.

So what is the default c1 & c2 values ?

Wiki has given example with both  (c1=0,c2=1)   &  (c1=1,c2=1)

---

No, there is not default value in quadratic probing, 

For m = 2ⁿ, a good choice for the constants are c₁ = c₂ = 1/2 .

For prime m > 2, good choices are : c₁ = c₂ = 1/2, c₁ = c₂ = 1, and c₁ = 0, c₂ = 1  possible. 

Read them :

https://stackoverflow.com/questions/15670712/quadratic-probing

https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/tables/quadratic_probing_and_double_hashing.html

---

@Bikram sir thank you.
But it should be mentioned.  Otherwise answer will be different.

---

so that means we have to evaluate the no of collisions according to the value of c1 and c2 and choose those pair of c1 and c2 that results in min collisions? because in the above question if we choose c1=c2=1 then for insertion of 279 we would get more than 1 collision?

---

@Ahwan

yes, it should be mentioned . ( in  exam this value should be given as there is no default in quadratic probing )

Now is this fine, see the question. I add the value.

---

@Bikram Sir, Now it is fine. Thank you.

---

how can it collide at 3rd index? can anyone explain ?