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

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