Resizing and rehashing
mediumThe bucket index is hash(k) mod m, so changing m changes every key's index - the table cannot be copied, it must be rebuilt. Amortised O(1), but the tail latency is real.
O(1) amortisedWorst O(n)Space O(n + m)Saved in this browser - no sign-up, nothing sent anywhere.
How resizing and rehashing works
A bucket index is not a property of the key alone - it is hash(k) mod m, a joint property of the key and the current table size. Double m and every index is recomputed against the new modulus, so growing a hash table can never be a copy: all n entries must be rehashed and reinserted, and whichever insert crosses the load threshold pays that O(n) bill.
Doubling makes the bill affordable. Each resize costs twice the previous one but takes twice as many inserts to trigger, so the total work over n insertions stays O(n) - amortised O(1) per insert, the same geometric argument as the dynamic array. This module resizes when α = n/m exceeds 0.75, the default Java's HashMap ships with.
The catch is the tail. Amortised O(1) does not stop one specific insert from stalling for a full rebuild - a real latency spike in serving systems, and the reason pre-sizing a map is worth doing. And when the buckets are servers instead of array slots, rehashing means moving nearly all the data - the problem consistent hashing was invented for.
Step by step
- Start with m = 4 buckets and a resize threshold of α = 0.75. Insert 9: bucket 9 mod 4 = 1, and α = 0.25.
- Insert 6 into bucket 2, then 10 - also bucket 2, chaining behind 6. Three keys make α = 0.75, exactly at the limit.
- Insert 21 into bucket 1. Now n = 4 and α = 1.00, over the threshold - this one insert must pay for a rebuild.
- Allocate 8 buckets and rehash every key: 9 mod 8 = 1, 6 mod 8 = 6, 10 mod 8 = 2, 21 mod 8 = 5.
- Compare: 9 and 10 kept their index while 6 and 21 moved - doubling preserves the low bits, so about half the keys stay put. The 6 and 10 collision dissolved.
- α is back to 4/8 = 0.50. The next resize will not trigger until the seventh key arrives - twice as far away and twice as expensive. That is the amortisation.
Complexity
| Average time | O(1) amortised |
|---|---|
| Worst case time | O(n) |
| Space | O(n + m) |
Doubling makes resizes rarer exactly as fast as they get more expensive.
Reference implementation
Python
MAX_LOAD = 0.75
def put(self, key, value):
self._insert(self.buckets, key, value)
self.n += 1
if self.n / len(self.buckets) > MAX_LOAD:
self._resize()
def _resize(self):
old = self.buckets
self.buckets = [[] for _ in range(len(old) * 2)]
for bucket in old:
for key, value in bucket:
# The index changes, because m changed. Every key
# must be rehashed - this is the O(n) part.
self._insert(self.buckets, key, value)JavaScript
const MAX_LOAD = 0.75;
put(key, value) {
this.#insert(this.buckets, key, value);
this.n++;
if (this.n / this.buckets.length > MAX_LOAD) this.#resize();
}
#resize() {
const old = this.buckets;
this.buckets = Array.from({ length: old.length * 2 }, () => []);
for (const bucket of old) {
for (const [key, value] of bucket) {
this.#insert(this.buckets, key, value); // index changes with m
}
}
}Worth noticing
Rehashing is unavoidable, not laziness
The bucket index is `hash(k) mod m`. Change m and every key's index changes, so the table cannot just be copied - every entry must be recomputed and reinserted.
Amortised O(1) again
Doubling means resizes get rarer exactly as fast as they get more expensive, so the total cost of n insertions stays O(n). Same geometric argument as the dynamic array - and the same catch: any individual insert can be O(n).
Why that matters in production
A latency-sensitive service can see a tail-latency spike the moment a large map resizes. Pre-sizing a map when you know roughly how many entries it will hold removes the spike entirely - one of the cheapest optimisations there is.
Consistent hashing exists because of this
If the buckets are servers rather than array slots, rehashing means moving nearly all the data. Consistent hashing changes the mapping so that adding a node moves only 1/n of the keys.
Common pitfalls
- Copying instead of rehashing. Entries carried straight into a bigger array keep their old positions, but lookups compute hash(k) mod newM - the table appears to lose keys that are physically present.
- Never resizing at all. Nothing crashes; chains just grow with n, and the promised O(1) decays into O(n) so gradually that it usually surfaces as a slow endpoint, not a bug.
- Growing one insert at a time when the final count is known. Every doubling rehashes every existing key; constructing the map with the right capacity skips all of that work.
- Holding a computed bucket index, iterator, or reference across inserts. A resize can move every entry, which is why many languages invalidate iterators or throw on concurrent modification.
- Raising the threshold to save memory. Above α = 1 average chains exceed one entry and keep growing; the memory saved is small next to the extra comparisons on every operation.
Where it is used
- Every growable map does this - Python's dict, Java's HashMap, Go's map - and each can stall a single operation while it rebuilds.
- Pre-sizing maps and sets when the element count is known - one of the cheapest latency wins available in a code review.
- Consistent hashing in distributed caches - when buckets are servers, rehashing would move nearly every key, so the ring moves only 1/n per node change.
- An interview staple: explain why hash insert is amortised O(1) - the doubling argument transfers directly from the dynamic array.
Frequently asked questions
What is the time complexity of resizing a hash table?
A single resize is O(n) - every key is rehashed against the new modulus. Spread across the inserts that led to it, insertion averages out to O(1) amortised, with O(n) worst case for the triggering insert. Space is O(n + m), and both tables briefly coexist during the rebuild.
Why do hash tables double in size instead of growing by a fixed amount?
Doubling makes resizes rarer at exactly the rate they get more expensive, so total work stays O(n) over n inserts. Growing by a constant would mean O(n) resizes of average cost O(n) - quadratic total. Doubling also preserves low bits, so about half the keys keep their bucket.
What load factor should trigger a resize?
0.75 is the convention for chained tables - Java's default - balancing memory against chain length. Open-addressed tables resize earlier, around 0.5 to 0.7, because probing collapses as the table nears full. A lower threshold buys shorter chains at the price of more empty buckets.
Do hash tables shrink when entries are deleted?
Usually not. Java's HashMap never gives capacity back, and most standard libraries behave the same, so a map that once held millions of entries keeps its bucket array after clearing. When that memory matters, the fix is to rebuild the survivors into a fresh, right-sized map.