Hash Tables
14 min
A hash table maps keys to values by running the key through a hash
function to compute a bucket index — giving average O(1) lookup, insert,
and delete regardless of how many items it holds. Python's dict and set
are both hash tables.
counts = {}
for word in ["a", "b", "a", "c", "a"]:
counts[word] = counts.get(word, 0) + 1
print(counts) # {'a': 3, 'b': 1, 'c': 1}
dict.get(key, default) avoids a KeyError when the key might not exist
yet — the single most common pattern for counting with a dict.
collections.Counter is a dict subclass built exactly for this — reach for it instead of hand-rolling counting logic in real code.
A hash function can map two different keys to the same bucket — a collision. Python's dict handles this internally (open addressing), so you never have to think about it directly, but it's why:
- Dict keys must be hashable (immutable) — you can't use a
listas a key, but you can use atuple. - Worst-case lookup is O(n) if everything collides (essentially never happens in practice with a good hash function), which is why textbooks always say "average-case O(1)," not "guaranteed O(1)."
Write a function `most_frequent(items)` that returns the most frequent element in a list, breaking ties by whichever value appears first in the list.
Write a function `two_sum(nums, target)` that returns a list `[i, j]` (i < j) of indices whose values sum to `target`, using a single pass with a dict — no nested loops.
What is the average-case time complexity of a lookup (`x in some_dict`) in a Python dict?
You can use a dict for O(1) average counting and lookups, and recognize the "hash map instead of nested loop" pattern.