GATE 2020 CS Q.23: solution and answer

GATE 2020 · CSQ.23 · 1 mark · NAT

Consider a double hashing scheme in which the primary hash function is $h_{1} (k) = k mod 23$ , and the secondary hash function is $h_{2} (k) = 1 + (k mod 19)$ . Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value $k = 90$ is ____.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The address returned by probe 1 is 13.

Official answer: 13Source: Official answer key, GATE 2020 CS (IIT Delhi)

Double hashing probe formula: $address (i) = (h_{1} (k) + i \cdot h_{2} (k)) mod 23$ , with probe 0 corresponding to $i = 0$ .
Compute $h_{1} (90) = 90 mod 23$ . Since $23 \times 3 = 69$ , the remainder is $90 - 69 = 21$ , so $h_{1} (90) = 21$ .
Compute $h_{2} (90) = 1 + (90 mod 19)$ . Since $19 \times 4 = 76$ , the remainder is $90 - 76 = 14$ , so $90 mod 19 = 14$ , giving $h_{2} (90) = 1 + 14 = 15$ .
Probe 0 address = $(21 + 0 \times 15) mod 23 = 21$ .
Probe 1 address = $(21 + 1 \times 15) mod 23 = 36 mod 23 = 13$ .
So the address returned by probe 1 is $13$ .

KEY IDEA

Double hashing: the probe sequence address at step $i$ is $address (i) = (h_{1} (k) + i \cdot h_{2} (k)) mod m$ , where probe 0 is the first probe ( $i = 0$ ).

WATCH OUT FOR

Numbering probe 0 as $i = 1$ (an off-by-one), which would compute probe 1 as $i = 2$ and give the wrong address; or computing $h_{2} (k)$ without the $+ 1$ offset.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes

GATE 2020 CS Q.23: solution and answer

Answer and solution

More Sorting & hashing questions