Hash Tables: Collisions and Resizing
How a hash table gets O(1) lookups, what happens when two keys land in the same slot, and why it resizes. Includes a small working implementation with the numbers it produces.
A hash table stores key-value pairs by hashing each key to an array slot, which gives O(1) lookups on average. Collisions are unavoidable, so tables use chaining or open addressing, and they resize when the load factor passes a threshold. Interviewers expect you to explain why doubling keeps inserts amortised O(1) and why the worst case is O(n).
A hash table stores key-value pairs by running the key through a hash function to pick an array slot, which gives O(1) lookups on average. Two keys can pick the same slot (a collision), so every real table needs a collision strategy and a rule for growing as it fills up.
- A hash table gives O(1) average insert, lookup and delete, but O(n) in the worst case when every key collides into one slot.
- Since Java 8, a HashMap bucket that grows past 8 entries in a table of at least 64 slots becomes a balanced tree, so worst-case lookup degrades to O(log n).
- Java's HashMap resizes when its load factor, entries divided by slots, reaches 0.75.
- Doubling a hash table on resize makes the total work across n inserts about 2n, so each insert is O(1) amortised.
- Open addressing with linear probing causes clustering and needs tombstone markers for deletes, because a later key may have probed past an emptied slot.
- With only 23 random keys and 365 slots, there is better than a 50% chance of at least one hash collision, an instance of the birthday problem.
01How a lookup works
An array gives you instant access if you know the index. A hash table gets the index from the key. A hash function turns the key into a big integer, and taking that number modulo the array length gives a slot between 0 and length-1.
To look up a key, you repeat the same two steps and look in that slot. No scanning, no comparing against every entry. That is where the O(1) comes from.
The word that matters is average. The speed depends on the keys being spread reasonably evenly. If they all land in one slot, the table behaves like a list and every lookup is O(n).
02Why collisions are unavoidable
There are infinitely many possible strings and only a few thousand slots in a small table, so two different keys will map to the same slot sooner or later. This is the pigeonhole principle, and no clever hash function removes it. Even with 23 random keys and 365 slots there is better than a 50% chance of at least one collision (the birthday problem).
So the design question is not how to avoid collisions but how to handle them cheaply. There are two standard answers.
03Separate chaining
In chaining, slot i points to a list (or sometimes a tree). Insert appends to that list. Lookup walks the list comparing keys. If the table is not overloaded the lists stay short, one or two entries long.
Java's HashMap works this way. Since Java 8, a bucket that grows past 8 entries (in a table of at least 64 slots) is converted from a linked list into a balanced tree, so even a badly behaving hash function degrades to O(log n) rather than O(n).
Chaining is simple, deleting is easy, and the table keeps working past 100% fullness. The cost is extra memory for the list nodes and poorer cache behaviour.
04Open addressing
With open addressing there are no lists. If your slot is taken, you try the next one, then the next, until you find an empty slot. This is called linear probing. Lookup follows the same path and stops when it finds the key or hits an empty slot.
Here is what four keys that all hash to slot 3 do in a table of 8 slots:
cap = 8
table = [None] * cap
for k in [3, 11, 19, 27]: # all give k % 8 == 3
i, steps = k % cap, 0
while table[i] is not None:
i = (i + 1) % cap
steps += 1
table[i] = k
print(k, 'slot', i, 'extra probes', steps)The output is slots 3, 4, 5, 6 with 0, 1, 2, 3 extra probes. Each new key has to step over all the earlier ones. That pile-up is called clustering, and it is why open addressing needs the table to stay well under full.
Deleting is the tricky part. You cannot just empty the slot, because a later key may have probed past it. Real implementations leave a marker (a tombstone). Python's dict uses open addressing with a more elaborate probe sequence than plain linear probing.
05Load factor and resizing
The load factor is entries divided by slots. Java's HashMap resizes at 0.75. Higher means less memory and more collisions, lower means the opposite.
Resizing allocates a bigger array and re-inserts every entry, because the slot number depends on the array length, so existing entries cannot stay where they are. That single insert costs O(n).
But it happens rarely. Doubling each time means the total work across n inserts is about 2n, so each insert is O(1) amortised. Here is a small chaining table that grows at 0.75:
class HT:
def __init__(self, cap=4):
self.b = [[] for _ in range(cap)]
self.n = 0
self.resizes = 0
def _slot(self, k):
return hash(k) % len(self.b)
def put(self, k, v):
bucket = self.b[self._slot(k)]
for p in bucket:
if p[0] == k:
p[1] = v
return
bucket.append([k, v])
self.n += 1
if self.n / len(self.b) > 0.75:
self._grow()
def _grow(self):
old = self.b
self.b = [[] for _ in range(len(old) * 2)]
self.n = 0
self.resizes += 1
for bucket in old:
for k, v in bucket:
self.put(k, v)
def get(self, k):
for kk, v in self.b[self._slot(k)]:
if kk == k:
return v
h = HT()
for i in range(100):
h.put(i, i * i)
print(len(h.b), h.n, h.resizes, h.get(7), h.get(1000))The output is 256 100 6 49 None. A table that started with 4 slots resized 6 times (4, 8, 16, 32, 64, 128, 256) to hold 100 entries, and a missing key returns None.
06What makes a good key and a good hash
A hash function should be fast, give the same output for equal keys, and spread different keys widely. In Python the built-in mutable containers (list, dict, set) are not hashable, so a list cannot be a dict key while a tuple of numbers can. If you could change a key after inserting it, its hash would change and you would never find it again.
In Java, if you override equals you must override hashCode too. Two objects that are equal must give the same hash code. Breaking that contract makes HashMap lose entries in a way that is very hard to debug.
Hash tables do not keep keys in sorted order and do not support fast range queries such as "all keys between 10 and 20". For that you want a balanced tree. Python 3.7 and later keep dict insertion order, but that is about the order you inserted, not sorted order.
One security note: if an attacker knows your hash function they can send keys that all collide and make every request O(n). Python randomises string hashes per process for this reason.
07Common interview questions
Q: What is the time complexity of a hash table?
A: O(1) average for insert, lookup and delete. O(n) worst case when everything collides, or O(log n) in Java 8+ where long chains turn into trees.
Q: Chaining or open addressing?
A: Chaining is simpler and tolerates a load factor above 1. Open addressing uses less memory per entry and caches better, but degrades quickly when full and needs tombstones for deletes.
Q: Why does resizing not make inserts O(n)?
A: Doubling means each element is moved only a handful of times in total. Spread across all inserts, the cost per insert is constant. That is amortised O(1).
Q: Two objects are equal. What must be true of their hash codes?
A: They must be equal. The reverse is not required, two unequal objects may share a hash code.
Q: How would you count word frequencies in a large file?
A: Stream through it, keep a hash map from word to count, and update it for each word. O(n) time and O(unique words) space.