Кукушка  


Күрделілік дәрежесі қиын
Жиі кіреді Эпикалық жүйелер Flipkart Google Microsoft Netflix Tesla
Hash Хэш

Проблемалық мәлімдеме  

Кукушка - бұл а-да соқтығысу кезінде проблеманы шешу үшін қолданылатын әдіс Хэш кестесі. Соқтығысулар кестедегі хэш функциясының екі хэш мәніне байланысты болуы мүмкін. Соқтығысу бір кілтке арналған екі хэш мәні кестенің хэш функциясында пайда болған кезде пайда болады. Бұл соқтығысуды шешу үшін біз Кукушка Хэшингті қолданамыз.

Куку-хэш деген атқа сәйкес, кукудың кейбір сипаттамаларынан алынған, өйткені кукушаның балапаны өздеріне орын жасау үшін ұядан басқа жұмыртқаларды немесе балаларды итеріп шығарады немесе итереді. Біз кукушки-хэштеу кезінде де, хэш-кестеге жаңа кілт енгізуге тырысып, ескі кілтті жаңа орынға басамыз. Міне, осылай Кукуш Хэшинг іске асырылды.

Қақтығыс  

Hash Table-ге енгізуге тырысатын жаңа кілт Hash Table-де қазірдің өзінде ээленген орынды тапқанда. Бұл жағдайда бұл жағдай коллизия деп аталады. Егер Hash кестесінде орналасқан жаңа кілт енгізілетін орынды көрсетсе, соқтығысу деп аталады.

Бұл жағдайды кейбір соқтығысу тәсілдерін қолдану арқылы шешуге болады.

  • Жабық мекен-жай немесе бөлек тізбек
  • Ашық мекен-жай

Жабық мекен-жай немесе бөлек тізбек

Бөлінген тізбек - Хэштің соқтығысу мәселелерін шешудің әдістерінің бірі кестелер. Бөлек тізбекте тұжырымдама - бұл ұяшықтарды байланыстың тізіміне қосу, хэш функциясының бірдей мәндері үшін жазбаларды сақтау.

Сондай-ақ, қараңыз
Теңдестірілген екілік ағаштың парақ кодының шешімі

Ашық мекен-жай

Ашық мекенжай - бұл соқтығысу мәселесін шешудің әдісі. Ашық мекен-жайда барлық кілттер мен мәндер хэш кестесінде сақталады. Кестенің өлшемі Hash кестесінде бар кілттерден үлкен немесе оған тең болуы керек және ол кез келген нүктеде орын алуы мүмкін.

Кукушка

Кукушки-хэштеуде бұл әдіс іске асырылуда екі ұғым бар, бұл O (1) ең нашар қарау уақытына кепілдік береді.

Бұл ұғымдар:

Бірнеше таңдау: біз F1 (Key) және F2 (key) енгізілетін кілт таңдауына еркін бола аламыз.

Орын ауыстыру: F1 (Key) және F2 (key) екеуі де орналасуы мүмкін жағдай. Сонымен, кукуша құсының сипаттамасын басқа жұмыртқаларды немесе жас балаларды ұядан шығаратындай етіп көшіруге тырысады. Хэш кестесіне жаңа кілтті итеріп көріңіз. Содан кейін ол ескі кілтті жаңа орынға итермелеуі мүмкін. Енді бізде сол ескі кілтке орын табу қиын.

Қазір екі нәрсе бар. Егер бұл ескі кілт үшін жаңа орын бос орын болса, онда бұл жақсы. Егер бұл бос орын болмаса, онда… ??

Егер бұл жағдай орын алса, онда біз сол жаңа кілтті ауыстырып, оған жаңа орын табуымыз керек. Енді бұл жағдай қайталанатын болса, онда біз кілт үшін бос орынды тапқанға дейін кілтті жаңа орынға бірнеше рет ауыстыруымыз керек.

 

Кукушка Hashing - Ең жаман жағдай O (1)

Сондай-ақ, қараңыз
Берілген екі жиынтықтың бөлінгендігін қалай тексеруге болады?

Негізінде, Hash кестесі (немесе тілдердегі кез-келген қолайлы әдіс) қолдайтын 3 операция бар:

  • Іздеу (кілт): Логикалық функция, егер ол бар болса немесе жоқ болса, True / False мәнін қайтарады.
  • Кірістіру (кілт): жаңа орын жасап, егер «Кілт» элементін Hash кестесіне жаңа жазба енгізіңіз.
  • Жою (кілт): Хэш кестесінен «Кілтті» жою.

 

Кукушкатүйреуіш Кукушкатүйреуіш Кукушкатүйреуіш Кукушкатүйреуіш Кукушкатүйреуіш Кукушкатүйреуіш түйреуіш түйреуіш Кукушкатүйреуіш түйреуіш

 

код  

Кукушка хэштеуді жүзеге асыру үшін C ++

#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 коды

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

Күрделілікті талдау  

Уақыттың күрделілігі

Енгізу: O (1)

Сондай-ақ, қараңыз
Екі массивтің тең немесе тең еместігін тексеріңіз

Жою: O (1)

Ғарыштың күрделілігі

O (1) өйткені қосымша орын қажет емес.