15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
The load factor is α = n/m, the number of stored entries divided by the table capacity. It measures how crowded the table is: higher values mean longer chains or more probes. When it passes a chosen limit, the table rehashes into a larger array, recomputing every key's index. That costs O(n) once and O(1) amortized per insertion.
| Formula | α = n / m, entries divided by capacity |
|---|---|
| Example | n = 3 and m = 4 give 3/4; after growing to m = 8 it is 3/8 |
| One rehash | O(n) time, visiting all n entries; old and new arrays coexist |
| Insertion cost | expected amortized O(1) with geometric growth; the resizing insert costs O(n) |
| Rule | recompute key mod newCapacity for every key; never copy old bucket positions |
The lesson assumes you can:
A hash table stores:
n: number of stored entries,m: table capacity, meaning number of buckets or slots.Its load factor is:
For a chained table, a larger load factor means more entries must fit into the same number of buckets. Collision chains therefore tend to become longer.
For an open-addressed table, a larger load factor means fewer empty slots remain. Searches and insertions may need more probes before they find a key or an available slot.
A resize threshold is an implementation policy. For example, a table may grow before an insertion would make its load factor exceed a chosen limit. The exact threshold is not part of the hashing rule. The table must grow while its collision policy can still operate correctly.
Capacity must be positive before a modulo-based hash function is used.
Use a chained hash table with:
m = 4,[1, 5, 9],Start with capacity 4.
| Key | Computation | Old bucket |
|---|---|---|
| 1 | 1 mod 4 = 1 | 1 |
| 5 | 5 mod 4 = 1 | 1 |
| 9 | 9 mod 4 = 1 | 1 |
The old table is:
| Bucket index | Chain |
|---|---|
| 0 | [] |
| 1 | [1, 5, 9] |
| 2 | [] |
| 3 | [] |
There are n = 3 stored keys and m = 4 buckets.
Now the growth policy requests capacity 8.
Each key must be placed according to capacity 8.
A resize transfers entries one at a time into a distinct new table. It does not move whole buckets.
Resizing re-hashes each key with the new capacity: 1 and 9 share bucket 1, while 5 goes to bucket 5. Copying old bucket 1 straight into new bucket 1 would misplace 5. Now n = 3, m = 8, α = 3/8.
Capacity is 4.
| Bucket index | Chain |
|---|---|
| 0 | [] |
| 1 | [1, 5, 9] |
| 2 | [] |
| 3 | [] |
All three keys are in bucket 1 because each key is congruent to 1 modulo 4.
Create a new, empty bucket array of capacity 8.
Do not overwrite the old table yet. The old table is still the only place that contains all entries.
| New bucket index | Chain |
|---|---|
| 0 | [] |
| 1 | [] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
| 5 | [] |
| 6 | [] |
| 7 | [] |
Compute the index again using the new capacity.
Place 1 in new bucket 1.
| New bucket index | Chain |
|---|---|
| 0 | [] |
| 1 | [1] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
| 5 | [] |
| 6 | [] |
| 7 | [] |
Now compute:
Key 5 was in old bucket 1, but it belongs in new bucket 5.
| New bucket index | Chain |
|---|---|
| 0 | [] |
| 1 | [1] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
| 5 | [5] |
| 6 | [] |
| 7 | [] |
Copying old bucket 1 directly to new bucket 1 would place key 5 at the wrong index.
Compute:
Place 9 in new bucket 1 using the chained table’s collision rule.
| New bucket index | Chain |
|---|---|
| 0 | [] |
| 1 | [1, 9] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
| 5 | [5] |
| 6 | [] |
| 7 | [] |
Only after every old entry has been transferred, replace the old capacity-4 table with the new capacity-8 table.
The number of entries is unchanged:
The capacity changed:
The new load factor is:
During transfer, part of the work is complete and part is still waiting.
After each transferred entry:
After the resize completes, the main invariant is:
Every previously stored key is present exactly once and is stored according to the hash function and collision policy for the new capacity.
For the example, after transferring 1 and 5:
1 is correctly in new bucket 1,5 is correctly in new bucket 5,9 remains available in the old table and still needs transfer.The resize is incomplete until 9 has also been rehashed and inserted.
Start with a request for newCapacity.
newCapacity is positive.newCapacity buckets.n, because resizing changes capacity, not the number of stored key-value pairs.A resize may happen before an insertion or immediately after a threshold crossing. For open addressing, growth must happen before an insertion is attempted on a full table. A capacity-4 open-addressed table with four occupied slots has no available slot for one more key.
The following operation is for a chained integer map.
Input: map, a chained map containing key-value entries; newCapacity, the requested number of buckets.
Return value: none.
Mutation behavior: replaces map.buckets and updates map.capacity; preserves all key-value associations and map.entryCount.
Boundary: newCapacity must be positive. A shrinking policy must also ensure newCapacity is not below the implementation’s valid minimum capacity.
insertIntoBucketsinsertIntoBuckets(buckets, capacity, key, value):
key mod capacity,1procedure resize(map, newCapacity)
2 input:
3 map: chained integer map with fields
4 buckets, capacity, entryCount
5 newCapacity: requested positive integer capacity
6 returns:
7 nothing
8 mutates:
9 map.buckets and map.capacity
10 preserves:
11 map.entryCount and every stored key-to-value association
12
131. if newCapacity <= 0
142. report invalid capacity
153. return
16
174. newBuckets <- array of newCapacity empty chains
18
195. for oldIndex <- 0 to map.capacity - 1
206. current <- first entry in map.buckets[oldIndex]
21
227. while current is not null
238. nextOldEntry <- current.next
249. insertIntoBuckets(
25 newBuckets,
26 newCapacity,
27 current.key,
28 current.value
29 )
3010. current <- nextOldEntry
31
3211. map.buckets <- newBuckets
3312. map.capacity <- newCapacitySaving nextOldEntry before insertion is useful when entries are linked nodes. The traversal must retain a path to the next old entry while the current entry is being transferred.
Use the original example:
map.capacity = 4map.entryCount = 31 contains [1, 5, 9]newCapacity = 8Lines 1–3:
8 <= 0 is false.Line 4:
newBuckets with indices 0 through 7.| New index | Chain |
|---|---|
| 0 | [] |
| 1 | [] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
| 5 | [] |
| 6 | [] |
| 7 | [] |
Line 5, oldIndex = 0:
0 is empty.Line 6:
current <- null.Line 7:
Line 5, oldIndex = 1:
1 contains [1, 5, 9].Line 6:
current <- entry for key 1.Line 7:
current is not null.Line 8:
nextOldEntry <- entry for key 5.Line 9:
insertIntoBuckets(newBuckets, 8, 1, value-for-1).1 mod 8 = 1.1 into new bucket 1.| New index | Chain |
|---|---|
| 0 | [] |
| 1 | [1] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
| 5 | [] |
| 6 | [] |
| 7 | [] |
Line 10:
current <- nextOldEntry.current now refers to key 5.Line 7:
current is not null.Line 8:
nextOldEntry <- entry for key 9.Line 9:
insertIntoBuckets(newBuckets, 8, 5, value-for-5).5 mod 8 = 5.5 into new bucket 5.| New index | Chain |
|---|---|
| 0 | [] |
| 1 | [1] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
| 5 | [5] |
| 6 | [] |
| 7 | [] |
Line 10:
current <- nextOldEntry.current now refers to key 9.Line 7:
current is not null.Line 8:
nextOldEntry <- null.Line 9:
insertIntoBuckets(newBuckets, 8, 9, value-for-9).9 mod 8 = 1.9 into new bucket 1 through the chaining rule.| New index | Chain |
|---|---|
| 0 | [] |
| 1 | [1, 9] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
| 5 | [5] |
| 6 | [] |
| 7 | [] |
Line 10:
current <- null.Line 7:
Lines 5–7 then inspect old indices 2 and 3.
Line 11:
map.buckets <- newBuckets.Line 12:
map.capacity <- 8.map.entryCount remains 3.
We show that resize preserves every key-value association and places every key according to the new capacity.
Before the loops begin, line 4 creates an empty new table.
No entry has been transferred yet. Therefore, every transferred entry—there are none—is present exactly once and correctly placed. All original entries remain in the old table, ready to be visited.
The transfer invariant holds before the first old bucket is examined.
Assume the transfer invariant holds before one execution of lines 8–10.
current refers to one untransferred old entry. Line 8 saves the next old entry, so the traversal can continue after this entry is transferred.
Line 9 calls insertIntoBuckets with:
newCapacity,By the helper contract, the helper computes the key’s index using key mod newCapacity and applies the chaining collision rule. The current key-value pair is inserted correctly into the new table.
The current entry is transferred once during this visit. Previously transferred entries remain in the new table. Entries not yet visited remain reachable through the old traversal path saved by nextOldEntry.
After line 10 advances current, the transfer invariant still holds.
The outer loop examines every old bucket from index 0 through map.capacity - 1.
For each bucket, the inner loop visits every entry in that bucket’s chain exactly once. Every old entry is transferred exactly once.
When both loops finish:
newBuckets,newCapacity,map.entryCount was not changed.Lines 11 and 12 replace the old table only after the complete transfer. After resize returns, every previously stored key is present exactly once and is stored according to the hash function and collision policy for the new capacity.
Computing load factor uses stored values n and m:
That requires one division, so computing is .
Now consider one resize.
The outer loop examines all m old buckets. Across all inner-loop executions, it visits exactly n stored entries.
Each transferred entry is inserted into the new table. Under the table’s controlled load policy, each such insertion has expected work.
One resize performs expected work proportional to the number of entries transferred:
A particular insertion can trigger a resize and therefore take expected time.
With geometric growth, such as repeatedly growing capacity by a constant factor, many ordinary insertions occur between resizes. The transfer work from a resize is distributed across those insertions.
Insertion has:
During rehashing, the old primary table and new primary table exist at the same time. Their bucket storage requires:
temporary table storage, in addition to the storage for the stored entries.
Incorrect assumption: an old bucket index is also the correct new bucket index.
1newBuckets[oldIndex] <- oldBuckets[oldIndex]Smallest exposing input:
4,8,5.Old index:
If code copies old bucket 1 directly to new bucket 1, key 5 remains at index 1.
Its correct new index is:
Wrong state: key 5 is stored in new bucket 1.
Correction: transfer each key separately and recompute its index with the new capacity.
Incorrect policy: wait until after an insertion attempt fails because no slot is available.
Smallest exposing input:
4,There is no empty slot available for the probing sequence to finish insertion.
Wrong result: insertion cannot complete before resizing begins.
Correction: check the growth policy before attempting an insertion into a full table.
Incorrect conclusion: because a resize transfers n entries, every insertion is .
Exposing input: a long sequence of insertions into a table that grows geometrically.
Most insertions only compute an index and follow the normal collision policy. Only occasional insertions trigger a transfer of existing entries.
Wrong conclusion: every insertion is linear.
Correction: separate:
Incorrect line or policy: permit newCapacity = 0.
Smallest exposing input:
1resize(map, 0)A later hash computation would require:
Wrong result: the table has no valid modulo-based bucket index.
Correction: reject nonpositive capacities before allocating or hashing.
Incorrect policy: repeatedly shrink without enforcing a minimum capacity.
Exposing input: a map whose shrink policy requests a capacity smaller than its defined valid minimum.
Wrong state: the table violates its own capacity boundary, and a later operation may attempt invalid indexing.
Correction: when shrinking, use the larger of the requested capacity and the implementation’s defined minimum capacity.
Implement resize(newCapacity) for a chained integer map.
Your implementation must satisfy this executable objective:
All inserted key-value pairs remain retrievable after growth, and each key is placed using
key % newCapacity.
The tests will check that your resize operation:
1class ChainedMap:
2 def __init__(self, capacity):
3 self.capacity = capacity
4 self.buckets = [[] for _ in range(capacity)]
5 self.entry_count = 0
6
7 def put(self, key, value): # no resize policy here
8 insert_into_buckets(self.buckets, self.capacity, key, value)
9 self.entry_count += 1
10
11 def get(self, key):
12 for k, v in self.buckets[key % self.capacity]:
13 if k == key:
14 return v
15 return None
16
17 def load_factor(self):
18 return self.entry_count / self.capacity
19
20 def resize(self, new_capacity):
21 if new_capacity <= 0:
22 raise ValueError("capacity must be positive")
23 new_buckets = [[] for _ in range(new_capacity)]
24 for chain in self.buckets: # every old bucket
25 for key, value in chain: # every entry in it
26 insert_into_buckets(new_buckets, new_capacity, key, value)
27 self.buckets = new_buckets # swap only after the full transfer
28 self.capacity = new_capacity
29
30def insert_into_buckets(buckets, capacity, key, value):
31 buckets[key % capacity].append((key, value)) # recompute the index with the NEW capacity
32
33def show(table):
34 for i, chain in enumerate(table.buckets):
35 if chain:
36 print(f"bucket {i}: [{', '.join(str(k) for k, _ in chain)}]")
37
38t = ChainedMap(4)
39for key in (1, 5, 9):
40 t.put(key, key * 10)
41print(f"before: capacity {t.capacity}, n={t.entry_count}, load factor {t.load_factor()}")
42show(t)
43t.resize(8)
44print(f"after: capacity {t.capacity}, n={t.entry_count}, load factor {t.load_factor()}")
45show(t)
46print("get(5) =", t.get(5))1import java.util.ArrayList;
2import java.util.List;
3
4public class Main {
5 static class Entry {
6 final int key, value;
7 Entry(int key, int value) { this.key = key; this.value = value; }
8 }
9
10 static class ChainedMap {
11 int capacity;
12 List<List<Entry>> buckets;
13 int entryCount = 0;
14
15 ChainedMap(int capacity) {
16 this.capacity = capacity;
17 this.buckets = newBuckets(capacity);
18 }
19
20 static List<List<Entry>> newBuckets(int capacity) {
21 List<List<Entry>> b = new ArrayList<>();
22 for (int i = 0; i < capacity; i++) b.add(new ArrayList<>());
23 return b;
24 }
25
26 // recompute the index with the capacity that was passed in
27 static void insertIntoBuckets(List<List<Entry>> buckets, int capacity, int key, int value) {
28 buckets.get(key % capacity).add(new Entry(key, value));
29 }
30
31 void put(int key, int value) { // no resize policy here
32 insertIntoBuckets(buckets, capacity, key, value);
33 entryCount++;
34 }
35
36 Integer get(int key) {
37 for (Entry e : buckets.get(key % capacity)) {
38 if (e.key == key) return e.value;
39 }
40 return null;
41 }
42
43 double loadFactor() { return (double) entryCount / capacity; }
44
45 void resize(int newCapacity) {
46 if (newCapacity <= 0) throw new IllegalArgumentException("capacity must be positive");
47 List<List<Entry>> fresh = newBuckets(newCapacity);
48 for (List<Entry> chain : buckets) { // every old bucket
49 for (Entry e : chain) { // every entry in it
50 insertIntoBuckets(fresh, newCapacity, e.key, e.value);
51 }
52 }
53 buckets = fresh; // swap only after the full transfer
54 capacity = newCapacity;
55 }
56
57 void show() {
58 for (int i = 0; i < capacity; i++) {
59 if (buckets.get(i).isEmpty()) continue;
60 List<String> keys = new ArrayList<>();
61 for (Entry e : buckets.get(i)) keys.add(String.valueOf(e.key));
62 System.out.println("bucket " + i + ": [" + String.join(", ", keys) + "]");
63 }
64 }
65 }
66
67 public static void main(String[] args) {
68 ChainedMap t = new ChainedMap(4);
69 for (int key : new int[]{1, 5, 9}) t.put(key, key * 10);
70 System.out.println("before: capacity " + t.capacity + ", n=" + t.entryCount + ", load factor " + t.loadFactor());
71 t.show();
72 t.resize(8);
73 System.out.println("after: capacity " + t.capacity + ", n=" + t.entryCount + ", load factor " + t.loadFactor());
74 t.show();
75 System.out.println("get(5) = " + t.get(5));
76 }
77}1#include <iostream>
2#include <stdexcept>
3#include <utility>
4#include <vector>
5using namespace std;
6
7using Buckets = vector<vector<pair<int, int>>>;
8
9// recompute the index with the capacity that was passed in
10void insertIntoBuckets(Buckets& buckets, int capacity, int key, int value) {
11 buckets[key % capacity].push_back({key, value});
12}
13
14struct ChainedMap {
15 int capacity;
16 Buckets buckets;
17 int entryCount = 0;
18
19 explicit ChainedMap(int capacity) : capacity(capacity), buckets(capacity) {}
20
21 void put(int key, int value) { // no resize policy here
22 insertIntoBuckets(buckets, capacity, key, value);
23 entryCount++;
24 }
25
26 int get(int key) const {
27 for (const auto& [k, v] : buckets[key % capacity]) {
28 if (k == key) return v;
29 }
30 return -1;
31 }
32
33 double loadFactor() const { return (double)entryCount / capacity; }
34
35 void resize(int newCapacity) {
36 if (newCapacity <= 0) throw invalid_argument("capacity must be positive");
37 Buckets fresh(newCapacity);
38 for (const auto& chain : buckets) { // every old bucket
39 for (const auto& [key, value] : chain) { // every entry in it
40 insertIntoBuckets(fresh, newCapacity, key, value);
41 }
42 }
43 buckets = std::move(fresh); // swap only after the full transfer
44 capacity = newCapacity;
45 }
46
47 void show() const {
48 for (int i = 0; i < capacity; i++) {
49 if (buckets[i].empty()) continue;
50 cout << "bucket " << i << ": [";
51 for (size_t j = 0; j < buckets[i].size(); j++) cout << (j ? ", " : "") << buckets[i][j].first;
52 cout << "]" << endl;
53 }
54 }
55};
56
57int main() {
58 ChainedMap t(4);
59 for (int key : {1, 5, 9}) t.put(key, key * 10);
60 cout << "before: capacity " << t.capacity << ", n=" << t.entryCount << ", load factor " << t.loadFactor() << endl;
61 t.show();
62 t.resize(8);
63 cout << "after: capacity " << t.capacity << ", n=" << t.entryCount << ", load factor " << t.loadFactor() << endl;
64 t.show();
65 cout << "get(5) = " << t.get(5) << endl;
66}1// recompute the index with the capacity that was passed in
2function insertIntoBuckets(buckets, capacity, key, value) {
3 buckets[key % capacity].push([key, value]);
4}
5
6class ChainedMap {
7 constructor(capacity) {
8 this.capacity = capacity;
9 this.buckets = Array.from({ length: capacity }, () => []);
10 this.entryCount = 0;
11 }
12
13 put(key, value) { // no resize policy here
14 insertIntoBuckets(this.buckets, this.capacity, key, value);
15 this.entryCount++;
16 }
17
18 get(key) {
19 for (const [k, v] of this.buckets[key % this.capacity]) {
20 if (k === key) return v;
21 }
22 return undefined;
23 }
24
25 loadFactor() { return this.entryCount / this.capacity; }
26
27 resize(newCapacity) {
28 if (newCapacity <= 0) throw new Error('capacity must be positive');
29 const fresh = Array.from({ length: newCapacity }, () => []);
30 for (const chain of this.buckets) { // every old bucket
31 for (const [key, value] of chain) { // every entry in it
32 insertIntoBuckets(fresh, newCapacity, key, value);
33 }
34 }
35 this.buckets = fresh; // swap only after the full transfer
36 this.capacity = newCapacity;
37 }
38
39 show() {
40 this.buckets.forEach((chain, i) => {
41 if (chain.length) console.log(`bucket ${i}: [${chain.map(([k]) => k).join(', ')}]`);
42 });
43 }
44}
45
46const t = new ChainedMap(4);
47for (const key of [1, 5, 9]) t.put(key, key * 10);
48console.log(`before: capacity ${t.capacity}, n=${t.entryCount}, load factor ${t.loadFactor()}`);
49t.show();
50t.resize(8);
51console.log(`after: capacity ${t.capacity}, n=${t.entryCount}, load factor ${t.loadFactor()}`);
52t.show();
53console.log(`get(5) = ${t.get(5)}`);There is no single correct value. The resize threshold is an implementation policy: grow before an insertion would push the load factor past a chosen limit. Open addressing must grow before the table fills. A chained table keeps working above 1, with longer chains.
Rehashing builds a larger bucket array and reinserts every entry using the new capacity. Key 5 sits in bucket 1 when m = 4, but it belongs in bucket 5 when m = 8.
With the division method, index = k mod m. Load factor is a separate formula, α = n/m, which measures how full the table is.
Expected O(1), not guaranteed. Cost grows with chain length or probe count, which the load factor controls. If every key collides in one chain, a lookup scans all n entries.
Only the insertion that triggers growth transfers n entries. Growing by a constant factor leaves many cheap insertions between resizes, so the O(n) work averages to O(1) per insertion.
A capacity 4 table holding 4 keys has no empty slot for a probe sequence to end on. Check the growth rule before the insertion, not after it fails.