Кукавичје распршивање


Ниво тешкоће Тежак
Често питани у Епиц Системс Флипкарт гоогле мицрософт Нетфлик Тесла
Хасх Хасхинг

Изјава о проблему

Кукавичко мешање је метода која се користи за решавање проблема када дође до судара у Хасх Табле. Колизије су вероватно две хеш вредности хеш функције у табели. До судара долази када се у хеш-функцији табеле појаве две хеш вредности за исти кључ. Да бисмо решили тај судар користимо кукавичко распршивање.

Као и из имена, Кукавичје расплињавање управо је изведено из неке карактеристике кукавице, јер пилећа кукавица гура или гура друга јајашца или младунце из гнезда како би направила место за себе. Исто што радимо у Цуцкоо Хасхинг-у, покушавајући да у хеш табелу убацимо нови кључ, само гурнемо старији кључ на ново место. И тако је спроведено Цуцкоо Хасхинг.

Судар

Када нови кључ, који покушавамо да убацимо у хеш табелу, нађе већ заузето место у хеш табели. У том случају се ова ситуација назива сударом. Када нови кључ означи место за уметање које је већ заузето у хеш табели назива се колизија.

Ова ситуација се може решити коришћењем неких од техника руковања сударом.

  • Затворено адресирање или одвојени ланац
  • Отворено адресирање

Затворено адресирање или одвојени ланац

Одвојени ланац је једна од техника за решавање проблема колизије хеш столова. У одвојеном ланцу концепт је да се ћелија придружи повезаној листи ради складиштења записа за исте вредности хеш функције.

Отворено адресирање

Отворено адресирање је такође метода за решавање проблема судара. У отвореном адресирању, сви кључеви и вредности се чувају у хеш табели. Величина табеле би требало да буде већа или једнака тастерима присутним у хеш табели и може се догодити у било ком тренутку.

Кукавичје распршивање

У ротирању кукавице постоје два концепта која је овај метод користио за постизање примене која гарантује О (1) најгоре време тражења.

Ти концепти су:

Вишеструки избор: Слободни смо да дозволимо избор кључа за уметање Ф1 (кључ) и Ф2 (кључ).

Пресељење: Могућ је случај и када су заузета Ф1 (кључ) и Ф2 (кључ). Дакле, покушаће да копира карактеристике птице кукавице на начин да из гнезда потискује остала јаја или млађа. У покушају да гурнете нови тастер у хеш табелу. Тада ће старији тастер можда гурнути на ново место. Сада имамо проблем да пронађемо место за тај старији кључ.

Сада су ту две ствари. Ако је ново место за тај старији кључ празан простор, онда је то добро. Али ако није слободно место, онда ... ??

Ако се ово стање догоди, морамо и нови кључ да померимо и пронађемо ново место за њега. Ако се опет догоди тај услов, једноставно морамо више пута премештати кључ на ново место док не пронађемо празно слободно место за кључ.

 

Кукавичкање - најгори случај О (1)

У основи постоје 3 операције које подржавају Хасх табеле (или било која одговарајућа метода у језицима):

  • Претраживање (кључ): Логичка функција, враћа тачно / нетачно ако је присутна или није.
  • Уметни (кључ): Направите ново место и убаците ту ставку „Кључ“ у хеш табелу ако је нови унос.
  • Делете (тастер): Избришите „Кеи“ из табеле хеширања.

 

Кукавичје распршивање Кукавичје распршивање Кукавичје распршивање Кукавичје распршивање Кукавичје распршивање Кукавичје распршивање Кукавичје распршивање

 

код

Ц ++ за примену Цуцкоо Хасхинг-а

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

Брисање: О (1)

Сложеност простора

О (1) јер није потребан додатни простор.