The intuition: compute where the answer lives
Imagine looking up a friend's phone number. In an unsorted list you'd scan every entry until you hit the right name. A hash table instead does arithmetic on the name itself to jump straight to the slot where the number is stored — no scanning. That single trick, computing a location directly from the key, is what makes lookups feel instant.
The price is that you give up order. A hash table won't hand you keys sorted, and it can't cheaply answer 'what's the next largest key.' In exchange you get near-constant-time insert, lookup, and delete — which is exactly the trade most interview problems are quietly asking for.
How hashing turns a key into an index
A hash function takes a key of almost any type — string, number, tuple — and returns a fixed-size integer. The table reduces that integer modulo the number of buckets to get an array index, then stores the (key, value) pair there. Because array indexing is itself O(1), and a good hash spreads keys evenly across buckets, most operations touch only a single slot.
As you add entries, the load factor (items divided by buckets) climbs. Once it crosses a threshold — often around 0.75 — the table allocates a larger array and rehashes every existing key into it. That resize costs O(n), but it happens rarely, so the amortized cost per operation stays O(1). Keeping the load factor bounded is what preserves fast lookups as the table grows.
Collisions: when two keys share a slot
Different keys can hash to the same index — a collision — and every real hash table needs a plan for it. The most common is separate chaining: each bucket holds a small list, and colliding entries live in that list. A lookup finds the bucket, then scans its (usually tiny) list for a matching key. The alternative, open addressing, probes forward to the next free slot instead of keeping lists.
Collisions are why O(1) is an average, not a guarantee. If every key collided into one bucket, a lookup would degrade to O(n) — a plain linear scan. A good hash function plus a bounded load factor keeps chains short, so in practice you get constant time. It also explains why untrusted keys are a real attack surface: inputs engineered to collide can deliberately force worst-case behavior.
class HashTable:
def __init__(self, capacity=8):
self.buckets = [[] for _ in range(capacity)]
self.size = 0
def _index(self, key):
return hash(key) % len(self.buckets)
def put(self, key, value):
bucket = self.buckets[self._index(key)]
for i, (k, _) in enumerate(bucket):
if k == key: # key exists -> overwrite
bucket[i] = (key, value)
return
bucket.append((key, value)) # new key -> chain it
self.size += 1
def get(self, key):
bucket = self.buckets[self._index(key)]
for k, v in bucket:
if k == key:
return v
raise KeyError(key)The O(1) is an amortized average that assumes a good hash function and a bounded load factor. Clustered or adversarial keys, or a table that never resizes, push operations toward O(n).
When to use it
- Membership tests: keep a set of seen items and answer 'have I encountered this before?' in O(1) instead of re-scanning a list.
- Frequency counting: map each item to a running count for character counts, word counts, or grouping anagrams.
- Caching and memoization: store computed results keyed by their inputs so you never recompute the same call twice.
- Collapsing nested loops: replace an O(n^2) 'find a matching pair' scan with a single pass that checks a hash map — the classic Two Sum trick.
Watch out for
- Assuming O(1) always holds. A poor hash function or adversarial keys can collide everything into one bucket and quietly degrade operations to O(n).
- Using mutable or unhashable objects as keys. In Python a list can't be a key at all, and mutating a key after insertion breaks your ability to find it again.
- Expecting order. Hash tables don't store keys sorted, so don't reach for one when you need range queries or ordered traversal — use a balanced tree or sorted structure instead.
Hash tables are the single most common optimization tool in coding interviews — in Python that's dict and set, in Java it's HashMap and HashSet. Problems like Two Sum, Group Anagrams, Longest Substring Without Repeating Characters, and subarray-sum questions are really tests of whether you can spot that a hash lookup collapses a brute-force O(n^2) scan into a single O(n) pass. Interviewers watch for that recognition, for a sensible choice of what to store as the key versus the value, and for awareness that O(1) is an average — strong candidates mention collisions and worst-case behavior rather than treating constant time as magic.