કોયલ હેશિંગ  


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એપિક સિસ્ટમો ફ્લિપકાર્ટ Google માઈક્રોસોફ્ટ Netflix ટેસ્લા
હેશ હેશિંગ

સમસ્યા સ્ટેટમેન્ટ  

કોયલ હેશિંગ એ એવી પદ્ધતિ છે કે જે સમસ્યામાં હલ કરવા માટે વપરાય છે જ્યારે જ્યારે અથડામણ થાય છે હેશ ટેબલ. અથડામણ એ કોષ્ટકમાં હેશ ફંકશનના બે હેશ મૂલ્યોની સંભાવના છે. જ્યારે કોઈ ટેબલના હેશ ફંક્શનમાં સમાન કી માટેના બે હેશ મૂલ્યો થાય છે ત્યારે અથડામણ થાય છે. તે ટક્કરને હલ કરવા માટે આપણે કોયલ હેશિંગનો ઉપયોગ કરીએ છીએ.

નામ પ્રમાણે, કોયલ હેશિંગ હમણાં જ કોયલની કેટલીક લાક્ષણિકતાઓમાંથી ઉતરી આવ્યું છે, કારણ કે કોયલનો ચિક એક ચિક અન્ય છોડના ઇંડા અથવા નાના બાળકોને પોતાને માટે એક જગ્યા બનાવવા માટે માળાની બહાર ધકેલી દે છે. આપણે કોયલ હેશિંગમાં જેવું જ કરીએ છીએ, હેશ ટેબલમાં નવી કી દાખલ કરવાનો પ્રયાસ કરીએ છીએ અમે જૂની કીને નવી જગ્યાએ આગળ ધકેલીએ છીએ. અને તે રીતે કોયલ હેશિંગનો અમલ થયો.

અથડામણ  

જ્યારે નવી કી, જેને આપણે હેશ ટેબલમાં દાખલ કરવાનો પ્રયાસ કરીએ છીએ, તે હેશ ટેબલમાં પહેલેથી જ કબજે કરેલું સ્થાન મળે છે. તે સ્થિતિમાં, આ પરિસ્થિતિને અથડામણ કહેવામાં આવે છે. જ્યારે નવી કી એ સ્થાન શામેલ કરવાની જગ્યા સૂચવે છે જે હેશ ટેબલમાં પહેલેથી જ કબજે છે તેને અથડામણ કહેવામાં આવે છે.

આ પરિસ્થિતિને કેટલાક જોડાણની હેન્ડલિંગ તકનીકોનો ઉપયોગ કરીને નિયંત્રિત કરી શકાય છે.

  • સરનામું અથવા અલગ ચેઇનિંગ બંધ
  • ઓપન એડ્રેસિંગ

સરનામું અથવા અલગ ચેઇનિંગ બંધ

હેશની અથડામણની સમસ્યાઓને નિયંત્રિત કરવા માટે અલગ ચેઇનિંગ એક તકનીક છે કોષ્ટકો. અલગ ચેઇનિંગમાં, ખ્યાલ એ છે કે એક જ હેશ ફંક્શન મૂલ્યો માટે રેકોર્ડ્સ સ્ટોર કરવા માટે કોષને લિંક કરેલી સૂચિમાં જોડવાનો છે.

આ પણ જુઓ
સંતુલિત દ્વિસંગી વૃક્ષ લીટકોડ સોલ્યુશન

ઓપન એડ્રેસિંગ

ટક્કરની સમસ્યાને હલ કરવા માટે ખુલ્લું સરનામું પણ એક પદ્ધતિ છે. ઓપન એડ્રેસિંગમાં, બધી કી અને મૂલ્યો હેશ ટેબલમાં સંગ્રહિત છે. કોષ્ટકનું કદ હેશ ટેબલમાં હાજર કીઓ કરતા વધારે અથવા સમાન હોવું જોઈએ, અને તે કોઈપણ બિંદુએ આવી શકે છે.

કોયલ હેશિંગ

