Lesson 4 of 10 · 7 min
Hashing: trading memory for time
Understand what a hash table does under the hood, and recognise the problems it collapses.
The mechanism
A hash table is an array plus a function that turns a key into an index. To look something up you hash the key, jump straight to that slot, and compare. No scanning, so the cost does not grow with the number of stored items.
Two keys can hash to the same slot. Implementations resolve that either by chaining (a list per bucket) or by probing to a nearby slot. Either way, heavy collisions turn the constant-time lookup into a linear scan — which is why a well-distributed hash matters.
Load factor and resizing
As a table fills, collisions become more likely and probe sequences lengthen sharply. Implementations therefore resize — allocate a bigger array and rehash everything — once occupancy passes roughly two thirds.
That rehash is O(n), but because the table grows geometrically it is amortised to O(1) per insertion. It is the same argument as list append.
from collections import Counter, defaultdict
# 1. Membership — have I seen this?
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
# 2. Counting — how many of each?
counts = Counter(s)
most_common_char, n = counts.most_common(1)[0]
# 3. Grouping — bucket by a canonical key
groups = defaultdict(list)
for word in words:
groups[tuple(sorted(word))].append(word) # anagrams share a keyOrdering guarantees
Since Python 3.7, dicts preserve insertion order as a language guarantee. Sets make no ordering promise at all, and because string hashes are randomised per process, set iteration order can differ between runs.
So never rely on set iteration order for deterministic output — sort explicitly if the order matters.
Worth remembering
- A hash function maps a key to a bucket, so lookup does not scan.
- O(1) is average, not worst case — collisions and bad hashes degrade it.
- Frequency counting, de-duplication and complement lookup are all the same tool.
Test it now
Counting and membership questions run through the whole easy bank.