15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Separate chaining resolves hash collisions by letting each array slot hold a bucket of entries. A key goes to bucket h(k), and each operation scans only that bucket, comparing real keys. Expected cost is O(1 + α), where α is the load factor n/m. The worst case is O(n), when every key shares one bucket.
| Insert, search, delete | O(1 + L), where L is the length of the selected bucket |
|---|---|
| Expected time | O(1 + α) with α = n/m, if keys spread evenly |
| Worst case time | O(n), all n keys in one bucket |
| Space | O(m + n): m bucket references plus n entries |
| Invariant | every stored key k lives only in bucket h(k) |
| Example | m = 5: keys 12, 7 and 17 all land in bucket 2 as [12, 7, 17] |
The lesson assumes you can already:
h(k) = k mod m;A hash table has a primary array of m buckets. A bucket is the collection stored at one array index.
With separate chaining, each bucket can hold multiple entries. Separate chaining handles a collision when two different keys produce the same index without either key replacing the other.
For this lesson, each entry stores one integer key. The table is a set, so a key is either present once or absent.
Use a table with capacity:
and this hash function:
Perform these operations in order:
1271771212Start with five empty buckets.
| Bucket index | Entries |
|---|---|
| 0 | [] |
| 1 | [] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
Now compute the three hash indices:
All three keys collide at bucket 2. Separate chaining keeps all three in that one bucket.
Separate chaining in one picture: 12, 7 and 17 all hash to bucket 2 and share its chain. A search examines only that one bucket and must check every entry before it can say a key is absent.
| Bucket index | Entries |
|---|---|
| 0 | [] |
| 1 | [] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
No keys are stored yet.
Compute the bucket index first:
Bucket 2 is empty, so create its first entry.
| Bucket index | Entries |
|---|---|
| 0 | [] |
| 1 | [] |
| 2 | [12] |
| 3 | [] |
| 4 | [] |
Compute the index:
Bucket 2 already contains 12. Compare the requested key against 12:
Append 7 to this bucket. Keep 12.
| Bucket index | Entries |
|---|---|
| 0 | [] |
| 1 | [] |
| 2 | [12, 7] |
| 3 | [] |
| 4 | [] |
Compute the index:
Scan bucket 2 for an equal key:
12 ≠ 177 ≠ 17No entry matches 17, so append it.
| Bucket index | Entries |
|---|---|
| 0 | [] |
| 1 | [] |
| 2 | [12, 7, 17] |
| 3 | [] |
| 4 | [] |
Compute the index:
Only bucket 2 can contain 7. Search its entries in order:
12 with 7: not equal.7 with 7: equal.Report that 7 is present.
Compute the index:
Bucket 2 is:
1[12, 7, 17]The matching entry is the first entry. Remove only 12. The remaining entries stay in their original order.
1[7, 17]| Bucket index | Entries |
|---|---|
| 0 | [] |
| 1 | [] |
| 2 | [7, 17] |
| 3 | [] |
| 4 | [] |
Compute the index:
Search bucket 2:
7 with 12: not equal.17 with 12: not equal.The bucket is now exhausted. Report that 12 is absent.
An unsuccessful search must finish the selected bucket. Finding a nonempty bucket is insufficient.
After each completed operation, the following statement remains true:
Every stored key
kappears in exactly one bucket: bucketh(k). Keys in other buckets are never examined for a lookup ofk.
The statement is the bucket-placement invariant.
In the example:
12, 7, and 17 all hash to 2.2.7 examines bucket 2, not buckets 0, 1, 3, or 4.12 removes one matching entry from bucket 2; it does not affect 7 or 17.The integer set also requires each key to appear at most once. Before inserting a key, scan its bucket for an equal key. If the key is already present, do not append another copy.
Each operation begins with these steps:
index = h(key).buckets[index].To insert a key:
Appending preserves colliding keys already stored there.
To search for a key:
The hash index narrows the search location. Key equality determines whether the requested key is present.
To remove a key:
For an array-like bucket representation, removing entry i shifts later entries one position left. For a linked-chain representation, removing an entry changes the link that bypasses that one node. Either representation must preserve the other bucket entries.
1ChainedIntSet
2 m: positive integer
3 buckets: array of m buckets
4 each bucket is an ordered sequence of integer keys
5
6Hash(key, m)
7 Input: integer key; positive integer m
8 Return: an integer index in [0, m - 1]
9 Behavior: returns key mod m for this lesson's exampleThe operations below mutate the set when stated. They do not inspect buckets other than buckets[Hash(key, set.m)].
11 Insert(set, key)
22 Input: ChainedIntSet set, integer key
33 Return: true if key was added; false if key was already present
44 Mutation: may append key to exactly one bucket
55 index ← Hash(key, set.m)
66 bucket ← set.buckets[index]
77 for each storedKey in bucket
88 if storedKey = key
99 return false
1010 append key to bucket
1111 return true11 Contains(set, key)
22 Input: ChainedIntSet set, integer key
33 Return: true if key is present; otherwise false
44 Mutation: none
55 index ← Hash(key, set.m)
66 bucket ← set.buckets[index]
77 for each storedKey in bucket
88 if storedKey = key
99 return true
1010 return false11 Remove(set, key)
22 Input: ChainedIntSet set, integer key
33 Return: true if key was removed; false if key was absent
44 Mutation: may remove exactly one matching entry from one bucket
55 index ← Hash(key, set.m)
66 bucket ← set.buckets[index]
77 for position from 0 to Length(bucket) - 1
88 if bucket[position] = key
99 remove the entry at position from bucket
1010 return true
1111 return falseThe boundary in Remove is 0 through Length(bucket) - 1. If the bucket is empty, that range has no positions, so the loop does not run.
Use the original example:
1m = 5
2Hash(key, 5) = key mod 5Initially:
| Index | Bucket |
|---|---|
| 0 | [] |
| 1 | [] |
| 2 | [] |
| 3 | [] |
| 4 | [] |
Insert(set, 12)index ← Hash(12, 5) = 2.bucket ← set.buckets[2], which is [].storedKey values to inspect.12 to bucket 2.true.State:
1bucket 2 = [12]Insert(set, 7)index ← Hash(7, 5) = 2.bucket ← set.buckets[2], which is [12].storedKey = 12.12 = 7 is false.7.true.State:
1bucket 2 = [12, 7]Insert(set, 17)index ← Hash(17, 5) = 2.bucket ← set.buckets[2], which is [12, 7].storedKey = 12.12 = 17 is false.storedKey = 7.7 = 17 is false.17.true.State:
1bucket 2 = [12, 7, 17]Contains(set, 7)index ← Hash(7, 5) = 2.bucket ← set.buckets[2], which is [12, 7, 17].storedKey = 12.12 = 7 is false.storedKey = 7.7 = 7 is true.true.No bucket changes.
Remove(set, 12)index ← Hash(12, 5) = 2.bucket ← set.buckets[2], which is [12, 7, 17].position = 0.bucket[0] = 12, so 12 = 12 is true.0.2 changes from [12, 7, 17] to [7, 17].true.Contains(set, 12)index ← Hash(12, 5) = 2.bucket ← set.buckets[2], which is [7, 17].storedKey = 7.7 = 12 is false.storedKey = 17.17 = 12 is false.false.The final table is:
| Bucket index | Entries |
|---|---|
| 0 | [] |
| 1 | [] |
| 2 | [7, 17] |
| 3 | [] |
| 4 | [] |
Before insertion, the bucket-placement invariant says every existing key is in its own hash bucket.
Insert computes Hash(key, set.m) and scans only that bucket.
h(key). The new key is in its required bucket.Insertion preserves the bucket-placement invariant and does not create a duplicate key.
Consider the loop in Contains. Before each comparison, every earlier entry in the selected bucket has already been checked and shown not equal to key.
key, the algorithm moves to the next entry. The checked prefix now contains one more entry, and none of its entries equals key.true, which is correct. If the loop ends, every entry in bucket h(key) has been checked and none matched.The bucket-placement invariant places key in no other bucket. Returning false after exhausting the selected bucket is correct.
Consider the loop in Remove. Before each iteration, every earlier position in the selected bucket has been checked and did not match key. Those entries are still present.
0, no entries have been examined, so the statement holds.bucket[position] = key, the algorithm removes exactly that entry and returns. All other entries stay in the bucket, so neighboring colliding keys are preserved.h(key) was checked and no match exists. The algorithm returns false without changing the table.Remove deletes a present key, preserves other entries, and correctly reports an absent key.
Let:
n be the total number of stored entries;m be the number of buckets;L be the number of entries in the one bucket selected by a key;Each operation first computes h(key) once. That costs:
The operation then scans at most L entries in one bucket.
Contains compares up to L keys.Insert checks up to L keys for a duplicate before appending.Remove checks up to L keys to locate the matching entry.Each operation costs:
Under an even-distribution assumption, the expected bucket length is approximately the load factor:
Expected operation time is:
In the example after inserting three keys into five buckets:
One bucket can be longer than the average: bucket 2 has three entries while the other four buckets are empty.
In the worst case, all n keys collide in one bucket. An operation may then inspect all n entries:
The primary bucket array stores m bucket references, which uses:
The entries themselves use:
The table storage is:
The operations use auxiliary space when scanning existing bucket entries without copying them.
Incorrect insertion idea:
1buckets[Hash(key, m)] ← [key]The assignment replaces the whole bucket instead of retaining its existing entries.
Exposing input:
1m = 5
2insert 12
3insert 7
4search 12Both keys hash to bucket 2.
Wrong state after inserting 7:
1bucket 2 = [7]Wrong result:
1search 12 → falseCorrection: scan bucket 2 for duplicates, then append 7 while keeping 12.
1bucket 2 = [12, 7]Incorrect search assumption:
1if Length(buckets[Hash(key, m)]) > 0
2 return trueExposing input:
1m = 5
2bucket 2 contains [12]
3search 7Since:
the search reaches a nonempty bucket. 12 is not 7.
Wrong result:
1search 7 → trueCorrection: compare key equality for each entry in the selected bucket.
112 ≠ 7The bucket ends, so the correct result is:
1search 7 → falseIncorrect deletion line:
1buckets[Hash(key, m)] ← []Exposing input:
1m = 5
2bucket 2 contains [12, 7]
3delete 12
4search 7Wrong state after deletion:
1bucket 2 = []Wrong result:
1search 7 → falseCorrection: remove only the matching entry.
1bucket 2 = [7]Then:
1search 7 → true| Operation | Starting bucket | Expected result |
|---|---|---|
Insert 12 | [] | [12] |
Search 7 | [] | absent, with no comparisons |
Remove 12 | [12, 7] | [7] |
Remove 12 | [12] | [] |
Insert duplicate 7 into a set | [7] | unchanged [7] |
For a map instead of a set, a duplicate key must follow the map API: update its value or reject the duplicate. It must not create ambiguous duplicate entries for the same key.
Implement a chained integer set with these operations:
1insert(key)
2contains(key)
3remove(key)The tested contract is:
contains must compare keys within that bucket;Executable tests will insert colliding keys, verify that each remains findable, remove one key, and verify that the other colliding keys remain present.
1class ChainedIntSet:
2 def __init__(self, m):
3 self.m = m
4 self.buckets = [[] for _ in range(m)]
5
6 def hash(self, key):
7 return key % self.m
8
9 def insert(self, key):
10 bucket = self.buckets[self.hash(key)]
11 for stored in bucket:
12 if stored == key: # set: never store a key twice
13 return False
14 bucket.append(key)
15 return True
16
17 def contains(self, key):
18 for stored in self.buckets[self.hash(key)]:
19 if stored == key:
20 return True
21 return False # only after the whole bucket is checked
22
23 def remove(self, key):
24 bucket = self.buckets[self.hash(key)]
25 for position in range(len(bucket)):
26 if bucket[position] == key:
27 del bucket[position] # remove this entry only
28 return True
29 return False
30
31def lower(flag):
32 return str(flag).lower()
33
34s = ChainedIntSet(5)
35for k in (12, 7, 17):
36 print(f"insert {k}: {lower(s.insert(k))}")
37print("contains 7:", lower(s.contains(7)))
38print("remove 12:", lower(s.remove(12)))
39print("contains 12:", lower(s.contains(12)))
40for i, bucket in enumerate(s.buckets):
41 print(f"bucket {i}: [{', '.join(map(str, bucket))}]")1import java.util.ArrayList;
2import java.util.List;
3
4public class Main {
5 static class ChainedIntSet {
6 final int m;
7 final List<List<Integer>> buckets = new ArrayList<>();
8
9 ChainedIntSet(int m) {
10 this.m = m;
11 for (int i = 0; i < m; i++) buckets.add(new ArrayList<>());
12 }
13
14 int hash(int key) { return key % m; }
15
16 boolean insert(int key) {
17 List<Integer> bucket = buckets.get(hash(key));
18 for (int stored : bucket) {
19 if (stored == key) return false; // set: never store a key twice
20 }
21 bucket.add(key);
22 return true;
23 }
24
25 boolean contains(int key) {
26 for (int stored : buckets.get(hash(key))) {
27 if (stored == key) return true;
28 }
29 return false; // only after the whole bucket is checked
30 }
31
32 boolean remove(int key) {
33 List<Integer> bucket = buckets.get(hash(key));
34 for (int position = 0; position < bucket.size(); position++) {
35 if (bucket.get(position) == key) {
36 bucket.remove(position); // remove this entry only
37 return true;
38 }
39 }
40 return false;
41 }
42 }
43
44 public static void main(String[] args) {
45 ChainedIntSet s = new ChainedIntSet(5);
46 for (int k : new int[]{12, 7, 17}) {
47 System.out.println("insert " + k + ": " + s.insert(k));
48 }
49 System.out.println("contains 7: " + s.contains(7));
50 System.out.println("remove 12: " + s.remove(12));
51 System.out.println("contains 12: " + s.contains(12));
52 for (int i = 0; i < s.m; i++) {
53 System.out.println("bucket " + i + ": " + s.buckets.get(i));
54 }
55 }
56}1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct ChainedIntSet {
6 int m;
7 vector<vector<int>> buckets;
8
9 explicit ChainedIntSet(int m) : m(m), buckets(m) {}
10
11 int hash(int key) const { return key % m; }
12
13 bool insert(int key) {
14 auto& bucket = buckets[hash(key)];
15 for (int stored : bucket) {
16 if (stored == key) return false; // set: never store a key twice
17 }
18 bucket.push_back(key);
19 return true;
20 }
21
22 bool contains(int key) const {
23 for (int stored : buckets[hash(key)]) {
24 if (stored == key) return true;
25 }
26 return false; // only after the whole bucket is checked
27 }
28
29 bool remove(int key) {
30 auto& bucket = buckets[hash(key)];
31 for (size_t position = 0; position < bucket.size(); position++) {
32 if (bucket[position] == key) {
33 bucket.erase(bucket.begin() + position); // remove this entry only
34 return true;
35 }
36 }
37 return false;
38 }
39};
40
41const char* flag(bool b) { return b ? "true" : "false"; }
42
43int main() {
44 ChainedIntSet s(5);
45 for (int k : {12, 7, 17}) {
46 cout << "insert " << k << ": " << flag(s.insert(k)) << endl;
47 }
48 cout << "contains 7: " << flag(s.contains(7)) << endl;
49 cout << "remove 12: " << flag(s.remove(12)) << endl;
50 cout << "contains 12: " << flag(s.contains(12)) << endl;
51 for (int i = 0; i < s.m; i++) {
52 cout << "bucket " << i << ": [";
53 for (size_t j = 0; j < s.buckets[i].size(); j++) cout << (j ? ", " : "") << s.buckets[i][j];
54 cout << "]" << endl;
55 }
56}1class ChainedIntSet {
2 constructor(m) {
3 this.m = m;
4 this.buckets = Array.from({ length: m }, () => []);
5 }
6
7 hash(key) { return key % this.m; }
8
9 insert(key) {
10 const bucket = this.buckets[this.hash(key)];
11 for (const stored of bucket) {
12 if (stored === key) return false; // set: never store a key twice
13 }
14 bucket.push(key);
15 return true;
16 }
17
18 contains(key) {
19 for (const stored of this.buckets[this.hash(key)]) {
20 if (stored === key) return true;
21 }
22 return false; // only after the whole bucket is checked
23 }
24
25 remove(key) {
26 const bucket = this.buckets[this.hash(key)];
27 for (let position = 0; position < bucket.length; position++) {
28 if (bucket[position] === key) {
29 bucket.splice(position, 1); // remove this entry only
30 return true;
31 }
32 }
33 return false;
34 }
35}
36
37const s = new ChainedIntSet(5);
38for (const k of [12, 7, 17]) console.log(`insert ${k}: ${s.insert(k)}`);
39console.log(`contains 7: ${s.contains(7)}`);
40console.log(`remove 12: ${s.remove(12)}`);
41console.log(`contains 12: ${s.contains(12)}`);
42s.buckets.forEach((bucket, i) => console.log(`bucket ${i}: [${bucket.join(', ')}]`));Chaining stores colliding entries together in a bucket. Open addressing keeps every entry inside the array and probes to another slot. Chaining deletes by removing one entry. Open addressing leaves a DELETED marker so later probes still pass through.
Hashing maps a key to an array index. With m = 5 and h(k) = k mod 5, key 12 goes to index 2. Keys 7 and 17 also go to 2, so a chained table stores [12, 7, 17] in bucket 2.
Find the matching entry in bucket h(k) and remove only that entry. Clearing the whole bucket loses the neighbors: deleting 12 from [12, 7] must leave [7].
A nonempty bucket does not prove the key is there. Bucket 2 holding [12] says nothing about 7. Only after every entry fails the equality check is the key absent.
A linked list or a dynamic array. With an array, removing entry i shifts later entries left. With a linked list, you change the link that skips one node. Either way the other entries must survive.
Only in expectation. Each operation costs O(1 + L). If keys spread evenly, L averages the load factor. If all keys collide, one operation scans all n entries.