Skip to content
GATETECH
Official PYQ · 2020Q23Searching, Sorting, HashingNAT1 mark

GATE CS 2020 Q23 — Searching, Sorting, Hashing

Explain with AI
Consider a double hashing scheme in which the primary hash function is h1(k)=k mod 23h_1(k)= k \text{ mod } 23, and the secondary hash function is h2(k)=1+(k mod 19)h_2(k)=1+(k \text{ mod } 19). Assume that the table size is 2323. Then the address returned by probe 11 in the probe sequence (assume that the probe sequence begins at probe 00) for key value k=90k=90 is_____________.
View worked solution

Answer: 13

In double hashing, the hash function for a key kk at probe ii (where the probe sequence starts at i=0i = 0) is given by:

h(k,i)=(h1(k)+i⋅h2(k))(modM)h(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod{M}

Given:

  • Table size M=23M = 23
  • Primary hash function: h1(k)=k(mod23)h_1(k) = k \pmod{23}
  • Secondary hash function: h2(k)=1+(k(mod19))h_2(k) = 1 + (k \pmod{19})
  • Key k=90k = 90
  • Probe index i=1i = 1

Step 1: Compute h1(90)h_1(90)

h1(90)=90(mod23)=21(since 23×3=69 and 90−69=21)h_1(90) = 90 \pmod{23} = 21 \quad \text{(since } 23 \times 3 = 69 \text{ and } 90 - 69 = 21\text{)}

Step 2: Compute h2(90)h_2(90)

h2(90)=1+(90(mod19))h_2(90) = 1 + (90 \pmod{19}) 90(mod19)=14(since 19×4=76 and 90−76=14)90 \pmod{19} = 14 \quad \text{(since } 19 \times 4 = 76 \text{ and } 90 - 76 = 14\text{)} h2(90)=1+14=15h_2(90) = 1 + 14 = 15

Step 3: Compute the address for probe 11 (i=1i = 1)

h(90,1)=(h1(90)+1⋅h2(90))(mod23)h(90, 1) = (h_1(90) + 1 \cdot h_2(90)) \pmod{23} h(90,1)=(21+15)(mod23)h(90, 1) = (21 + 15) \pmod{23} h(90,1)=36(mod23)=13h(90, 1) = 36 \pmod{23} = 13

Thus, the address returned by probe 11 is 13.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Searching, Sorting, Hashing questions