درهم سازی فاخته — به زبان ساده

۵۹ بازدید
آخرین به‌روزرسانی: ۱۹ تیر ۱۴۰۲
زمان مطالعه: ۱۱ دقیقه
درهم سازی فاخته -- به زبان ساده

در این مطلب، «درهم سازی فاخته» (Cuckoo Hashing) که به آن درهم سازی کوکو نیز گفته می‌شود، مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java) و «سی‌شارپ» (#C) انجام شده است. شایان ذکر است، پیش از این در مطلب «تابع هش یا درهم سازی (Hash Function) چیست؟ — به زبان ساده» به مفهوم «درهم‌سازی» (Hash) پرداخته شد. به طور کلی، سه عملیات پایه وجود دارد که باید به وسیله یک «جدول درهم‌سازی» (Hash Table) (یا یک دیکشنری) پشتیبانی شود.

  • Lookup(key)‎: در صورتی که «کلید» (Key) در «جدول» (Table) وجود داشته باشد، «درست» (True) و در غیر این صورت، «غلط» (False) بازگردانده می‌شود.
  • Insert(key)‎: عنصر «key» را در صورتی که تاکنون نمایش داده نشده باشد، به جدول اضافه می‌کند.
  • Delete(key)‎: این دستور، «key» را از جدول حذف می‌کند.

امکان وقوع تصادم حتی در صورتی که یک جدول بزرگ برای ذخیره‌سازی کلیدها موجود باشد، وجود دارد. در واقع، «مساله تاریخ تولد» (Birthday Problem) یا «پارادوکس تولد» (Birthday Paradox) در اینجا مصداق دارد. با تنها ۲۳ نفر، احتمال آنکه دو نفر دارای روز تولد یکسانی باشند، ۵۰ درصد است. سه استراتژی کلی برای حل تصادم درهم‌سازی وجود دارد.

  • آدرس‌دهی بسته یا زنجیری (Closed addressing یا Chaining): عناصر دارای تصادم را در یک ساختار داده موقت مانند یک لیست لینکی یا درخت جستجوی دودویی ذخیره می‌کند.
  • آدرس‌دهی باز (Open Addressing): این امکان را فراهم می‌کند که عناصر از سطل هدف خود سر ریز شوند و به فضای دیگری بریزند.

اگرچه، راهکار بالا هزینه جستجوی (lookup) مورد انتظار O(1)‎ را فراهم می‌کند، هزینه بدترین حالت مورد نظر جستجو در آدرس‌دهی باز (با کاوش خطی) از درجه Ω(log n)‎ و در آدرس‌دهی زنجیری ساده برابر با Θ(log n / log log n)‎ است. برای حذف شکاف زمان مورد انتظار و زمان مورد انتظار بدترین حالت، دو راهکار قابل استفاده است.

  • درهم‌سازی چند انتخابی: به هر عنصر، چندین انتخاب برای موقعیتی که می‌تواند درجدول درهم‌سازی مستقر شود می‌دهد.
  • درهم‌سازی با موقعیت‌دهی مجدد: این امکان را فراهم می‌کند تا عناصر موجود در جدول هش پس از قرارگیری در محل خود، جا به جا شوند.

درهم سازی فاخته

درهم سازی کوکو (Cuckoo Hashing) ایده چند انتخابی و موقعیت‌دهی مجدد را با هم پیاده‌سازی و بدترین زمان جستجوی O(1) ‎ را تضمین می‌کند.

چند انتخابی: به یک کلید، دو انتخاب h1(key)‎ و h2(key)‎ برای استقرار داده می‌شود.

موقعیت‌دهی مجدد: هنگامی اتفاق می‌افتد که h1(key)‎ و h2(key)‎ از پیش به کار گرفته شده باشند. این موضوع، با مساله تقلید پرنده فاخته حل می‌شود. فاخته، دیگر تخم‌مرغ‌ها یا فاخته‌های جوان را وقتی که تخم‌گذاری می‌کند، از لانه خارج می‌کند.

به طور مشابه، درج یک کلید جدید در جدول هش فاخته ممکن است موجب قرارگیری یک کلید قدیمی‌تر در موقعیت دیگری شود. این مساله موجب می‌شود تا کاربر با مساله جایگذاری مجدد کلید قدیمی‌تر مواجه شود. اگر موقعیت جایگزین کلید قدیمی‌تر خالی است، مشکلی وجود ندارد.

در غیر این صورت، کلید قدیمی‌تر، کلید دیگری را جا به جا می‌کند. این کار تا زمانی ادامه پیدا می‌کند که «رویه» (Procedure) یک موقعیت خالی پیدا کند یا وارد یک چرخه شود. در شرایط چرخه، تابع‌های درهم‌سازی جدید انتخاب می‌شوند و کل ساختار داده «درهم‌سازی مجدد» (Rehashed) می‌شود. درهم‌سازی‌های مجدد ممکن است پیش از موفقیت الگوریتم کوکو لازم باشند.

  • درج از درجه O(1)‎ با احتمال بالا است، حتی وقتی احتمال درهم‌سازی مجدد در نظر گرفته می‌شود، تا هنگامی که عدد کلیدها زیر نیمی از ظرفیت جدول هش نگه داشته می‌شود (برای مثال، عامل بارگذاری زیر ٪۵۰ است) درج از همین درجه خواهد بود.
  • حذف در بدترین حالت نیز از درجه O(1)‎ است. زیرا نیاز به بررسی دو موقعیت در جدول درهم‌سازی دارد.

روش کار الگوریتم بالا، به صورت زیر است.

ورودی:

{20, 50, 53, 75, 100, 67, 105, 3, 36, 39}

تابع هش:

h1(key) = key%11
h2(key) = (key/11)%11

درهم سازی فاخته -- به زبان ساده

کار با درج ۲۰ در موقعیت ممکن برای آن در اولین جدولی که به وسیله h1(20)‎ تعبیه شده، انجام می‌شود.

درهم سازی فاخته -- به زبان ساده

بعدی: ۵۰

درهم سازی فاخته -- به زبان ساده

بعدی: ۵۳. داریم که h1(53) = 9. اما ۲۰ در حال حاضر در ۹ قرار دارد. ۵۳ در جدول ۱ و ۲۰ در جدول ۲ در h2(20)‎ قرار داده می‌شود.

درهم سازی فاخته -- به زبان ساده

بعدی: ۷۵. داریم که h1(75) = 9. اما ۵۳ در حال حاضر در ۹ قرار دارد. ۷۵ در جدول ۱ و ۵۳ در جدول ۲ در h2(53)‎ قرار می‌گیرد.

درهم سازی فاخته -- به زبان ساده

بعدی: ۱۰۰. h1(100) = 1.

درهم سازی فاخته -- به زبان ساده

بعدی: ۶۷. داریم که h1(67) = 1. اما، ۱۰۰ در حال حاضر در آنجا در ۱ قرار دارد. ۶۷ در جدول ۱ و ۱۰۰ در جدول ۲ قرار داده می‌شود.

درهم سازی فاخته -- به زبان ساده

بعدی: ۱۰۵. داریم که h1(105) = 6. اما ۵۰ در حال حاضر در آنجا و در ۶ قرار دارد. ۱۰۵ در جدول ۱ و ۵۰ در جدول ۲ در h2(50) = 4 قرار می‌گیرد. اکنون، ۵۳ جایگزین شده است.  h1(53) = 9. اکنون، ۷۵ جا به جا شده است. h2(75) = 6.

درهم سازی فاخته -- به زبان ساده

بعدی ۳. داریم که h1(3) = 3.

درهم سازی فاخته -- به زبان ساده

بعدی: ۳۶. داریم که h1(36) = 3 و h2(3) = 0.

درهم سازی فاخته -- به زبان ساده

بعدی: ۳۹. داریم که h1(39) = 6 و h2(105) = 9 و h1(100) = 1 و h2(67) = 6 و h1(75) = 9 و h2(53) = 4 و h1(50) = 6 و h2(39) = 3.

در اینجا، کلید جدید ۳۹، بعدا در فراخوانی‌های بازگشتی جا به جا شده است تا ۱۰۵ را جایگذاری کند که جا به جا شده است.

درهم سازی فاخته -- به زبان ساده

درهم سازی فاخته در ++C

// C++ program to demonstrate working of Cuckoo 
// hashing. 
#include<bits/stdc++.h> 
  
// upper bound on number of elements in our set 
#define MAXN 11 
  
// choices for position 
#define ver 2 
  
// Auxiliary space bounded by a small multiple 
// of MAXN, minimizing wastage 
int hashtable[ver][MAXN]; 
  
// Array to store possible positions for a key 
int pos[ver]; 
  
/* function to fill hash table with dummy value 
 * dummy value: INT_MIN 
 * number of hashtables: ver */
void initTable() 
{ 
    for (int j=0; j<MAXN; j++) 
        for (int i=0; i<ver; i++) 
            hashtable[i][j] = INT_MIN; 
} 
  
/* return hashed value for a key 
 * function: ID of hash function according to which 
    key has to hashed 
 * key: item to be hashed */
int hash(int function, int key) 
{ 
    switch (function) 
    { 
        case 1: return key%MAXN; 
        case 2: return (key/MAXN)%MAXN; 
    } 
} 
  
/* function to place a key in one of its possible positions 
 * tableID: table in which key has to be placed, also equal 
   to function according to which key must be hashed 
 * cnt: number of times function has already been called 
   in order to place the first input key 
 * n: maximum number of times function can be recursively 
   called before stopping and declaring presence of cycle */
void place(int key, int tableID, int cnt, int n) 
{ 
    /* if function has been recursively called max number 
       of times, stop and declare cycle. Rehash. */
    if (cnt==n) 
    { 
        printf("%d unpositioned\n", key); 
        printf("Cycle present. REHASH.\n"); 
        return; 
    } 
  
    /* calculate and store possible positions for the key. 
     * check if key already present at any of the positions. 
      If YES, return. */
    for (int i=0; i<ver; i++) 
    { 
        pos[i] = hash(i+1, key); 
        if (hashtable[i][pos[i]] == key) 
           return; 
    } 
  
    /* check if another key is already present at the 
       position for the new key in the table 
     * If YES: place the new key in its position 
     * and place the older key in an alternate position 
       for it in the next table */
    if (hashtable[tableID][pos[tableID]]!=INT_MIN) 
    { 
        int dis = hashtable[tableID][pos[tableID]]; 
        hashtable[tableID][pos[tableID]] = key; 
        place(dis, (tableID+1)%ver, cnt+1, n); 
    } 
    else //else: place the new key in its position 
       hashtable[tableID][pos[tableID]] = key; 
} 
  
/* function to print hash table contents */
void printTable() 
{ 
    printf("Final hash tables:\n"); 
  
    for (int i=0; i<ver; i++, printf("\n")) 
        for (int j=0; j<MAXN; j++) 
            (hashtable[i][j]==INT_MIN)? printf("- "): 
                     printf("%d ", hashtable[i][j]); 
  
    printf("\n"); 
} 
  
/* function for Cuckoo-hashing keys 
 * keys[]: input array of keys 
 * n: size of input array */
void cuckoo(int keys[], int n) 
{ 
    // initialize hash tables to a dummy value (INT-MIN) 
    // indicating empty position 
    initTable(); 
  
    // start with placing every key at its position in 
    // the first hash table according to first hash 
    // function 
    for (int i=0, cnt=0; i<n; i++, cnt=0) 
        place(keys[i], 0, cnt, n); 
  
    //print the final hash tables 
    printTable(); 
} 
  
/* driver function */
int main() 
{ 
    /* following array doesn't have any cycles and 
       hence  all keys will be inserted without any 
       rehashing */
    int keys_1[] = {20, 50, 53, 75, 100, 67, 105, 
                    3, 36, 39}; 
  
    int n = sizeof(keys_1)/sizeof(int); 
  
    cuckoo(keys_1, n); 
  
    /* following array has a cycle and hence we will 
       have to rehash to position every key */
    int keys_2[] = {20, 50, 53, 75, 100, 67, 105, 
                    3, 36, 39, 6}; 
  
    int m = sizeof(keys_2)/sizeof(int); 
  
    cuckoo(keys_2, m); 
  
    return 0; 
}

درهم سازی کوکو (فاخته) در جاوا

// Java program to demonstrate working of  
// Cuckoo hashing. 
import java.util.*; 
  
class GFG  
{ 
  
// upper bound on number of elements in our set 
static int MAXN = 11; 
  
// choices for position 
static int ver = 2; 
  
// Auxiliary space bounded by a small multiple 
// of MAXN, minimizing wastage 
static int [][]hashtable = new int[ver][MAXN]; 
  
// Array to store possible positions for a key 
static int []pos = new int[ver]; 
  
/* function to fill hash table with dummy value 
* dummy value: INT_MIN 
* number of hashtables: ver */
static void initTable() 
{ 
    for (int j = 0; j < MAXN; j++) 
        for (int i = 0; i < ver; i++) 
            hashtable[i][j] = Integer.MIN_VALUE; 
} 
  
/* return hashed value for a key 
* function: ID of hash function according to which 
    key has to hashed 
* key: item to be hashed */
static int hash(int function, int key) 
{ 
    switch (function) 
    { 
        case 1: return key % MAXN; 
        case 2: return (key / MAXN) % MAXN; 
    } 
    return Integer.MIN_VALUE; 
} 
  
/* function to place a key in one of its possible positions 
* tableID: table in which key has to be placed, also equal 
  to function according to which key must be hashed 
* cnt: number of times function has already been called 
  in order to place the first input key 
* n: maximum number of times function can be recursively 
  called before stopping and declaring presence of cycle */
static void place(int key, int tableID, int cnt, int n) 
{ 
    /* if function has been recursively called max number 
    of times, stop and declare cycle. Rehash. */
    if (cnt == n) 
    { 
        System.out.printf("%d unpositioned\n", key); 
        System.out.printf("Cycle present. REHASH.\n"); 
        return; 
    } 
  
    /* calculate and store possible positions for the key. 
    * check if key already present at any of the positions. 
    If YES, return. */
    for (int i = 0; i < ver; i++) 
    { 
        pos[i] = hash(i + 1, key); 
        if (hashtable[i][pos[i]] == key) 
        return; 
    } 
  
    /* check if another key is already present at the 
       position for the new key in the table 
    * If YES: place the new key in its position 
    * and place the older key in an alternate position 
    for it in the next table */
    if (hashtable[tableID][pos[tableID]] != Integer.MIN_VALUE) 
    { 
        int dis = hashtable[tableID][pos[tableID]]; 
        hashtable[tableID][pos[tableID]] = key; 
        place(dis, (tableID + 1) % ver, cnt + 1, n); 
    } 
    else // else: place the new key in its position 
    hashtable[tableID][pos[tableID]] = key; 
} 
  
/* function to print hash table contents */
static void printTable() 
{ 
    System.out.printf("Final hash tables:\n"); 
  
    for (int i = 0; i < ver; i++, System.out.printf("\n")) 
        for (int j = 0; j < MAXN; j++) 
            if(hashtable[i][j] == Integer.MIN_VALUE)  
                System.out.printf("- "); 
            else
                System.out.printf("%d ", hashtable[i][j]); 
  
    System.out.printf("\n"); 
} 
  
/* function for Cuckoo-hashing keys 
* keys[]: input array of keys 
* n: size of input array */
static void cuckoo(int keys[], int n) 
{ 
    // initialize hash tables to a dummy value  
    // (INT-MIN) indicating empty position 
    initTable(); 
  
    // start with placing every key at its position in 
    // the first hash table according to first hash 
    // function 
    for (int i = 0, cnt = 0; i < n; i++, cnt = 0) 
        place(keys[i], 0, cnt, n); 
  
    // print the final hash tables 
    printTable(); 
} 
  
// Driver Code 
public static void main(String[] args)  
{ 
    /* following array doesn't have any cycles and 
    hence all keys will be inserted without any 
    rehashing */
    int keys_1[] = {20, 50, 53, 75, 100,  
                    67, 105, 3, 36, 39}; 
  
    int n = keys_1.length; 
  
    cuckoo(keys_1, n); 
  
    /* following array has a cycle and hence we will 
    have to rehash to position every key */
    int keys_2[] = {20, 50, 53, 75, 100,  
                    67, 105, 3, 36, 39, 6}; 
  
    int m = keys_2.length; 
  
    cuckoo(keys_2, m); 
} 
}  
  
// This code is contributed by Princi Singh

درهم سازی فاخته در #C

// C# program to demonstrate working of  
// Cuckoo hashing. 
using System; 
      
class GFG  
{ 
  
// upper bound on number of 
// elements in our set 
static int MAXN = 11; 
  
// choices for position 
static int ver = 2; 
  
// Auxiliary space bounded by a small  
// multiple of MAXN, minimizing wastage 
static int [,]hashtable = new int[ver, MAXN]; 
  
// Array to store  
// possible positions for a key 
static int []pos = new int[ver]; 
  
/* function to fill hash table  
with dummy value 
* dummy value: INT_MIN 
* number of hashtables: ver */
static void initTable() 
{ 
    for (int j = 0; j < MAXN; j++) 
        for (int i = 0; i < ver; i++) 
            hashtable[i, j] = int.MinValue; 
} 
  
/* return hashed value for a key 
* function: ID of hash function  
according to which key has to hashed 
* key: item to be hashed */
static int hash(int function, int key) 
{ 
    switch (function) 
    { 
        case 1: return key % MAXN; 
        case 2: return (key / MAXN) % MAXN; 
    } 
    return int.MinValue; 
} 
  
/* function to place a key in one of  
its possible positions 
* tableID: table in which key  
has to be placed, also equal to function 
according to which key must be hashed 
* cnt: number of times function has already  
been called in order to place the first input key 
* n: maximum number of times function  
can be recursively called before stopping and 
declaring presence of cycle */
static void place(int key, int tableID,  
                  int cnt, int n) 
{ 
    /* if function has been recursively  
    called max number of times, 
    stop and declare cycle. Rehash. */
    if (cnt == n) 
    { 
        Console.Write("{0} unpositioned\n", key); 
        Console.Write("Cycle present. REHASH.\n"); 
        return; 
    } 
  
    /* calculate and store possible positions  
    * for the key. Check if key already present  
    at any of the positions. If YES, return. */
    for (int i = 0; i < ver; i++) 
    { 
        pos[i] = hash(i + 1, key); 
        if (hashtable[i, pos[i]] == key) 
        return; 
    } 
  
    /* check if another key is already present  
    at the position for the new key in the table 
    * If YES: place the new key in its position 
    * and place the older key in an alternate position 
    for it in the next table */
    if (hashtable[tableID,  
              pos[tableID]] != int.MinValue) 
    { 
        int dis = hashtable[tableID, pos[tableID]]; 
        hashtable[tableID, pos[tableID]] = key; 
        place(dis, (tableID + 1) % ver, cnt + 1, n); 
    } 
    else // else: place the new key in its position 
    hashtable[tableID, pos[tableID]] = key; 
} 
  
/* function to print hash table contents */
static void printTable() 
{ 
    Console.Write("Final hash tables:\n"); 
  
    for (int i = 0; i < ver; 
             i++, Console.Write("\n")) 
        for (int j = 0; j < MAXN; j++) 
            if(hashtable[i, j] == int.MinValue)  
                Console.Write("- "); 
            else
                Console.Write("{0} ", 
                        hashtable[i, j]); 
  
    Console.Write("\n"); 
} 
  
/* function for Cuckoo-hashing keys 
* keys[]: input array of keys 
* n: size of input array */
static void cuckoo(int []keys, int n) 
{ 
    // initialize hash tables to a  
    // dummy value (INT-MIN) 
    // indicating empty position 
    initTable(); 
  
    // start with placing every key  
    // at its position in the first  
    // hash table according to first  
    // hash function 
    for (int i = 0, cnt = 0; 
             i < n; i++, cnt = 0) 
        place(keys[i], 0, cnt, n); 
  
    // print the final hash tables 
    printTable(); 
} 
  
// Driver Code 
public static void Main(String[] args)  
{ 
    /* following array doesn't have  
    any cycles and hence all keys  
    will be inserted without any rehashing */
    int []keys_1 = {20, 50, 53, 75, 100,  
                    67, 105, 3, 36, 39}; 
  
    int n = keys_1.Length; 
  
    cuckoo(keys_1, n); 
  
    /* following array has a cycle and  
    hence we will have to rehash to  
    position every key */
    int []keys_2 = {20, 50, 53, 75, 100,  
                    67, 105, 3, 36, 39, 6}; 
  
    int m = keys_2.Length; 
  
    cuckoo(keys_2, m); 
} 
} 
  
// This code is contributed by PrinciRaj1992

خروجی قطعه کدهای بالا به صورت زیر است.

Final hash tables:
- 100 - 36 - - 50 - - 75 - 
3 20 - 39 53 - 67 - - 105 - 

105 unpositioned
Cycle present. REHASH.
Final hash tables:
- 67 - 3 - - 39 - - 53 - 
6 20 - 36 50 - 75 - - 100 -

تعمیم درهم سازی کوکو که در آن از بیش از ۲ تابع درهم‌سازی جایگزین استفاده شده است برای به کارگیری بخش بزرگ‌تری از جدول درهم‌سازی به صورت موثر استفاده می‌شود.

البته در این حالت، سرعت جستجو و درج، قربانی می‌شوند. برای مثال، اگر از سه تابع هش استفاده شود، امن است که ۹۱٪ بارگذاری شود و همچنان در مرزهای مورد نظر کار کند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۱ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *