Question

Give an example of a probe sequence produced by quadratic probing that does not reach the entire hash table, even if the size of the table is a prime number.

Answer 1

Let the size of the hash table be 7.

The input sequence be : 1 4 8 15 10 22

Index	Key
0
1	1
2	8
3	10
4	4
5	15
6

In the above hash table, first 1 is inserted.

hash(1) = 1 mod 7 = 1 and the element is at index 1 in the hash table.

The next element inserted is 4.

hash(4) = 4 mod 7 = 4  and the element is at index 4 in the hash table.

The next element inserted is 8.

hash(8) = 8 mod 7 = 1 but index 1 is already filled up in the hash table.

So, apply quadratic hashing for i^2 = 1^2

hash(8) = (( 8 mod 7 ) + 1) mod 7 = 2 and so, 8 is inserted at index 2.

The next element to be inserted is 15.

hash(15) = 15 mod 7 = 1

but index 1 is already filled up in the hash table.

So, apply quadratic hashing for i^2 = 1^2

hash(15) = (( 15 mod 7 ) + 1) mod 7 = 2 but index 2 is also filled up.

Apply quadratic hashing for i^2 = 2^2 = 4

hash(15) = (( 15 mod 7 ) + 4) mod 7 = 5 and so, 15 is inserted at index 5.

The next element to be inserted is 10.

hash(10) = 10 mod 7 = 3 and the key 10 is placed at index 3.

The next element to be inserted is 22.

hash(22) = 22 mod 7 = 1

but index 1 is already filled up in the hash table.

So, apply quadratic hashing for i^2 = 1^2

hash(22) = (( 22 mod 7 ) + 1) mod 7 = 2 but index 2 is also filled up.

Apply quadratic hashing for i^2 = 2^2 = 4

hash(22) = (( 22 mod 7 ) + 4) mod 7 = 5 but index 5 is already filled up.

Apply quadratic hashing for i^2 = 3^2 = 9

hash(22) = (( 22 mod 7 ) + 9) mod 7 = 3 but index 3 is already filled up.

So, to check key 22 is suffering from secondary clusterting or not, let there be the following table :

i^2 for i = 0,1,2 ..	0	1	4	9	16	25	36	49	63	81	100	121	144	169	196
((22 mod 7) + i )	1	2	5	10	17	26	37	50	64	82	101	122	145	170	197
((22 mod 7) + i ) mod 7	1	2	5	3	3	5	2	1	2	5	3	3	5	2	1
Is index empty	False	False	False	False	False	False	False	False	False	False	False	False	False	False	False

It can be seen from the above table that the value of ( ((22 mod 7) + i ) mod 7 ) is following a pattern as :

1 2 5 3 3 5 2 1 2 5 3 3 5 2 1

This means the quadratic probing wants 22 to be placed in either 1,2 ,3 or 5. But all the 4 places have been filled up and the other empty spaces would remain unutilized. This is a phenomenon known as secondary clustering which is the disadvantage of quadratic probing. Hence, the value 22 does not reach the entire hash table.