708 views
1 votes
1 votes
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 _______

2 Answers

Best answer
6 votes
6 votes
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
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

3 votes
3 votes
2 answers
2
Bikram asked Oct 4, 2016
678 views
Is the following implementation of hashCode() legal assming a hashtable of size 20?public int hashCode(x) { return 17; }yesno because it fills only one slotno because it ...
2 votes
2 votes
2 answers
3
Bikram asked Oct 4, 2016
347 views
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___