Project ForgeSign up free
Data Structures
Hashing
GATE 2009
Hard

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table? (compare final slot 2,3,4,5,6,7,8 contents)

  • A2:12, 3:23, 4:16, 5:15, 8:18
  • B2:12, 3:13, 4:_, 5:5, 8:18
  • 2:12, 3:13, 4:2, 5:3, 6:23, 7:5, 8:18, 9:15
  • D2:12, 3:14, 5:2, 7:23, 8:18

Explanation

Inserting in order: 12→2, 18→8, 13→3, 2 (home2, occupied)→probes to 4, 3 (home3, occupied)→probes to 5, 23 (home3, occupied)→probes through 4,5→lands at 6, 5 (home5, occupied)→probes through 6→lands at 7, 15 (home5, occupied)→probes through 6,7,8→lands at 9. Final: 2:12, 3:13, 4:2, 5:3, 6:23, 7:5, 8:18, 9:15.

Source: GATE CS 2009 (2009)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free