The problem hash maps solve
Here is a question you will see in some form in almost every interview: "Given a list of numbers, find two that add up to a target." The obvious approach checks every pair.
def two_sum_slow(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return (i, j)
Two nested loops means O(n^2). For 10,000 numbers that is 100 million comparisons. Now watch what a dict does:
def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
if target - n in seen:
return (seen[target - n], i)
seen[n] = i
One pass, O(n). The trick is that in seen is not a search. It does not scan. It computes where the answer would live and looks there directly. That is the whole superpower, and once you see it you will reach for it constantly.
Why lookups are (basically) free
A Python dict and set are hash tables. When you store a key, Python runs it through a hash function, a fast computation that turns your key into a number, and uses that number to pick a slot in an internal array. Reading works the same way: hash the key, jump to the slot, done. No scanning, so lookups, inserts, and deletes are O(1) on average.
Two keys can hash to the same slot. That is a collision, and Python handles it for you by probing nearby slots until it finds the right one. Collisions are why the guarantee is "average" O(1), not "always." In practice, for normal data, you never notice.
The one rule you must respect: keys have to be hashable, which in Python means immutable. Strings, numbers, and tuples work. Lists and dicts do not.
seen = set()
seen.add((1, 2)) # tuple: fine
seen.add([1, 2]) # TypeError: unhashable type: 'list'
If you need a list as a key, convert it to a tuple first.
The four patterns that cover most problems
Almost every O(n^2)-to-O(n) win falls into one of four shapes. Learn to recognize them.
Counting
When a problem says "most frequent," "how many times," or "appears more than once," you are counting. collections.Counter is a dict subclass built for exactly this.
from collections import Counter
votes = ["a", "b", "a", "c", "a", "b"]
counts = Counter(votes) # {'a': 3, 'b': 2, 'c': 1}
counts.most_common(1) # [('a', 3)]
Grouping
When you need to bucket items by some shared key, anagrams by their sorted letters, transactions by user, use defaultdict so you never have to check "does this bucket exist yet."
from collections import defaultdict
groups = defaultdict(list)
for word in ["eat", "tea", "tan", "ate"]:
groups[tuple(sorted(word))].append(word)
# {('a','e','t'): ['eat','tea','ate'], ('a','n','t'): ['tan']}
The sorted letters become a fingerprint. Every anagram lands in the same bucket.
Deduping
A set gives you uniqueness for free. Checking membership as you go turns "have I seen this?" into an O(1) question.
def first_duplicate(nums):
seen = set()
for n in nums:
if n in seen:
return n
seen.add(n)
return None
Lookups
This is two_sum: instead of searching for a partner, you store what you have seen and ask the set whether the partner is already there. Any time you catch yourself writing an inner loop to "find the matching thing," stop and ask whether a dict could answer that in one step.
When dicts and sets bite back
They are not free of trade-offs. Three things to keep in mind.
Order. Since Python 3.7, a dict remembers insertion order, so iterating gives you keys in the order you added them. A set does not guarantee any order. If order matters for a set, keep a separate list, or use dict.fromkeys(items) to dedupe while preserving order:
unique_in_order = list(dict.fromkeys(["b", "a", "b", "c"])) # ['b', 'a', 'c']
Memory. Hash tables trade space for speed. A set of a million integers uses far more memory than the same integers in a list. Usually worth it, but know that you are paying for it.
The average-case asterisk. O(1) is the average. Adversarial keys engineered to collide can degrade to O(n), which matters for security-sensitive code but almost never in an interview or normal app.
One more habit worth building: reach for .get(key, default) and defaultdict instead of guarding every access with if key in d. Cleaner code, same speed.
Your default tool
The mental shortcut is this: when you see nested loops, ask whether a hash map removes the inner one. Counting, grouping, deduping, membership tests, and pairing all collapse from O(n^2) to O(n) the moment you stop searching and start hashing. It costs some memory and forgets about order unless you ask, but for the vast majority of problems that is a trade you take without thinking.
If you want more reps writing this kind of idiomatic Python, the DSA with Python course and Advanced Python Programming drill these patterns with runnable exercises. Do enough of them and spotting the hash-map solution stops being a trick and becomes the first thing you see.