Cuckoo sequence program

Difficulty Level Hard
Frequently asked in Epic Systems Flipkart Google Microsoft Netflix Tesla
Hash HashingViews 3691

Problem Statment

Cuckoo sequence program or 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.

 

Cuckoo Hashing Cuckoo Hashing Cuckoo Hashing Cuckoo Hashing Cuckoo Hashing Cuckoo Hashing Cuckoo Hashing

 

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

Cuckoo sequence program in Java

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.

Translate »