DSA · Lesson 3 of 9
Hash maps & sets
Constant-time lookups for counting, grouping and finding pairs.
A hash map (Python dict) and hash set (set) find, add and remove items in O(1) average time by hashing the key to a storage slot.
Recognise these patterns:
- Counting — word frequencies, most common skill (
collections.Counter). - Seen-before — duplicates, first repeating character, two-sum.
- Grouping — anagrams grouped by sorted letters (
defaultdict(list)).
Keys must be hashable (immutable): strings, numbers, tuples — not lists.
Try it yourself
Press Run to see the output.
Edit and press Run (or Ctrl/⌘ + Enter). Python runs in your browser — the first run downloads the Python engine and takes a few seconds.
Key points
- dict/set give O(1) average lookups.
- Counter for frequencies; defaultdict for grouping.
- Trade extra memory for speed.
Quick check
Which cannot be a dict key in Python?
Lists are mutable and unhashable; tuples of immutables are fine.
Practice task
Return the length of the longest substring without repeating characters (hint: dict of last seen index + sliding window).
Interview corner
How does a hash map handle collisions?
Two keys landing in the same slot are resolved by chaining (a list per bucket) or open addressing (probing for another slot). Python dicts use open addressing.
When is a hash map lookup not O(1)?
In the worst case — many collisions — it degrades to O(n); resizing also costs O(n) occasionally, though amortised cost stays O(1).
Further reading
Official documentation, linked for deeper study. These are outside sites; this lesson's text is our own.
Original lesson written by the InfoparkDaily team · © 2026 InfoparkDaily · Free to learn — no paid course or subscription.