167 views

Consider the following keys that are hashed into the hash table in the given order using the hash function H(key) = key mod 11.
12, 44, 13, 88, 23, 94, 11, 39, 20, 16, 21
Where hash table using quarditic probing of mod11 to handle the collisions, after inserting the above keys in table. Then find the number of keys cannot go inside the hash table ________ (value will be a whole number).

I can't understand what is "i"

is it number of collision?

in DS | 167 views
0
In quadratic probing if there is collision, then probing is done as H(key) + i², where i= 1,2,3.....
0
Means we'll just increment i by 1, it has nothing to do with collision?

And.   " H(key) + i² " is this standard formula for quadratic probing?or question will mention which formula to use.
0

If we have to count the no of collisions then simply calculate the H(key), we will get a location for this key, if there is already a key present there then it is a collision so now calculate H(key) + 1², we will get a new location in hash table if here also at this position a key is present then it is again a collsion, again calculate H(key) + 2², suppose this time we got empty slot so we will insert key into this collision, and in total we got 2 collsion for this key.

Similarly do this for rest of the keys too and yes H(key) + i² is standard formula

For more: