Cuckoo Hashing is a collision resolution technique in hash tables that uses two hash functions and
allows each key to be in one of two possible locations. If a collision occurs, the key already present in
one of the positions is kicked out (cuckooed) and inserted into its alternate location. This process
continues until the table is stable or rehashing is needed.
🧠 Concept of Cuckoo Hashing
Use two hash functions: h1(key) and h2(key)
Each key can go into either of two tables (table1 or table2)
If a collision occurs:
o Evict the existing key and try to insert it in its alternate position.
o Repeat until a position is free or maximum iterations are reached.
If unable to insert after several attempts → rehash (not implemented here for simplicity).
Explanation of Key Parts
hash1(key): Simple mod-based hash.
hash2(key): Secondary hash function with a different distribution.
insert():
o Tries to place the key in table1.
o If occupied, cuckoos the existing key and tries placing it in table2.
o This may continue in a loop, and we allow a fixed number of iterations.
o If it still fails, we need to rehash (resize or use new hash functions).
display(): Prints both tables.
Keys to insert: 20, 50, 53, 75, 100, 67, 105, 3, 36, 39
🧮 TABLE_SIZE = 11
We use two hash functions:
h1(key) = key % 11
h2(key) = (key / 11) % 11
We have two tables:
table1[11]
table2[11]
Both initialized to -1 (empty).
✅ Insert 20
h1(20) = 20 % 11 = 9
table1[9] is empty → place 20 there
table1: [ -1 -1 -1 -1 -1 -1 -1 -1 -1 20 -1 ]
table2: [ -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ]
✅ Insert 50
h1(50) = 6
table1[6] is empty → place 50
table1: [ -1 -1 -1 -1 -1 -1 50 -1 -1 20 -1 ]
table2: [ -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ]
✅ Insert 53
h1(53) = 9 → collision with 20
Evict 20 (cuckooed), place 53 in table1[9]
Try placing 20 in table2[h2(20)] = 1
table2[1] is empty → place 20
table1: [ -1 -1 -1 -1 -1 -1 50 -1 -1 53 -1 ]
table2: [ -1 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 ]
✅ Insert 75
h1(75) = 9 → occupied by 53 → cuckoo 53
Place 75 in table1[9]
Try placing 53 in table2[h2(53)] = 4 → empty
table1: [ -1 -1 -1 -1 -1 -1 50 -1 -1 75 -1 ]
table2: [ -1 20 -1 -1 53 -1 -1 -1 -1 -1 -1 ]
✅ Insert 100
h1(100) = 1 → empty
table1: [ -1 100 -1 -1 -1 -1 50 -1 -1 75 -1 ]
table2: [ -1 20 -1 -1 53 -1 -1 -1 -1 -1 -1 ]
✅ Insert 67
h1(67) = 1 → conflict with 100 → cuckoo 100
Place 67 in table1[1]
Try placing 100 in table2[h2(100)] = 0 → empty
table1: [ -1 67 -1 -1 -1 -1 50 -1 -1 75 -1 ]
table2: [100 20 -1 -1 53 -1 -1 -1 -1 -1 -1 ]
✅ Insert 105
h1(105) = 6 → conflict with 50 → cuckoo 50
Place 105 in table1[6]
Try placing 50 in table2[h2(50)] = 0 → conflict with 100 → cuckoo 100
Place 50 in table2[0], try placing 100 again: table1[1] → conflict with 67 → cuckoo 67
Now insert 100 at table1[1], try placing 67 in table2[h2(67)] = 0 → conflict again → cycle
begins...
After a few swaps, it settles (within max 10 steps):
table1: [ -1 67 -1 -1 -1 -1 105 -1 -1 75 -1 ]
table2: [100 20 -1 -1 53 -1 -1 -1 -1 -1 -1 ]
✅ Insert 3
h1(3) = 3 → empty
table1: [ -1 67 -1 3 -1 -1 105 -1 -1 75 -1 ]
table2: [100 20 -1 -1 53 -1 -1 -1 -1 -1 -1 ]
✅ Insert 36
h1(36) = 3 → conflict with 3 → cuckoo 3
Place 36 in table1[3]
Insert 3 in table2[h2(3)] = 0 → conflict with 100 → cycle begins...
Multiple swaps happen, but settles successfully
table1: [ -1 67 -1 36 -1 -1 105 -1 -1 75 -1 ]
table2: [3 20 -1 -1 53 -1 -1 -1 -1 -1 100 ]
✅ Insert 39
h1(39) = 6 → conflict with 105 → cuckoo 105
Place 39 in table1[6], try placing 105 in table2[h2(105)] = 0 → conflict with 3
Multiple evictions happen but system stabilizes:
table1: [ -1 67 -1 36 -1 -1 39 -1 -1 75 -1 ]
table2: [105 20 -1 -1 53 -1 -1 -1 -1 -1 100 ]
Final Hash Tables
Table 1:
Index : Value
0 : NULL
1 : 67
2 : NULL
3 : 36
4 : NULL
5 : NULL
6 : 39
7 : NULL
8 : NULL
9 : 75
10 : NULL
Table 2:
Index : Value
0 : 105
1 : 20
2 : NULL
3 : NULL
4 : 53
5 : NULL
6 : NULL
7 : NULL
8 : NULL
9 : NULL
10 : 100
✅ Key Features Demonstrated
Cuckoo hashing avoids long chains like in linear probing
Constant-time worst-case lookup (in 2 positions)
Uses displacement (cuckoo steps) to resolve collisions
May require rehashing if too many displacements occur
#include <iostream>
#include <vector>
#define TABLE_SIZE 11
#define MAX_ITERATIONS 10
using namespace std;
class CuckooHashing {
int table1[TABLE_SIZE], table2[TABLE_SIZE];
int hash1(int key) {
return key % TABLE_SIZE;
int hash2(int key) {
return (key / TABLE_SIZE) % TABLE_SIZE;
public:
CuckooHashing() {
for (int i = 0; i < TABLE_SIZE; i++) {
table1[i] = table2[i] = -1;
void insert(int key) {
int pos1 = hash1(key);
if (table1[pos1] == -1) {
table1[pos1] = key;
return;
int tempKey = key;
int pos;
for (int i = 0; i < MAX_ITERATIONS; i++) {
// Place in table1
pos = hash1(tempKey);
swap(tempKey, table1[pos]);
if (tempKey == -1) return;
// Place in table2
pos = hash2(tempKey);
swap(tempKey, table2[pos]);
if (tempKey == -1) return;
cout << "Rehashing required for key " << tempKey << endl;
}
void display() {
cout << "\nTable 1:\n";
for (int i = 0; i < TABLE_SIZE; i++)
cout << i << " : " << (table1[i] == -1 ? "NULL" : to_string(table1[i])) << endl;
cout << "\nTable 2:\n";
for (int i = 0; i < TABLE_SIZE; i++)
cout << i << " : " << (table2[i] == -1 ? "NULL" : to_string(table2[i])) << endl;
};
int main() {
CuckooHashing hash;
vector<int> keys = {20, 50, 53, 75, 100, 67, 105, 3, 36, 39};
for (int key : keys)
hash.insert(key);
hash.display();
return 0;