કોયલ હેશિંગમાં, બે વિભાવનાઓ છે કે આ પદ્ધતિ અમલીકરણને પ્રાપ્ત કરવા માટે વપરાય છે જેણે ઓ (1) સૌથી ખરાબ કિસ્સામાં લુક-અપ સમયની બાંયધરી આપી છે.

તે વિભાવનાઓ છે:

મલ્ટીપલ ચોઇસ: અમે F1 (કી) અને F2 (કી) શામેલ કરવાની ચાવી માટે પસંદગીની મંજૂરી આપવા માટે મુક્ત છીએ.

સ્થાનાંતરણ: એક કેસ પણ શક્ય છે કે જ્યારે એફ 1 (કી) અને એફ 2 (કી) બંનેનો કબજો હોય. તેથી, તે કોયલ પક્ષીની લાક્ષણિકતાની ક copyપિ કરવાનો પ્રયાસ કરશે, એવી રીતે કે બાકીના ઇંડા અથવા નાનાને માળામાંથી બહાર કા .ીને. હેશ ટેબલમાં નવી કીને દબાણ કરવાનો પ્રયાસ કરો. તે પછી, તે જૂની કીને નવી જગ્યાએ દબાણ કરી શકે છે. હવે અમને તે જૂની કી માટે કોઈ સ્થાન શોધવામાં સમસ્યા છે.

હવે ત્યાં બે વસ્તુઓ છે. જો તે જૂની કી માટે નવું સ્થાન ખાલી જગ્યા છે, તો તે સારું છે. પણ જો તે ખાલી જગ્યા નથી, તો… ??

જો આ સ્થિતિ થાય છે, તો આપણે તે નવી કીને પણ ડિસ્પ્લે કરવી પડશે અને તેના માટે નવી જગ્યા શોધવી પડશે. હવે જો ફરીથી તે સ્થિતિ થાય, તો આપણે કી માટે વારંવાર ખાલી જગ્યાની ખાલી જગ્યા ન મળે ત્યાં સુધી આપણે કીને ફરીથી કોઈ નવા સ્થાને સ્થાનાંતરિત કરવી પડશે.

 

કોયલ હેશિંગ - સૌથી ખરાબ કેસ ઓ (1)

આ પણ જુઓ
જો આપેલ બે સેટ અસ્પષ્ટ છે કે નહીં તે કેવી રીતે તપાસવું?

મૂળભૂત રીતે, ત્યાં 3 કામગીરી છે જે હેશ ટેબલ (અથવા ભાષાઓમાં કોઈ યોગ્ય પદ્ધતિ) દ્વારા સપોર્ટેડ છે:

  • લુકઅપ (કી): બુલિયન ફંક્શન, જો તે હાજર હોય કે ન હોય તો સાચું / ખોટું પાછું આપે છે.
  • શામેલ કરો (કી): નવી જગ્યા બનાવો અને જો નવી એન્ટ્રી હોય તો તે આઇટમ “કી” ને હેશ ટેબલ પર દાખલ કરો.
  • કા keyી નાખો (કી): હેશ ટેબલમાંથી "કી" કા .ી નાખો.

 

કોયલ હેશિંગપિન કોયલ હેશિંગપિન કોયલ હેશિંગપિન કોયલ હેશિંગપિન કોયલ હેશિંગપિન કોયલ હેશિંગપિન પિન પિન કોયલ હેશિંગપિન પિન

 

કોડ  

કોયલ હેશિંગને અમલમાં મૂકવા માટે સી ++

#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

કોયલ હેશિંગને લાગુ કરવા માટે જાવા કોડ

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

જટિલતા વિશ્લેષણ  

સમય જટિલતા

નિવેશ: ઓ (1)

આ પણ જુઓ
તપાસો કે બે એરે સમાન છે કે નહીં

કાleી નાખવું: ઓ (1)

અવકાશ જટિલતા

ઓ (1) કોઈ વધારાની જગ્યા જરૂરી નથી.