Cuckoo Hashing  

Difficulty Level Hard
Frequently asked in Epic Systems Flipkart Google Microsoft Netflix Tesla
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.

Please click Like if you loved this article?

  • Closed Addressing or Separate Chaining
  • Open Addressing
See also
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

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.

See also
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.

 

Cuckoo HashingPin Cuckoo HashingPin Cuckoo HashingPin Cuckoo HashingPin Cuckoo HashingPin Cuckoo HashingPin Pin Pin Cuckoo HashingPin Pin

 

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)

Please click Like if you loved this article?

See also
Minimum sum of multiplications of n numbers

Deletion: O(1)

Space Complexity

O(1) as no extra space is required.

Please click Like if you loved this article?