# Cuckoo Hashing  Difficulty Level Hard
Hash Hashing

## 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
How to check if two given sets are disjoint?

### 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 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.

Check if two arrays are equal or not

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
```

Insertion: O(1)