Хөхөө хэшлэх


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Эпик системүүд Flipkart Google-ийн Microsoft- Netflix Tesla
Хаш Хаширч байна

Асуудлын мэдэгдэл

Хөхөө цохих нь а-д мөргөлдөх үед асуудлыг шийдвэрлэхэд ашигладаг арга юм Хэш хүснэгт. Мөргөлдөөн нь хүснэгтэд байгаа хэш функцийн хоёр хэш утгатай байх магадлалтай. Хүснэгтийн хэш функцэд ижил түлхүүрийн хоёр хэш утга гарч ирэхэд мөргөлдөөн үүсдэг. Энэхүү мөргөлдөөнийг арилгахын тулд бид Хөхөө Хэшийг ашигладаг.

Нэрнээс нь харахад Хөхөө Хэшинг нь зөвхөн хөхөө хөхний дэгдээхэйн шинж чанараас үүдэлтэй бөгөөд хөхний дэгдээхэйнүүд өөр өндөгнүүд эсвэл балчируудыг өөртөө зориулж байр гаргахын тулд үүрнээс нь түлхэж эсвэл түлхдэг. Хөх хүснэгтэд шинэ түлхүүр оруулахыг хичээгээд бид хуучин газар шинэ түлхүүрийг түлхэж оруулдаг. Энэ нь Хөхөө Хэшийг хэрхэн хэрэгжүүлсэн юм.

Зөрчилдөөн

Хэш хүснэгтэд оруулах гэж оролдож буй шинэ түлхүүр нь Хэш хүснэгтэд аль хэдийн эзлэгдсэн байрыг олоход. Энэ тохиолдолд энэ нөхцөл байдлыг мөргөлдөөн гэж нэрлэдэг. Хэш хүснэгтэд аль хэдийн орсон байгаа байршилд шинэ түлхүүр оруулахыг мөргөлдөөн гэж нэрлэдэг.

Энэ нөхцөл байдлыг зарим мөргөлдөх арга техникийг ашиглан зохицуулж болно.

  • Хаалттай хаяг эсвэл салангид гинж
  • Хаяг нээх

Хаалттай хаяг эсвэл салангид гинж

Тусгаарлагдсан гинж нь Хэш Хүснэгтүүдийн мөргөлдөөний асуудлыг шийдвэрлэх аргуудын нэг юм. Тусдаа гинжлэхэд ижил төстэй хэш функцийн утгыг хадгалахын тулд холбосон жагсаалтад байгаа нүдийг нэгтгэх явдал юм.

Хаяг нээх

Нээлттэй хаяглалт нь мөргөлдөх асуудлыг шийдвэрлэх арга юм. Нээлттэй хаяглалт дээр бүх түлхүүрүүд болон утгууд нь Hash Table-д хадгалагддаг. Хүснэгтийн хэмжээ нь Hash Table-д байгаа товчлууруудаас их эсвэл тэнцүү байх ёстой бөгөөд энэ нь аль ч үед тохиолдож болно.

Хөхөө хэшлэх

Хөхөөтэй хэш хийхдээ энэ аргыг хэрэгжүүлэхэд O (1) хамгийн тааруухан харагдах хугацааг баталгаажуулсан хоёр ойлголт байдаг.

Эдгээр ойлголтууд нь:

Олон сонголт: Түлхүүрийг F1 (Түлхүүр) ба F2 (түлхүүр) оруулах сонголтыг бид чөлөөтэй хийх боломжтой.

Нүүлгэн шилжүүлэлт: F1 (Түлхүүр) ба F2 (түлхүүр) хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёулаа хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь хоёуланг нь эзэлдэг. Тиймээс энэ нь хөхний шувууны шинж чанарыг бусад өндөгнүүд эсвэл залуу хүүхдүүдийг үүрнээс нь түлхэх байдлаар хуулбарлахыг хичээх болно. Хэш хүснэгтэд шинэ түлхүүр оруулахыг хичээ. Дараа нь хуучин түлхүүрийг шинэ газар руу түлхэж магадгүй юм. Одоо бидэнд тэр хуучин түлхүүрт байр олох асуудал тулгараад байна.

Одоо хоёр зүйл байна. Хэрэв тэр хуучин түлхүүрийн шинэ газар хоосон зай байвал сайн байна. Гэхдээ энэ нь сул газар биш бол ... ??

Хэрэв ийм нөхцөл байдал үүссэн бол бид тэр шинэ түлхүүрийг бас нүүлгэж, түүнд зориулж шинэ газар олох ёстой. Хэрэв энэ нөхцөл байдал дахин давтагдвал бид түлхүүрийн хоосон зайг олох хүртэл шинэ газрыг түлхүүрийг дахин дахин шилжүүлэх хэрэгтэй болно.

 

Хөхөө хагалах - Хамгийн муу тохиолдол O (1)

Үндсэндээ Hash Table (эсвэл хэл дээрх ямар ч тохиромжтой аргыг) дэмждэг 3 үйлдэл байдаг:

  • Хайх (түлхүүр): Булын функц, хэрэв байгаа эсвэл байхгүй бол True / False-ийг буцаана.
  • Оруулах (түлхүүр): Шинэ газар байрлуулж, "Түлхүүр" гэсэн зүйлийг шинэ оруулбал Хэш хүснэгтэд оруулна уу.
  • Устгах (түлхүүр): Хэш хүснэгтээс "Түлхүүр" -ийг устгах.

 

Хөхөө хэшлэх Хөхөө хэшлэх Хөхөө хэшлэх Хөхөө хэшлэх Хөхөө хэшлэх Хөхөө хэшлэх Хөхөө хэшлэх

 

код

Cuckoo Hashing-ийг хэрэгжүүлэх 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

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Оруулга: O (1)

Устгах: O (1)

Сансрын нарийн төвөгтэй байдал

O (1) нэмэлт зай шаардагдахгүй тул.