קוקיה האשינג


רמת קושי קשה
נשאל לעתים קרובות מערכות אפיות Flipkart Google מיקרוסופט נטפליקס טסלה
בליל חבטות

הצהרת בעיות

Hashing קוקיה היא שיטה המשמשת לפתרון הבעיה כאשר מתרחשת התנגשות ב- טבלת גיבוב. ככל הנראה התנגשויות הן שני ערכי חשיש של פונקציית חשיש בטבלה. התנגשות מתרחשת כאשר שני ערכי hash לאותו מפתח מתרחשים בפונקציית ה- hash של הטבלה. כדי לפתור את ההתנגשות הזו אנו משתמשים בקוקי האשינג.

מהשם, קוקיה האשינג פשוט נגזר מאפיין כלשהו של קוקיה, כשגוזל הקוקיה דוחף או דוחף את הביצים האחרות או את הצעירים אל מחוץ לקן כדי ליצור מקום לבד. אותו דבר אנו עושים בקוקו האשינג, כשמנסים להכניס מפתח חדש לטבלת החשיש פשוט דוחפים את המקש הישן למקום החדש. וכך מיושם קוקיה האשינג.

התנגשות

כאשר מפתח חדש, אותו אנו מנסים להכניס לטבלת Hash, ימצא מקום שכבר תפוס בטבלת Hash. במקרה זה, מצב זה נקרא התנגשות. כאשר מפתח חדש מציין מקום להכנס שכבר תפוס בטבלת Hash נקרא התנגשות.

ניתן לטפל במצב זה באמצעות כמה מטכניקות הטיפול בהתנגשות.

  • כתובת סגורה או שרשור נפרד
  • פתח כתובת

כתובת סגורה או שרשור נפרד

השרשור המופרד הוא אחת הטכניקות לטיפול בבעיות התנגשות של שולחנות האש. בשרשרת נפרדת, הרעיון הוא להצטרף לתא לרשימה מקושרת כדי לאחסן רשומות עבור אותם ערכי פונקציית hash.

פתח כתובת

כתובת פתוחה היא גם שיטה לפתרון בעיית ההתנגשות. בכתובת פתוחה, כל המקשים והערכים נשמרים בטבלת Hash. גודל הטבלה צריך להיות גדול או שווה למפתחות הקיימים בטבלת Hash, והיא יכולה להתרחש בכל נקודה.

קוקיה האשינג

ב- Cuckoo Hashing, ישנם שני מושגים ששיטה זו השתמשה בהם כדי להשיג את היישום אשר הבטיח את זמן ה- Look (Up) במקרה הגרוע ביותר.

מושגים אלה הם:

בחירה מרובה: אנו חופשיים לאפשר אפשרות להכניס מפתח F1 (מפתח) ו- F2 (מפתח).

רילוקיישן: ייתכן גם מקרה שכאשר F1 (מפתח) ו- F2 (מפתח) שניהם תפוסים. לכן, היא תנסה להעתיק את המאפיין של ציפור קוקיה, באופן שדוחף מנוחה של ביצים אחרות או את הצעירות מהקן. בניסיון לדחוף מפתח חדש לטבלת Hash. לאחר מכן, הוא עשוי לדחוף את המקש הישן למקום חדש. עכשיו יש לנו בעיה למצוא מקום לאותו מפתח ישן יותר.

עכשיו שני דברים שם. אם מקום חדש לאותו מפתח ישן יותר הוא מקום ריק, הוא טוב. אבל אם זה לא מקום פנוי, אז ??

אם מצב זה מתרחש, עלינו לעקור גם את אותו מפתח חדש ולמצוא לו מקום חדש. עכשיו אם שוב התנאי הזה מתרחש, עלינו רק להזיז את המפתח שוב ושוב למקום חדש עד שנמצא מקום ריק ריק למפתח.

 

קוקיה האשינג - המקרה הגרוע ביותר O (1)

בעיקרון, ישנן 3 פעולות הנתמכות על ידי טבלת Hash (או כל שיטה מתאימה בשפות):

  • חיפוש (מפתח): פונקציה בוליאנית, מחזירה נכון / לא נכון אם היא קיימת או לא.
  • הוסף (מפתח): צור מקום חדש והוסף את הפריט "מפתח" לטבלת Hash אם ערך חדש.
  • מחק (מפתח): מחק את ה"מפתח "מטבלת ה- Hash.

 

קוקיה האשינג קוקיה האשינג קוקיה האשינג קוקיה האשינג קוקיה האשינג קוקיה האשינג קוקיה האשינג

 

קופונים

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

קוד ג'אווה ליישום הקוקו האשינג

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) מכיוון שלא נדרש מקום נוסף.