Project ForgeData Structures
Hashing
GATE 2014
Medium
Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are
- 3, 0, and 1
- B3, 3, and 3
- C4, 0, and 1
- D3, 0, and 2
Explanation
h(k)=k mod 9 for each key: 5→5, 28→1, 19→1, 15→6, 20→2, 33→6, 12→3, 17→8, 10→1. Slot contents: slot1={28,19,10} (length 3), slot2={20}(1), slot3={12}(1), slot5={5}(1), slot6={15,33}(2), slot8={17}(1), slots 0,4,7 empty(0). Max chain=3, min=0, average=9 keys/9 slots=1.
Source: GATE CS 2014 (Session 1) (2014)
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.