Table of Contents

## Problem Statment

Cuckoo Hashing is a method used to solve the problem when a collision occurs in a Hash Table. Collisions are likely of two hash values of a hash function in a table. A collision occurs when two hash values for the same key occurs in the hash function of a table. To resolve that collision we use Cuckoo Hashing.

As from the name, Cuckoo Hashing is just derived from some characteristic of a cuckoo, as a chick of the cuckoo shove or pushes the other eggs or the young ones out of the nest to make a place for own. The same we do in Cuckoo Hashing, trying to insert a new key into the hash table we just push the older key to the new place. And that is how Cuckoo Hashing implemented.

## Collision

When a new key, which we try to insert in a Hash Table find an already occupied place in a Hash Table. In that case, this situation is called a collision. When a new key indicates a place to be inserted which is already occupied in a Hash Table is called a collision.

This situation can be handled by using some of the Collision handling techniques.

- Closed Addressing or Separate Chaining
- Open Addressing

### Closed Addressing or Separate Chaining

The Separated Chaining is one of the techniques to handle collision problems of Hash Tables. In Separate Chaining, the concept is to join a cell to a linked list to store records for the same hash function values.

### Open Addressing

Open Addressing is also a method to resolve the problem of collision. In Open Addressing, all of the keys and values are stored in a Hash Table. The size of the table should be greater than or equal to the keys present in a Hash Table, and it can occur at any point.

### Cuckoo Hashing

In a Cuckoo Hashing, there are two concepts that this method used to achieve the implementation which has guaranteed O(1) worst-case Look-Up time.

Those concepts are:

Multiple Choice: We are free to allow a choice for a Key to be inserted F1 (Key) and F2 (key).

Relocation: A case is also possible that when F1 (Key) and F2 (key) both are occupied. So, it will try to copy the characteristic of a cuckoo bird, in a manner that pushing rest other eggs or the younger ones out of the nest. In a try to push a new key into the Hash Table. Then, it may push the older key to a new place. Now we have a problem to find a place for that older key.

Now two things are there. If a new place for that older key is an empty space, then it is good. But if it is not a vacant place, then…??

If this condition occurs then we have to displace that new key as well and find a new place for it. Now if again that condition occurs, then we just have to repeatedly displace the key to a new place until we find an empty of vacant space for the key.

Cuckoo Hashing – Worst case O(1)

Basically, there are 3 operations that supported by a Hash Table (or any suitable method In Languages) :

- Lookup(key): A Boolean function, Returns True/False if it is present or not.
- Insert(key): Make a new place and insert that item “Key” to the Hash Table if a new entry.
- Delete(key): Delete the “Key” from the Hash Table.

## Code

### C++ to implement Cuckoo Hashing

#include<bits/stdc++.h> #define TNO 2 #define MOD 6 using namespace std; int cuckooTable[TNO][MOD]; int POSITION[TNO]; void fillTable() { for (int j=0; j<MOD; j++) for (int i=0; i<TNO; i++) cuckooTable[i][j] = INT_MIN; } void printTable() { cout<<"Hash Tables are:\n"<<endl; for (int i=0; i<TNO; i++, printf("\n")) { int k=i+1; cout<<"Table: "<<k<<"-> "; for (int j=0; j<MOD; j++) { if(cuckooTable[i][j]==INT_MIN) cout<<" N "; else cout<<" "<<cuckooTable[i][j]; } } cout<<endl; } int getHashValue(int function, int key) { switch (function) { case 1: return key%MOD; case 2: return (key/MOD)%MOD; } } void getArrange(int key, int id, int c, int n) { if (c==n) { cout<<key<< " do not have a position\n"<<endl; //cycle present rehash return; } for (int i=0; i<TNO; i++) { POSITION[i] = getHashValue(i+1, key); if (cuckooTable[i][POSITION[i]] == key) return; } if (cuckooTable[id][POSITION[id]]!=INT_MIN) { int dis = cuckooTable[id][POSITION[id]]; cuckooTable[id][POSITION[id]] = key; getArrange(dis, (id+1)%TNO, c+1, n); } else cuckooTable[id][POSITION[id]] = key; } void cuckooFunction(int keys[], int n) { fillTable(); for (int i=0, c=0; i<n; i++, c=0) getArrange(keys[i], 0, c, n); printTable(); } int main() { int keyTable1[] = {77, 53, 44, 37, 24, 55}; int n = sizeof(keyTable1)/sizeof(int); cuckooFunction(keyTable1, n); int keyTable2[] = {77, 53, 44, 37, 24, 55}; int m = sizeof(keyTable2)/sizeof(int); cuckooFunction(keyTable2, m); return 0; }

Hash Tables are: Table: 1-> 24 55 44 N N 77 Table: 2-> 37 N 53 N N N Hash Tables are: Table: 1-> 24 55 44 N N 77 Table: 2-> 37 N 53 N N N

### Java code to implement Cuckoo Hashing

import java.util.*; class CuckooHashing { private static int MOD = 6; private static int TNO = 2; private static int [][]cuckooTable = new int[TNO][MOD]; private static int []POSITION = new int[TNO]; public static void fillTable() { for (int j = 0; j < MOD; j++) for (int i = 0; i < TNO; i++) cuckooTable[i][j] = Integer.MIN_VALUE; } public static int getHashValue(int function, int key) { switch (function) { case 1: return key % MOD; case 2: return (key / MOD) % MOD; } return Integer.MIN_VALUE; } public static void getArrange(int key, int id, int c, int n) { if (c == n) { System.out.println(key+" is not have a position"); return; } for (int i = 0; i < TNO; i++) { POSITION[i] = getHashValue(i + 1, key); if (cuckooTable[i][POSITION[i]] == key) return; } if (cuckooTable[id][POSITION[id]] != Integer.MIN_VALUE) { int dis = cuckooTable[id][POSITION[id]]; cuckooTable[id][POSITION[id]] = key; getArrange(dis, (id + 1) % TNO, c + 1, n); } else cuckooTable[id][POSITION[id]] = key; } public static void printTable() { System.out.println("Hash Tables are:"); for (int i = 0; i < TNO; i++, System.out.println()) { int t=i+1; System.out.print(" Table: " + t+" --> " ); for (int j = 0; j < MOD; j++) { if(cuckooTable[i][j] == Integer.MIN_VALUE) System.out.print(" N "); else System.out.print(" "+ cuckooTable[i][j]); } System.out.println(); } } public static void cuckooFunction(int keys[], int n) { fillTable(); for (int i = 0, cnt = 0; i < n; i++, cnt = 0) getArrange(keys[i], 0, cnt, n); printTable(); } public static void main(String[] args) { int KeysTable1[] = {77, 53, 44, 37, 24, 55}; int n = KeysTable1.length; cuckooFunction(KeysTable1, n); int KeysTable2[] = {77, 53, 44, 37, 24, 55}; int m = KeysTable2.length; cuckooFunction(KeysTable2, m); } }

Hash Tables are: Table: 1 --> 24 55 44 N N 77 Table: 2 --> 37 N 53 N N N Hash Tables are: Table: 1 --> 24 55 44 N N 77 Table: 2 --> 37 N 53 N N N

## Complexity Analysis

### Time Complexity

Insertion: O(1)

Deletion: O(1)

### Space Complexity

**O(1) **as no extra space is required.