Ququ ardıcıllığı proqramı

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Epik Sistemlər Flipkart google microsoft Netflix Tesla
Sükut HashingBaxılıb 53

Problem bəyanatı

Ququ ardıcıllığı proqramı və ya Cuckoo Hashing, bir yerdə toqquşma baş verdikdə problemi həll etmək üçün istifadə edilən bir üsuldur. Hash Cədvəli. Çarpışmalar, ehtimal ki, bir cədvəldəki bir hash funksiyasının iki hash dəyəridir. Bir cədvəlin hash funksiyasında eyni açar üçün iki hash dəyəri meydana gəldiyi zaman toqquşma baş verir. Bu toqquşmanı həll etmək üçün Cuckoo Hashing istifadə edirik.

Adından da göründüyü kimi, Cuckoo Hashing, bir guguğun bir cücəsi, digər yumurtaları və ya cavanları özlərinə yer düzəltmək üçün yuvadan itələdiyi və ya itələdiyi üçün yalnız bir guguğun bəzi xüsusiyyətlərindən qaynaqlanır. Cuckoo Hashing-də etdiyimiz kimi, hash masasına yeni bir düymə əlavə etməyə çalışırıq, yalnız köhnə düyməni yeni yerə itələyirik. Və Guguk Haşinqi belə tətbiq edildi.

toqquşma

Bir Hash Cədvəlinə yerləşdirməyə çalışdığımız yeni bir düymə Hash Table-da artıq işğal olunmuş bir yer tapanda. Bu vəziyyətdə bu vəziyyət bir toqquşma adlanır. Yeni bir düymə, Hash Cədvəlində artıq yerləşdirilmiş bir yerin göstərilməsinə toqquşma deyilir.

Bu vəziyyət bəzi toqquşma işləmə üsullarından istifadə etməklə həll edilə bilər.

  • Qapalı Ünvanlama və ya Ayrı Zəncirləmə
  • Ünvanı açın

Qapalı Ünvanlama və ya Ayrı Zəncirləmə

Ayrılmış Zəncir Hash -ın toqquşma problemlərini həll etmək üsullarından biridir Masaların. Ayrı Zəncirləmə anlayışı, eyni hash funksiyası dəyərləri üçün qeydləri saxlamaq üçün bir hüceyrəni əlaqəli siyahıya qatmaqdır.

Ünvanı açın

Açıq Ünvanlandırma da toqquşma problemini həll etmək üçün bir üsuldur. Açıq Ünvanlandırmada bütün düymələr və dəyərlər Hash Cədvəlində saxlanılır. Cədvəlin ölçüsü Hash Cədvəlində mövcud olan düymələrdən böyük və ya ona bərabər olmalıdır və istənilən nöqtədə baş verə bilər.

Ququ Hashing

Göyquşu qarışıqlığında, bu metodun tətbiq olunmasına nail olmaq üçün istifadə etdiyi iki anlayış var ki, O (1) ən pis baxış müddətini təmin etdi.

Bu anlayışlar:

Birden çox seçim: Bir düymənin F1 (Açar) və F2 (açar) daxil edilməsinə icazə verməkdə sərbəstik.

Yer dəyişdirmə: F1 (Açar) və F2 (açar) hər ikisi işğal edildiyi bir vəziyyət də mümkündür. Beləliklə, başqa bir yumurtanı və ya daha kiçik olanları yuvadan itələyəcək şəkildə bir ququ quşunun xüsusiyyətini kopyalamağa çalışacağıq. Hash Table-a yeni bir düyməni basmağa çalışın. Sonra köhnə düyməni yeni bir yerə itələyə bilər. İndi o köhnə düyməyə yer tapmaqda problemimiz var.

İndi iki şey var. Bu köhnə düymə üçün yeni bir yer boş bir yerdirsə, yaxşıdır. Ancaq boş bir yer deyilsə, o zaman ... ??

Əgər bu vəziyyət yaranarsa, o yeni açarı da yerimizdən dəyişməli və bunun üçün yeni bir yer tapmalıyıq. Yenidən bu vəziyyət baş verərsə, açar üçün boş yer tapana qədər açarı təkrar-təkrar yeni yerə köçürməliyik.

 

Cuckoo Hashing - Ən pis hal O (1)

Əsasən, bir Hash Cədvəli (və ya Dillərdə hər hansı bir uyğun metod) tərəfindən dəstəklənən 3 əməliyyat vardır:

  • Axtarış (açar): Bir Boolean funksiyası, Varsa və ya olmasa True / False qaytarır.
  • Daxil edin (açar): Yeni bir yer düzəldin və yeni bir giriş olarsa, "Açar" maddəsini Hash Cədvəlinə daxil edin.
  • Sil (düymə): Hash Cədvəlindən "Düyməni" silin.

 

Ququ HashingPin Ququ HashingPin Ququ HashingPin Ququ HashingPin Ququ HashingPin Ququ HashingPin Pin Pin Ququ HashingPin Pin

 

Kodu

Cuckoo Hashing tətbiq etmək üçün 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-da kuku ardıcıllığı proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Taxmaq: O (1)

Silinmə: O (1)

Kosmik Mürəkkəblik

O (1) əlavə yer tələb olunmadığı üçün.

Translate »
1