Կուկու Հաշինգ


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Էպիկական համակարգեր Flipkart Google Microsoft Netflix Tesla
Խանգարել Հեշինգ

Խնդիրների հայտարարում

Cuckoo Hashing- ը մեթոդ է, որն օգտագործվում է խնդիրը լուծելու համար, երբ բախում է տեղի ունենում ա-ում Հաշ սեղան, Բախումները հավանական է, որ աղյուսակում hash ֆունկցիայի երկու hash արժեք ունեն: Բախում է տեղի ունենում, երբ միևնույն ստեղնի համար երկու hash արժեք տեղի է ունենում սեղանի hash գործառույթում: Այդ բախումը լուծելու համար մենք օգտագործում ենք Cuckoo Hashing:

Ինչ վերաբերում է անունին, Կուկու Հաշինգը պարզապես առաջացել է կոկուի որոշ բնութագրիչներից, քանի որ կուքի ճուտը ցնցում է կամ մյուս ձվերը կամ երիտասարդներին բույնից դուրս է մղում ՝ ինքնուրույն տեղ ստեղծելու համար: Նույնը, ինչ մենք անում ենք Cuckoo Hashing- ում, փորձելով նոր բանալին տեղադրել հեշ սեղանի մեջ, մենք պարզապես սեղմում ենք հին բանալին դեպի նոր վայր: Եվ այդպես իրականացրեց Կկու Հաշինգը:

Բախում

Երբ նոր բանալին, որը մենք փորձում ենք տեղադրել Hash Table- ում, Hash Table- ում գտնում է արդեն զբաղեցրած տեղ: Այդ դեպքում այս իրավիճակը կոչվում է բախում: Երբ նոր բանալին նշում է տեղադրելու տեղը, որն արդեն զբաղված է Hash աղյուսակում, կոչվում է բախում:

Այս իրավիճակը կարելի է կարգավորել ՝ օգտագործելով բախումների հետ վարվելու որոշ տեխնիկա:

  • Փակ հասցեագրում կամ առանձին շղթայակցում
  • Բաց հասցեագրում

Փակ հասցեագրում կամ առանձին շղթայակցում

The Separated Chaining- ը Hash սեղանների բախման խնդիրները կարգավորելու մեթոդներից մեկն է: Առանձին շղթայակցման մեջ գաղափարը բջիջը միացնել կապակցված ցուցակին ՝ նույն հեշ գործառույթի արժեքների համար գրառումներ պահելու համար:

Բաց հասցեագրում

Բաց հասցեագրումը նաև բախման խնդիրը լուծելու մեթոդ է: Բաց հասցեագրության մեջ բոլոր բանալիները և արժեքները պահվում են Hash աղյուսակում: Աղյուսակի չափը պետք է լինի ավելի մեծ կամ հավասար Hash աղյուսակում առկա ստեղներից, և այն կարող է առաջանալ ցանկացած կետում:

Կուկու Հաշինգ

Cuckoo Hashing- ում կա երկու հասկացություն, որոնք այս մեթոդով օգտագործվել են իրականացմանը հասնելու համար, որը երաշխավորել է O (1) վատթարագույն Փնտրման ժամանակը:

Այդ հասկացություններն են.

Բազմակի ընտրություն. Մենք ազատորեն թույլ ենք տալիս ընտրություն կատարել բանալին F1 (բանալին) և F2 (բանալին) տեղադրելու համար:

Վերաբնակեցում. Հնարավոր է նաև դեպք, երբ F1 (Key) և F2 (key) երկուսն էլ զբաղված լինեն: Այսպիսով, այն կփորձի պատճենել կուչու թռչնի բնութագիրը, այնպես, որ մյուս ձվերը կամ փոքրերին բույնից դուրս մղի: Փորձելով մի նոր բանալի հրել Hash Table- ի մեջ: Այնուհետև այն կարող է հին բանալին նոր վայր մղել: Հիմա մենք խնդիր ունենք տեղ գտնել այդ հին բանալու համար:

Հիմա երկու բան կա: Եթե ​​այդ հին բանալու համար նոր տեղը դատարկ տեղ է, ապա լավ է: Բայց եթե դա թափուր տեղ չէ, ապա… ??

Եթե ​​այս պայմանը առաջանա, ապա մենք պետք է տեղափոխենք նաև այդ նոր բանալին և գտնենք դրա համար նոր տեղ: Եթե ​​նորից այդ պայմանը տեղի ունենա, ապա մենք պարզապես ստիպված ենք բազմիցս բանալին տեղափոխել նոր վայր, մինչև որ գտնենք բանալու համար դատարկ տեղ:

 

Cuckoo Hashing - Ամենավատ դեպքը O (1)

Հիմնականում կա 3 գործողություն, որոնք ապահովվում են Hash աղյուսակի միջոցով (կամ լեզուներով ցանկացած հարմար մեթոդ):

  • Փնտրում (բանալի). Բուլյան գործառույթ, վերադարձնում է ճիշտ / կեղծ, եթե այն առկա է, թե ոչ:
  • Տեղադրել (բանալին). Նոր տեղ դնել և տեղադրել «Բանալին» կետը «Հաշ» սեղանին, եթե նոր գրառում է:
  • Deleteնջել (բանալին). Հաշ աղյուսակից ջնջել «Բանալին»:

 

Կուկու Հաշինգ Կուկու Հաշինգ Կուկու Հաշինգ Կուկու Հաշինգ Կուկու Հաշինգ Կուկու Հաշինգ Կուկու Հաշինգ

 

Կոդ

C ++ ՝ 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 Hashing- ի իրականացման համար 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

Բարդության վերլուծություն

Timeամանակի բարդություն

Տեղադրում. O (1)

Deնջում ՝ O (1)

Տիեզերական բարդություն

Ո (1) քանի որ լրացուցիչ տարածք չի պահանջվում: