Hash Tables: The Power Behind Dicts and Sets

Python's dict and set are hash tables, and they are the single most useful tool in your algorithmic toolbox. A hash table answers "have I seen this before?" and "what value belongs to this key?" in O(1) average time. Most interview problems that look hard with loops become easy the moment you throw a dictionary at them. This lesson shows you how hashing works and drills the patterns you will use constantly.

What You'll Learn

• How hashing maps keys to storage slots
• Why dict and set lookups are O(1) on average
• The three killer patterns: membership, counting, grouping
• What makes a key hashable and how collisions are handled

How Hashing Works

A hash function turns any key into a number. The table uses that number (modulo the table size) to pick a slot, so lookup jumps straight to the right place instead of scanning:

Two different keys can land in the same slot (a collision). Real hash tables handle this by chaining entries or probing nearby slots, and they resize when they get too full, which keeps the average lookup at O(1). The worst case is O(n), but Python's implementation makes that vanishingly rare in practice.

The Speed Difference Is Not Subtle

Pattern 1: Membership (Seen Before?)

The duplicate check from lesson one, now as a reusable idiom:

Pattern 2: Counting Frequencies

Count occurrences with a dict, or let collections.Counter do it for you:

Frequency counting cracks anagram checks, majority elements, and "top k" problems, usually turning O(n^2) into O(n).

Pattern 3: Grouping

Group items by a computed key with dict.setdefault or defaultdict. Grouping anagrams together is the classic example. Try extending this one fullscreen:

What Can Be a Key?

Keys must be hashable: their hash cannot change while they sit in the table. Immutable types (strings, numbers, tuples of immutables) qualify. Mutable ones (lists, dicts, sets) do not:

Exercises

Key Takeaways

• Dicts and sets are hash tables: O(1) average lookup, insert, and delete
• Hashing maps a key to a slot; collisions and resizing are handled for you
• Membership, counting, and grouping are the three patterns that solve most "seen before" problems in O(n)
• Keys must be immutable (hashable); use tuples instead of lists as compound keys
• When a nested-loop solution feels slow, ask what a dict could remember for you