გუგული ჰაშინგი


Რთული ტური Hard
ხშირად ეკითხებიან ეპიკური სისტემები Flipkart Google microsoft Netflix Tesla
Hash ჰაშინგი

პრობლემის შეფასება

გუგული ჰაშინგი არის მეთოდი, რომელიც გამოიყენება პრობლემის გადასაჭრელად, როდესაც შეჯახება ხდება ა ჰეშის მაგიდა. შეჯახება სავარაუდოდ hash ფუნქციის ორი hash მნიშვნელობისაა. შეჯახება ხდება მაშინ, როდესაც ერთი და იგივე გასაღების ორი ჰეშის მნიშვნელობა ხდება ცხრილის ჰეშის ფუნქციაში. ამ შეჯახების მოსაგვარებლად ვიყენებთ Cuckoo Hashing.

სახელიდან გამომდინარე, Cuckoo Hashing უბრალოდ გამომდინარეობს გუგულისთვის დამახასიათებელი თვისებებით, რადგან გუგულის წიწილა ნიჩბებს ან უბიძგებს სხვა კვერცხუჯრედებს ან ახალშობილებს ბუდედან, რომ ადგილი გაუჩნდეს თავისთვის. იგივე გავაკეთოთ Cuckoo Hashing- ში, ვცდილობთ ჩასვათ ახალი გასაღები ჰეშის ცხრილში, ჩვენ უბრალოდ ვრთავთ უფროს კლავიშს ახალ ადგილას. და ასე გამოიყენა გუგული ჰეშინგმა.

შეჯახების

როდესაც ახალი გასაღები, რომლის ჩასმას ვცდილობთ Hash Table- ში, იპოვნებს Hash Table- ში უკვე დაკავებულ ადგილს. ამ შემთხვევაში, ამ სიტუაციას ეწოდება შეჯახება. როდესაც ახალი გასაღები მიუთითებს ჩასასმელად ადგილას, რომელიც უკვე არის დაკავებული Hash Table- ში, ეწოდება შეჯახება.

ამ სიტუაციის მოგვარება შესაძლებელია შეჯახების მართვის ზოგიერთი ტექნიკის გამოყენებით.

  • დახურული მისამართით ან ცალკეული ჯაჭვით
  • გახსენით მისამართები

დახურული მისამართით ან ცალკეული ჯაჭვით

განცალკევებული ჯაჭვა არის ერთ-ერთი ტექნიკა ჰეშ მაგიდების შეჯახების პრობლემების მოსაგვარებლად. ცალკე ჯაჭვაში, კონცეფციაა უჯრედის მიერთება დაკავშირებულ სიაში, რათა შეინახოს ჩანაწერები იგივე ჰეშის ფუნქციის მნიშვნელობებისთვის.

გახსენით მისამართები

ღია მიმართვა ასევე არის მეთოდი შეჯახების პრობლემის გადასაჭრელად. ღია მისამართით, ყველა გასაღები და მნიშვნელობა ინახება Hash ცხრილში. ცხრილის ზომა უნდა იყოს მეტი ან ტოლი ჰეშის ცხრილში მოცემული გასაღებისა და ის შეიძლება მოხდეს ნებისმიერ წერტილში.

გუგული ჰაშინგი

Cuckoo Hashing- ში არსებობს ორი ცნება, რომლითაც ეს მეთოდი გამოიყენება იმპლემენტაციის მისაღწევად, რამაც უზრუნველყო O (1) უარეს შემთხვევაში Look-Up დრო.

ეს ცნებებია:

მრავალჯერადი არჩევანი: ჩვენ თავისუფლად დავუშვებთ არჩევანს, რომ გასაღები ჩასმული იყოს F1 (გასაღები) და F2 (გასაღები).

გადაადგილება: ასევე შესაძლებელია შემთხვევა, როდესაც F1 (გასაღები) და F2 (გასაღები) ორივე დაკავებულია. ასე რომ, ის შეეცდება დააკოპიროს გუგული ფრინველის მახასიათებელი, ისე, რომ სხვა კვერცხუჯრედები ან უფრო ახალგაზრდა კვერცხუჯრედები ბუდიდან გამოვიდეს. ცდილობენ ახალი გასაღები ჩაუშვან Hash Table- ში. შემდეგ, მას შეუძლია ძველი გასაღები ახალი ადგილისკენ მიიტანოს. ახლა ჩვენ გვაქვს პრობლემა, რომ იპოვოთ ადგილი ამ ძველი გასაღებისთვის.

ახლა ორი რამ არის. თუ ამ ძველი გასაღების ახალი ადგილი ცარიელი ადგილია, კარგია. თუ ეს არ არის ვაკანტური ადგილი, მაშინ… ??

თუ ეს მდგომარეობა მოხდა, ჩვენ უნდა გადავანაწილოთ ეს ახალი გასაღებიც და ვიპოვნოთ ახალი ადგილი. თუ ისევ მოხდა ეს მდგომარეობა, ჩვენ უბრალოდ განმეორებით უნდა გადავაადგილოთ გასაღები ახალი ადგილისთვის, სანამ არ ვიპოვებთ გასაღების ცარიელ ადგილს.

 

გუგული ჰაშინგი - ყველაზე ცუდი შემთხვევა O (1)

ძირითადად, არსებობს 3 ოპერაცია, რომელსაც მხარს უჭერს Hash Table (ან სხვა შესაფერისი მეთოდი ენებში):

  • ძიება (გასაღები): ლოგიკური ფუნქცია, უბრუნებს მართებულს / მცდარს, თუ ის არის თუ არა.
  • ჩასმა (გასაღება): გააკეთეთ ახალი ადგილი და ჩასვით ჰეშის ცხრილში ეს პუნქტი "გასაღები", თუ ახალი ჩანაწერია.
  • წაშლა (გასაღები): წაშალეთ "გასაღები" ჰეშის ცხრილიდან.

 

გუგული ჰაშინგი გუგული ჰაშინგი გუგული ჰაშინგი გუგული ჰაშინგი გუგული ჰაშინგი გუგული ჰაშინგი გუგული ჰაშინგი

 

კოდი

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

Java კოდი Cuckoo Hashing- ის განსახორციელებლად

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) რადგან დამატებითი ადგილი არ არის საჭირო.