in Algorithms
746 views
1 vote
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 _______
in Algorithms
by
746 views

1 comment

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

0
0

2 Answers

6 votes
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$
edited by

4 Comments

@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
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

@Arjun sir, sorry. Yes, I edited wrongly. I will take care of these things next time.

1
1
2 votes
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.

Answer:

Related questions