Hashing — the O(1) lookup that unlocks interviews

Hash maps (dict) and hash sets (set) give you average O(1) membership check and lookup. This one trick collapses many nested-loop O(n²) problems into a single-pass O(n).

When to reach for a hash map

• "Have I seen X before?" — set or dict.
• "Where did I see X?" — dict[value] = index.
• "Group these by some key" — defaultdict(list) + a key function.
• "Count frequencies" — collections.Counter.
• "Complement lookup" — Two-Sum pattern: for each element, look up what would complete it.

Choosing your key

The key must be hashable — immutable in Python. Common keys:

• Strings, ints, tuples ✓
• Frozen sets, frozensets ✓
• Lists, dicts, regular sets ✗ (mutable)

For "same characters, different order": key on tuple(sorted(word)). For "same bag of numbers": key on tuple(sorted(nums)) or a Counter's items().

The O(1) caveat

Hash-map ops are O(1) average. Worst case is O(n) if every key collides. In practice, Python's hash function is strong enough that this doesn't matter — unless you're being adversarially attacked (which is a real security concern for public-facing APIs, mitigated by random hash seeds).

Space cost

Trading time for space. A hash map for n items uses O(n) memory. In interviews, always mention the space complexity — interviewers care.

Try it

1. Given a list, find whether any two numbers add to a target — return True/False.
2. Given two strings, check if they're anagrams using a Counter.