in DS edited by
1,568 views
1 vote
1 vote

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$
in DS edited by
1.6k views

1 comment

c. 9
0
0

3 Answers

5 votes
5 votes
Best answer

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
by

1 comment

Nice explanation. Though, Proper details must have been given in the Question itself. At different places (different authors) Quadratic function is described in little bit different way.. As the first one that you described is in Cormen and Second one is from Wikipedia. So, Question is incomplete.

Kya foonk ke question set karte hain examiners kabhi kabhi..
2
2
0 votes
0 votes

http://ice-web.cc.gatech.edu/ce21/1/static/audio/static/pythonds/SortSearch/Hashing.html

Quadratic Probing adds 1, 3, 5, 7, 9, ..... (odd numbers) to the obtained hash upon each failed access and rehashes.

So,

1. 4594 % 100 = 94 (failed)

2. (94+1) % 100 = 95 (failed)

3. (95+3) %100 = 98 (failed) 

4. (98+5) % 100 = 103 % 100 = 3 (Answer).

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)