The Gateway to Computer Science Excellence
0 votes
137 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 by Active (1.4k points) | 137 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:

https://www.geeksforgeeks.org/hashing-set-3-open-addressing/

1 Answer

0 votes
no. of keys= 0
by (189 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,654 questions
56,170 answers
193,882 comments
94,311 users