Where it runs
1. The problem
The last two steps handled collisions in a table of fixed size. Such a table has a hidden limit. The more keys you add, the fuller the buckets get and the longer the lists inside them become. A lookup "in about one step" slowly turns into "walk a long list". A table that never grows gets slower with every new key.
The fix: let the table grow on its own. When the buckets get too full, the table makes more buckets and moves every entry over. Lookups stay fast, and you never have to guess the right size in advance.
2. In plain words
Take the numbers the tests use. The table starts with 4 buckets. After 3 keys it holds 3 entries in 4 buckets, fewer than one per bucket, so a lookup checks about one entry. Keep adding keys without growing, and with 40 keys every bucket would hold about 10 entries for a lookup to walk through.
So the table watches how full it is. When the 4th key arrives, there are 4 entries in 4 buckets, and the table decides that is too crowded. It makes 8 buckets and puts all 4 keys into them again. Now each bucket holds half an entry on average, and lookups are short again. The table did this on its own; your code only called set.
3. The idea
First you need a way to measure how full the table is. The load factor is one number: the count of entries divided by the count of buckets. 3 entries in 4 buckets give a load factor of 0.75. 8 entries in 4 buckets give 2.0: each bucket holds 2 entries on average, and each lookup checks about 2 entries instead of one.
You pick a threshold: the load factor past which you call the table too full. A common choice is 0.75. Each time you insert a new key, you check whether the load factor has passed the threshold. If it has, you resize: you make a bigger table, usually with twice as many buckets.
This is where many people go wrong. You cannot just copy the old buckets into the new table. A key's bucket number is hash(key) % bucketCount, and bucketCount has just changed. So many keys now belong in a different bucket. For example, a key whose code sum is 13 lands in bucket 1 with 4 buckets (13 % 4 = 1), and in bucket 5 with 8 buckets (13 % 8 = 5). You have to rehash: walk over every entry and insert it again, computing its bucket number for the new bucket count.
Trace it on the numbers the tests check. Start with 4 buckets. Insert 3 keys: the load factor is 3 / 4 = 0.75. That is not above the threshold, so nothing happens. Insert the 4th key: the load factor is 4 / 4 = 1.0, which is above 0.75. The table doubles to 8 buckets, and all 4 keys are rehashed into it. Comparing fractions is awkward, and different languages can round them differently. So check the load factor with whole numbers: count * 4 > bucketCount * 3 means the same as count / bucketCount > 0.75, without fractions. For 4 keys in 4 buckets it is 16 > 12, so the condition holds.
4. What it costs
One resize costs O(n): you rehash each of the n entries once. That sounds expensive, and one insert really can be expensive. But resizes are rare. After a doubling the load factor halves, for example from 1.0 to 0.5. Before the next resize come many cheap O(1) inserts, about as many as the entries the table already held. Divide the cost of one resize, O(n), among those inserts, and each gets a constant amount of extra work. This is called amortized O(1) (the average cost over a long series of operations): a single insert can be slow, but over a long series the cost of one insert is constant on average.
Memory is O(n) for the entries, plus the bucket array itself. Because of the doubling there are sometimes more buckets than needed. Right after a resize there are about twice as many as the minimum needed to keep the load factor at or below 0.75. That is the price of keeping inserts cheap on average.
6. Where this shows up
Every growing hash structure you use does this inside: Map and Set in JavaScript, dict and set in Python, HashMap in Java, maps in Go. They all start small and grow as they fill up. That is why you can put millions of keys into them without ever giving a size. The same move works in a session store or an in-memory cache that grows with traffic. It works in the symbol table of a compiler or interpreter, which keeps meeting new names in the code. It works in any router (the part of a server that picks the code for a request's address) that registers an unknown number of routes at startup. When you need fast lookup by key and do not know in advance how many keys there will be, a hash table that grows on its own is the first choice.
On LeetCode
Design problems about a hash table that has to stay fast while it fills up, and the interview question of why its operations cost amortized O(1).
Start small, then double the buckets and rehash every pair once count * 4 > buckets * 3.
The same growth rule for a set, so the chains stay short however many keys arrive.
Up to 10^5 values go into one Set, and the doubling you wrote is why each check stays about one step.
Your task (Tier 2)
Most of the HashMap class is already written. The constructor (4 buckets), the size and bucketCount getters, the hash helper, and get / has / delete are given. You write the two methods that make the table grow: set and _resize.
The load factor is size / bucketCount. When it passes 0.75 the buckets get crowded, so the table doubles its number of buckets and places every pair again.
- Effect:
setstores or overwrites a key, and grows the table when it gets too full. _resizedoubles the buckets and places every pair again into the bigger table.
Steps:
set(key, value): find the bucket with_index(key). If the key is already there, change its value and stop (no size change, no growth). Otherwise add[key, value]and add 1 to the count. Then check the load: ifcount * 4 > bucketCount * 3(more than0.75full), call_resize._resize: keep the old buckets. Make a new set of buckets, twice as many, all empty. Go through every pair in the old buckets and add each one again with_index. There are more buckets now, so_indexgives a new bucket number. That is why you place the pairs again instead of copying.
Done when all tests pass:
- starts small:
bucketCount->4,size->0 - after the 4th different key it grows:
bucketCount->8, andgetstill finds every earlier key - after the 7th different key it grows again:
bucketCount->16, all 7 keys still found - overwriting a key (
set("x",1),set("x",2),set("x",3)) ->get("x")->3,size->1,bucketCount->4(no growth) - empty map:
size->0,bucketCount->4,get("missing")->undefined
Practice
HashMap with load factor and auto-resize
// Most of this class is written. Complete set() and _resize(). The task is described above the editor.
export class HashMap {
constructor() {
// 4 buckets to start; each bucket is a list of [key, value] pairs.
this.buckets = [[], [], [], []];
this.count = 0;
}
get size() {
return this.count;
}
get bucketCount() {
return this.buckets.length;
}
// sum of the key's char codes, wrapped into a bucket index.
_index(key) {
let sum = 0;
for (let i = 0; i < key.length; i++) sum += key.charCodeAt(i);
return sum % this.buckets.length;
}
set(key, value) {
// TODO: your core here.
// 1. Find the bucket for this key with _index.
// 2. If the key is already in that bucket, overwrite its value and return.
// An overwrite must not change size and must not resize.
// 3. Otherwise add the [key, value] pair and count it.
// 4. Then check the load factor and resize once it passes 0.75. Compare
// with whole numbers so every language agrees on the same moment.
}
get(key) {
const b = this.buckets[this._index(key)];
for (const pair of b) if (pair[0] === key) return pair[1];
return undefined;
}
has(key) {
const b = this.buckets[this._index(key)];
for (const pair of b) if (pair[0] === key) return true;
return false;
}
delete(key) {
const b = this.buckets[this._index(key)];
for (let i = 0; i < b.length; i++) {
if (b[i][0] === key) { b.splice(i, 1); this.count--; return true; }
}
return false;
}
_resize() {
// TODO: your core here.
// 1. Hold on to the current buckets.
// 2. Give this.buckets a fresh set of empty lists, twice as many.
// 3. Re-insert every pair from the old buckets, asking _index again for
// each key. The table is bigger now, so _index answers differently.
// That is why you rehash instead of copying.
}
}
Running as a guest
The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.
Hint ladder
Stuck? Reveal one rung at a time, but try it yourself first.