What this topic covers
18 subtopics- Hash maps6
- Counting5
- Open addressing5
- Patterns4
- Collisions3
- Hash functions3
- Sets3
- Chaining2
- Load factor2
- Prefix sums2
- Rolling hash2
- Sliding window2
Show all 18 subtopics
- Basics1
- Distributed hashing1
- equals and hashCode1
- Hashable keys1
- Probabilistic structures1
- Security1
- Beginner 15
- Intermediate 15
- Advanced 15
About this topic
A hash table turns a key into an array index with a hash function, giving O(1) average lookups. Two keys can land in the same slot – a collision – resolved by chaining (a list per slot) or open addressing (probe for the next free slot). GATE asks you to trace probing by hand; interviews use hash maps to turn O(n²) searches into one pass. Probing traces on this page were computed by a checker program.
Free preview
Sample questions
Try each one first, then open the answer for the explanation and why the other options are wrong.
What does this print?
from collections import Counter
c = Counter("mississippi")
print(c.most_common(2))Show answer and explanation
Explanation
Counter is a dict of counts. i and s both occur 4 times; ties keep the order in which keys were first seen, and i appears before s.
Why the other options are wrong
- As (4) beats p (2).
- Bi is first seen before s.
- Cmost_common sorts by count.
A table of size 7 uses h(k) = k mod 7 with linear probing. Keys are inserted in this order: 50, 700, 76, 85, 92, 73, 101. What is the final table (slots 0–6)?
- 0·
- 1·
- 2·
- 3·
- 4·
- 5·
- 6·
- 700
- 50
- 92
- 85
- 73
- 101
- 76
- 700
- 50
- 85
- 73
- 92
- 101
- 76
- 700
- 50
- 85
- 92
- 73
- 101
- 76
- 50
- 700
- 85
- 92
- 73
- 101
- 76
Show answer and explanation
Explanation
50 → 1, 700 → 0, 76 → 6. 85 hashes to 1 (taken) → 2. 92 hashes to 1 → 2 taken → 3. 73 hashes to 3 (taken) → 4. 101 hashes to 3 → 4 taken → 5. Note how keys pile into one run – primary clustering.
Why the other options are wrong
- A85 is inserted before 92 and takes slot 2.
- B92 is inserted before 73 and takes slot 3.
- D700 mod 7 is 0.