A hash table stores key-value pairs and answers "what's the value for this key?" in (usually) constant time, by turning the key into an array index instead of scanning for it. It is the structure behind a Python dict, a Java HashMap, a database index's in-memory lookup layer, a cache, a deduplication set, and the symbol table a compiler uses to resolve variable names. Interviewers lean on it constantly because "can you get this from O(n) to O(1) with a hash map" is the single most common optimization move in easy-to-medium problems, and because the "O(1) average, not worst case" caveat separates candidates who memorized the term from candidates who understand why it holds.
"dog" repeats the same arithmetic and lands on slot 2 with no searching.The whole trick is that a hash function converts an arbitrary key into a number, and that number modulo the table's capacity becomes an array index. Reading or writing an array slot by index is O(1) (see arrays.html — it's just base_address + index * element_size), so if you can compute the right index in O(1), you get O(1) access to a value that has nothing to do with position, unlike an array where the "index" only ever meant "the k-th thing I put in." A hash table is really "an array, plus a function that decides where each key belongs."
This only works if the hash function is deterministic (the same key always maps to the same slot — otherwise you could never find what you stored), fast to compute (O(1) or close to it, or you've just moved the cost around), and spreads keys evenly across slots (bunch every key into slot 0 and you've built a slow linked list with extra steps). Python's hash(), Java's hashCode(), and library implementations like FNV or MurmurHash exist precisely to satisfy the third property for arbitrary data without you having to design one per key type.
A collision is two different keys hashing to the same slot. This is not a sign of a badly written hash function — it is mathematically guaranteed by the pigeonhole principle the moment the key space is larger than the table (which it always is: a table of a million slots still has to accept an unbounded number of possible strings). A "good" hash function does not eliminate collisions, it only makes them rare and unpredictable, so no small set of real-world keys clusters together by accident. This is also why hash tables are a natural interview trap: candidates who forget collisions exist will claim guaranteed O(1) lookup, which is wrong.
What differs between a good and bad hash function is how badly collisions cluster. The character-sum function above is a bad hash specifically because anagrams — a common pattern in real data (usernames, permutations of the same letters) — always collide; it throws away information (order) that a better function like a polynomial rolling hash (h = h*31 + ord(c) for each character) preserves.
put("one"), put("two"), put("three") and 4 slots (real rolling hash from the demo), "one" and "three" both land in slot 2, so slot 2 keeps a short list. A lookup goes to the slot, then compares keys along the list.def put(self, key, value):
i = str_hash(key) % self.capacity
bucket = self.buckets[i]
for pair in bucket:
if pair[0] == key:
pair[1] = value
return
bucket.append([key, value])
self.size += 1
if self.size / self.capacity > 0.75:
self._resize()==, because different keys can share a bucket.Chaining resolves a collision by not fighting it: each slot holds a small bucket (usually a linked list, sometimes a small dynamic array or, in Java 8+'s HashMap, a balanced tree once a bucket gets large) of every key that landed there. Insert always succeeds in O(1) — append to the bucket. Lookup is O(1) only when buckets stay short; if k keys land in one bucket, finding one of them costs O(k) because you're walking a list and comparing keys one by one. That's exactly what "O(1) average" is hedging against: average bucket length is total keys ÷ number of slots (the load factor), and average-case analysis assumes the hash function keeps that distribution roughly even. If every key collided into one bucket, chaining degrades to a single linked list: O(n) per lookup.
Chaining's real advantage is that it degrades gracefully — a table at load factor 3 (three times more keys than slots) still works, just slower, because buckets simply grow. The cost is memory: every entry carries pointer overhead for the list node, and walking a chain means chasing pointers around memory instead of scanning contiguous slots, which is slower in practice than the Big-O suggests (see arrays.html's cache-friendliness discussion).
def put(self, key, value):
i = self.hash_fn(key) % self.capacity
probes = 1
while self.slots[i] is not None:
if self.slots[i][0] == key:
self.slots[i] = (key, value)
return probes
i = (i + 1) % self.capacity
probes += 1
self.slots[i] = (key, value)
self.size += 1
return probes% self.capacity wraps from the last slot back to 0.Open addressing keeps every key directly in the array — no buckets, no pointers. On a collision, it probes: it computes a sequence of candidate slots and walks it until it finds an empty one. Linear probing tries index, index+1, index+2, ... (wrapping around with modulo); quadratic probing tries index, index+1², index+2², ... to spread out clusters better; double hashing uses a second hash function to pick the step size, which avoids linear probing's tendency to form long runs of occupied slots ("primary clustering"). The demo above shows the mechanism honestly: a good hash spreads these 7 keys into 7 different slots (1 probe each), and a deliberately bad hash (constant, ignoring the actual key content) collapses them into one growing run, where the 7th insert needs 7 probes — this is the O(n) worst case made visible, not asserted.
Open addressing's payoff is cache-friendliness: probing walks adjacent array slots, which is exactly the memory-access pattern CPUs prefetch well, unlike chaining's pointer chasing. Its cost is that it degrades much harder as the table fills — at a high load factor, insert and lookup can require scanning long runs (the demo shows probes climbing from 1 to 7 as load factor goes from 0.125 to 0.875), which is why open-addressing tables are typically resized well before they get full (commonly around 0.7), more conservatively than a chaining table.
user4 is deleted by emptying slot 1, a lookup for user5 (home slot 5) hits that empty slot and wrongly stops. A tombstone (✝) says "deleted, keep probing"; inserts may reuse it.Chaining deletes trivially — remove the entry from its bucket's list, done. Open addressing cannot: probing relies on "keep scanning until you hit an empty slot" to know a key isn't present, and if a delete leaves a true empty slot in the middle of a probe chain, later lookups for keys that were pushed past that slot will stop early and wrongly report "not found," even though the key is still sitting further along. The standard fix is a tombstone — a special marker meaning "something used to be here, keep probing past me, but I'm free to insert into." Tombstones accumulate over time and slow probing back down even at a moderate load factor, which is why open-addressing tables with heavy delete traffic periodically rehash from scratch to clear them out.
index = hash(key) % capacity.(key, value) to the list at that slot (replacing the value if the key is already present in the bucket).index = hash(key) % capacity.Two implementations: separate chaining with automatic resizing, and open addressing with linear probing, run once with a good hash and once with a deliberately bad one to make the collision cost visible rather than asserted.
def str_hash(key):
"""Deterministic string hash (polynomial rolling hash), so runs are reproducible."""
h = 0
for c in key:
h = (h * 31 + ord(c)) % (2**32)
return h
class ChainingHashTable:
"""Separate chaining: each slot holds a list of (key, value) pairs."""
def __init__(self, capacity=4):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _index(self, key):
return str_hash(key) % self.capacity
def put(self, key, value):
i = self._index(key)
bucket = self.buckets[i]
for pair in bucket:
if pair[0] == key:
pair[1] = value
return
bucket.append([key, value])
self.size += 1
if self.size / self.capacity > 0.75:
self._resize()
def get(self, key):
bucket = self.buckets[self._index(key)]
for k, v in bucket:
if k == key:
return v
raise KeyError(key)
def _resize(self):
old_buckets = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old_buckets:
for k, v in bucket:
self.put(k, v)
def load_factor(self):
return self.size / self.capacity
t = ChainingHashTable(capacity=4)
words = ["one", "two", "three", "four", "five", "six", "seven"]
for w in words:
t.put(w, len(w))
print(f"put {w!r:8} size={t.size} capacity={t.capacity} load_factor={t.load_factor():.2f}")
print("get 'four' ->", t.get("four"))
print("bucket sizes:", [len(b) for b in t.buckets])
class OpenAddressingTable:
"""Linear probing: on collision, scan forward until an empty slot."""
def __init__(self, capacity, hash_fn):
self.capacity = capacity
self.size = 0
self.slots = [None] * capacity
self.hash_fn = hash_fn
def put(self, key, value):
i = self.hash_fn(key) % self.capacity
probes = 1
while self.slots[i] is not None:
if self.slots[i][0] == key:
self.slots[i] = (key, value)
return probes
i = (i + 1) % self.capacity
probes += 1
self.slots[i] = (key, value)
self.size += 1
return probes
print("-- good hash, open addressing, filling to load factor 0.875 --")
good = OpenAddressingTable(capacity=8, hash_fn=str_hash)
for i in range(7):
key = f"user{i}"
probes = good.put(key, i)
print(f"insert {key:6} load_factor={good.size/good.capacity:.3f} probes={probes}")
print()
print("-- bad hash (hash = len(key)), same 7 keys, same capacity --")
bad = OpenAddressingTable(capacity=8, hash_fn=lambda k: len(k))
for i in range(7):
key = f"user{i}"
probes = bad.put(key, i)
print(f"insert {key:6} load_factor={bad.size/bad.capacity:.3f} probes={probes}")
# Output:
# put 'one' size=1 capacity=4 load_factor=0.25
# put 'two' size=2 capacity=4 load_factor=0.50
# put 'three' size=3 capacity=4 load_factor=0.75
# put 'four' size=4 capacity=8 load_factor=0.50
# put 'five' size=5 capacity=8 load_factor=0.62
# put 'six' size=6 capacity=8 load_factor=0.75
# put 'seven' size=7 capacity=16 load_factor=0.44
# get 'four' -> 4
# bucket sizes: [0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 1, 1, 0]
#
# -- good hash, open addressing, filling to load factor 0.875 --
# insert user0 load_factor=0.125 probes=1
# insert user1 load_factor=0.250 probes=1
# insert user2 load_factor=0.375 probes=1
# insert user3 load_factor=0.500 probes=1
# insert user4 load_factor=0.625 probes=1
# insert user5 load_factor=0.750 probes=1
# insert user6 load_factor=0.875 probes=1
#
# -- bad hash (hash = len(key)), same 7 keys, same capacity --
# insert user0 load_factor=0.125 probes=1
# insert user1 load_factor=0.250 probes=2
# insert user2 load_factor=0.375 probes=3
# insert user3 load_factor=0.500 probes=4
# insert user4 load_factor=0.625 probes=5
# insert user5 load_factor=0.750 probes=6
# insert user6 load_factor=0.875 probes=7str_hash is a polynomial rolling hash: h * 31 + ord(c) per character, so order matters (unlike the character sum) and runs are repeatable.ChainingHashTable is the chaining code above. The printout shows the resizes: when the load factor would pass 0.75 the capacity doubles (4 → 8 → 16) and the load factor drops again.get hashes to the bucket and walks it comparing keys, raising KeyError like a dict when the key is missing.OpenAddressingTable is linear probing. The same 7 keys are inserted twice: with the real hash each takes 1 probe; with hash = len(key) (all length 5) the probes climb 1, 2, … 7.Notice the last block: identical keys, identical capacity, only the hash function changed, and probes needed per insert went from a flat 1 to climbing 1-through-7. That's the entire "O(1) average, O(n) worst case" claim made concrete instead of asserted.
hash(key) % old_capacity indices are meaningless once capacity changes.equals() without hashCode() in Java) — if the key's hash can change after insertion, the entry becomes unfindable at its own slot.Q: What is a hash collision, and why is it unavoidable no matter how good your hash function is?
A: A collision is two different keys mapping to the same slot. It's unavoidable by the pigeonhole principle: a table has a fixed, finite number of slots, but the space of possible keys (strings, in particular) is unbounded, so some two keys must share a slot once you have more possible keys than slots. A good hash function doesn't prevent this — it only makes collisions rare and spread out instead of clustered on real-world data.
Q: What's the real difference between chaining and open addressing for handling collisions?
A: Chaining stores a list of entries per slot, so a collision just means appending to that slot's list — memory grows per bucket, and lookups pay for pointer-chasing but degrade gracefully as load factor rises. Open addressing keeps every entry directly in the array and resolves a collision by probing for the next open slot, which is cache-friendlier (sequential-ish memory access) but needs tombstones for deletion and degrades sharply as the table fills, since probe chains get long.
Q: Why does open addressing get worse as the load factor approaches 1?
A: As more slots fill up, a new insert or lookup is statistically more likely to hit an occupied slot on its first probe and has to keep scanning; near-full tables can require probing a large fraction of all slots for one operation, visible in the demo where probes climbed from 1 to 7 as load factor went from 0.125 to 0.875 with a poor hash. Chaining doesn't have this failure mode the same way — a full "slot" just means a longer list, not a longer scan through mostly-occupied neighboring slots.
Q: What is a load factor, and why does a hash table resize when it gets too high?
A: Load factor is entries ÷ capacity — how full the table is. As it rises, average bucket length (chaining) or average probe length (open addressing) rises with it, degrading the O(1) average toward O(n). Resizing allocates a bigger backing array (commonly double) and re-inserts every entry re-hashed against the new capacity, which restores a low load factor and, amortized over many inserts, keeps average insert cost O(1) — the same amortized argument as a dynamic array's doubling (see arrays.html).
Q: Is hash table lookup really O(1) — under what conditions does that break down?
A: It's O(1) on average, assuming the hash function distributes real keys roughly uniformly across slots and the load factor is kept low by resizing. It breaks down to O(n) if the hash function clusters keys badly (as demonstrated with a length-based hash on same-length strings) or if an attacker can choose keys specifically to collide (a real denial-of-service vector against naive hash functions, which is why languages like Python randomize string hashing per process by default).
Q: How would you design a hash function for strings?
A: Combine every character's contribution so that order matters and small input changes produce large output changes — a polynomial rolling hash like h = h * P + ord(c) for a prime P (31 and 37 are common choices) accumulated over all characters, then reduced mod the table capacity. It must never depend only on a property many different keys share, like length or character sum, because that throws away the information that would otherwise separate keys.
Follow-up: If chaining tolerates a high load factor fine, why do languages still resize chained hash tables at load factor around 0.75 instead of letting it grow?
A: Because "tolerates" doesn't mean "free" — average bucket length still grows linearly with load factor, so lookups slowly get more expensive even though nothing breaks. Resizing at a modest threshold keeps buckets short (close to 1 entry on average) so the O(1) average stays close to actually O(1) in practice, trading some wasted array space for consistently fast operations.
Follow-up: You need to cache the last 1000 API responses and evict the oldest when full — is a plain hash table enough?
A: No — a hash table gives you O(1) lookup by key but no ordering information, so it can't tell you which entry is oldest. You need a hash table combined with an ordering structure: a doubly linked list threaded through the entries (classic LRU cache design) or, if eviction is by insertion time rather than access time, a queue alongside the hash table. The hash table's job stays "find this entry fast"; something else has to track order.
Follow-up: Two different objects have the same hashCode() in Java but are not equal() — is that a bug?
A: No, that's an ordinary collision and is expected — the contract only requires that equal objects have equal hash codes, not the reverse. It becomes a bug only if you override equals() without also overriding hashCode() consistently, because then two objects that are logically equal could get different hash codes and land in different buckets, making a stored entry unfindable by an equal key.
Hash tables are the wrong choice whenever you need ordering: keys in sorted order, range queries ("all users between 18 and 25"), or "the smallest/largest key" — a balanced BST or a sorted array answers those in O(log n) while a hash table can't answer them faster than a full O(n) scan, because it deliberately discards positional relationships between keys to get O(1) point lookup. They're also a poor fit under adversarial input (an attacker choosing keys to collide) unless the language's hash is randomized or you use a cryptographic hash, and they carry real memory overhead — chaining's pointers and open addressing's spare capacity both cost more than a tightly packed array or a bit-level structure like a trie for prefix-heavy string keys. When you need both fast lookup and ordering, the practical compromise is often a hash table plus a separate ordered structure (as in an LRU cache), rather than picking just one.