Redirected
edited by
1,578 views
1 votes
1 votes

Suppose we are implementing quadratic probing with a Hash function, Hash $(y)=X$ mode $100$. If an element with key $4594$ is inserted and the first three locations attempted are already occupied, then the next cell that will be tried is :

  1. $2$
  2. $3$
  3. $9$
  4. $97$
edited by

3 Answers

Best answer
5 votes
5 votes

The quadratic hash function for key value $k$ at $i^{th}$ probe sequence is given by

$h(k, i)$ = $(h(k) + c_{1}.i + c_{2}.i^2)$  $mod$  $m$

Where $i = 0, 1, 2, 3.........$ and

$c_{2} ≠ 0$ (since it will degrade to linear probing) so in general we take $c_{2} = 1$ and also

$h(k) = k$ $mod$ $m$

in our case $h(k) = 4594$ $mod$ $100 = 94$

now the value of $h(k , i)$ depends upon $c_{1}$

If we take $c_{1} = 0$ the corresponding probe sequence will be

$h(4594, 0)$ = $(94 + 0•0 + 1•0^2)$ $mod$ 100 = 94 (already occupied)

$h(4594, 1)$ = $(94 + 0•1 + 1•1^2)$ $mod$ 100 = 95 (already occupied)

$h(4594, 2)$ = $(94 + 0•2 + 1•2^2)$ $mod$ 100 = 98 (already occupied)

$h(4594, 3)$ = $(94 + 0•3 + 1• 3^2)$ $mod$ 100 = (103)  $mod$ 100 = 3 (which matches our options)

now if we take different value for $c_{1}$ and $c_{2}$ we get different probe sequences

For example if we take $c_{1} = 1$ & $c_{2} = 1$ , the probe sequence we get is 94, 96, 0, 6... (6 not in option)

In wikipedia they have taken quadratic function as $h(k, i)$ = H + $i^{2}$

Where H = k mod m and  i = 0, 1, 2, 3,.....

https://en.m.wikipedia.org/wiki/Quadratic_probing

When we take $c_{1} =0$ & $c_{2} = 1$ , we get the same fuction.

selected by
0 votes
0 votes
$$\text{QuadraticProbing(key, i) = } [HashFunction(key)+i^2 ]mod \space m$$

Given, $HashFunction = X mod  100$, and 3 attempts ($i$) have been failed.

$QuadraticProbing(4594, 0) = [4594 mod 100 +0^2 ]mod \space 100$   (failed)

$QuadraticProbing(4594, 1) = [4594 mod 100 +1^2 ]mod \space 100$   (failed)

$QuadraticProbing(4594, 2) = [4594 mod 100 +2^2 ]mod \space 100$    (failed)

$QuadraticProbing(4594, 3) = [4594 mod 100 +3^2 ]mod \space 100  =  103 mod 100 = 3 $ (answer)

Related questions

2 votes
2 votes
2 answers
1
go_editor asked Mar 27, 2020
863 views
Which of the following is not collision resolution technique?Hash addressingChainingBoth (A) and (B)Indexing
0 votes
0 votes
2 answers
2
go_editor asked Mar 26, 2020
1,027 views
What item is at the root after the following sequence of insertions into an empty splay tree :$1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2, ?$$1$$2$$4$$8$
1 votes
1 votes
1 answer
3
go_editor asked Mar 26, 2020
1,285 views
What operation is supported in constant time by the doubly linked list, but not by the singly linked list ?AdvanceBackupFirstRetrieve
0 votes
0 votes
2 answers
4
go_editor asked Mar 27, 2020
3,760 views
Code optimization is responsibility of :Application programmerSystem programmerOperating systemAll of the above