Question

Suppose you have a collision resolution scheme that jumps ahead three positions after each collision rather than one position as you do with linear probing. What would be a poor choice, in general terms, for the size of the hash table? Justify your answer with an example.

Answer 1

As we aware about what is collision in hash table, it happens when same value we try to put in one cell of hash table.

So to solve this Here collision resolution scheme is defined as to jumps ahead of three position after each collision rathen then one position.

So, besically the function is : whenever [(hash(x))%HASHTABLE_SIZE] is full.we will use.

[(hash(x) + 3)%HASHTABLE_SIZE] instead of [(hash(x) + 1)%HASHTABLE_SIZE] 

Here poor choice for HASHTABLE_SIZE can be following.

So, Data to insert into hash table is : 50, 700, 76, 85

and HASHTABLE_SIZE = 4

so, let's insert one by one into table.

index	HASHTABLE
0	700
1	85
2	50
3	76-->collide at index 0

1. So, Form Here we have learnt that HASHTABLE_SIZE should be >3 always to utilize this function.

Now moving forward.

2. This may suffer with Primary Clustering Problem.

3. Always HASHTABLE_SIZE should be greater than total no of keys in data.