@Bikram Sir Why Mod 5 in 2nd and 3rd step??

Dark Mode

Bikram
asked
in Algorithms
Oct 4, 2016

433 views
1 vote

Consider a hash table of size $m = 10$ and a corresponding hash function $h(k) = k A \mod m$ for $A = 5$ where collisions are resolved by quadratic probing. The location (starting from 1) to which the key 65 is mapped if the current contents of hashtable is $4 \;8 \;\_ \;\_ \;7 \;8 \;6 \;\_\; 0\; \_$ is _______

6 votes

Best answer

Here, hash function $h(k)= kA\; \mod\; m$ and $A=5$, where collisions are resolved by quadratic probing.

Assuming, the $i^{th}$ probe position for a value $k$ is given by the function :

$h(k,i)= (kA + i^2)\; \mod \;m $ where $i = 1,2,3\ldots$

So,

$h (65,1) = (65*5 + 1^2)\; \mod\; 10 = 6$ but at this place key $6$ is present so probe next.

$h(65,2) = (65*5 + 2^2)\; \mod \;10 = 9$ yes this position is free. So, key $65$ should be mapped at $9^{th}$ position in the hash table. But since the location starts from $1,$ (as given in question description) this will be named as location $10.$

Answer: $10$

Assuming, the $i^{th}$ probe position for a value $k$ is given by the function :

$h(k,i)= (kA + i^2)\; \mod \;m $ where $i = 1,2,3\ldots$

So,

$h (65,1) = (65*5 + 1^2)\; \mod\; 10 = 6$ but at this place key $6$ is present so probe next.

$h(65,2) = (65*5 + 2^2)\; \mod \;10 = 9$ yes this position is free. So, key $65$ should be mapped at $9^{th}$ position in the hash table. But since the location starts from $1,$ (as given in question description) this will be named as location $10.$

Answer: $10$

@Vijay Thakur yes you are correct. 4 is the right answer. Also it is mentioned in question that location is starting from 1. Who chooses these wrong best answers?

0

@ankitgupta.1729 Please do not change any answer unless it is a typo or small correction. If you feel given answer is not correct you can give a new answer or write a comment. Those who answered will be really frustrated if someone edits their answer wrongly.

2

2 votes

INDEXING IN HASH TABLE STARTS FROM 0. Its slots would be from 0 to 9, that's how mod10 works. But *location* count starts from 1 as mentioned by the question.

325 mod 10 = 5. In index 5 => location 6, 8 is already present.

325 + 1 mod 10 = 6. In index 6, => location 7, 6 is already present.

325 + 4 mod 10 = 9. In index 9 => **location 10** the slot is empty. We can place it there.

The best answer here is correct, it writes mod5 in place of mod10, tho — probably a silly error.