درهم سازی فاخته — به زبان ساده
در این مطلب، «درهم سازی فاخته» (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}
تابع هش:
1h1(key) = key%11
2h2(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
1// C++ program to demonstrate working of Cuckoo
2// hashing.
3#include<bits/stdc++.h>
4
5// upper bound on number of elements in our set
6#define MAXN 11
7
8// choices for position
9#define ver 2
10
11// Auxiliary space bounded by a small multiple
12// of MAXN, minimizing wastage
13int hashtable[ver][MAXN];
14
15// Array to store possible positions for a key
16int pos[ver];
17
18/* function to fill hash table with dummy value
19 * dummy value: INT_MIN
20 * number of hashtables: ver */
21void initTable()
22{
23 for (int j=0; j<MAXN; j++)
24 for (int i=0; i<ver; i++)
25 hashtable[i][j] = INT_MIN;
26}
27
28/* return hashed value for a key
29 * function: ID of hash function according to which
30 key has to hashed
31 * key: item to be hashed */
32int hash(int function, int key)
33{
34 switch (function)
35 {
36 case 1: return key%MAXN;
37 case 2: return (key/MAXN)%MAXN;
38 }
39}
40
41/* function to place a key in one of its possible positions
42 * tableID: table in which key has to be placed, also equal
43 to function according to which key must be hashed
44 * cnt: number of times function has already been called
45 in order to place the first input key
46 * n: maximum number of times function can be recursively
47 called before stopping and declaring presence of cycle */
48void place(int key, int tableID, int cnt, int n)
49{
50 /* if function has been recursively called max number
51 of times, stop and declare cycle. Rehash. */
52 if (cnt==n)
53 {
54 printf("%d unpositioned\n", key);
55 printf("Cycle present. REHASH.\n");
56 return;
57 }
58
59 /* calculate and store possible positions for the key.
60 * check if key already present at any of the positions.
61 If YES, return. */
62 for (int i=0; i<ver; i++)
63 {
64 pos[i] = hash(i+1, key);
65 if (hashtable[i][pos[i]] == key)
66 return;
67 }
68
69 /* check if another key is already present at the
70 position for the new key in the table
71 * If YES: place the new key in its position
72 * and place the older key in an alternate position
73 for it in the next table */
74 if (hashtable[tableID][pos[tableID]]!=INT_MIN)
75 {
76 int dis = hashtable[tableID][pos[tableID]];
77 hashtable[tableID][pos[tableID]] = key;
78 place(dis, (tableID+1)%ver, cnt+1, n);
79 }
80 else //else: place the new key in its position
81 hashtable[tableID][pos[tableID]] = key;
82}
83
84/* function to print hash table contents */
85void printTable()
86{
87 printf("Final hash tables:\n");
88
89 for (int i=0; i<ver; i++, printf("\n"))
90 for (int j=0; j<MAXN; j++)
91 (hashtable[i][j]==INT_MIN)? printf("- "):
92 printf("%d ", hashtable[i][j]);
93
94 printf("\n");
95}
96
97/* function for Cuckoo-hashing keys
98 * keys[]: input array of keys
99 * n: size of input array */
100void cuckoo(int keys[], int n)
101{
102 // initialize hash tables to a dummy value (INT-MIN)
103 // indicating empty position
104 initTable();
105
106 // start with placing every key at its position in
107 // the first hash table according to first hash
108 // function
109 for (int i=0, cnt=0; i<n; i++, cnt=0)
110 place(keys[i], 0, cnt, n);
111
112 //print the final hash tables
113 printTable();
114}
115
116/* driver function */
117int main()
118{
119 /* following array doesn't have any cycles and
120 hence all keys will be inserted without any
121 rehashing */
122 int keys_1[] = {20, 50, 53, 75, 100, 67, 105,
123 3, 36, 39};
124
125 int n = sizeof(keys_1)/sizeof(int);
126
127 cuckoo(keys_1, n);
128
129 /* following array has a cycle and hence we will
130 have to rehash to position every key */
131 int keys_2[] = {20, 50, 53, 75, 100, 67, 105,
132 3, 36, 39, 6};
133
134 int m = sizeof(keys_2)/sizeof(int);
135
136 cuckoo(keys_2, m);
137
138 return 0;
139}
درهم سازی کوکو (فاخته) در جاوا
1// Java program to demonstrate working of
2// Cuckoo hashing.
3import java.util.*;
4
5class GFG
6{
7
8// upper bound on number of elements in our set
9static int MAXN = 11;
10
11// choices for position
12static int ver = 2;
13
14// Auxiliary space bounded by a small multiple
15// of MAXN, minimizing wastage
16static int [][]hashtable = new int[ver][MAXN];
17
18// Array to store possible positions for a key
19static int []pos = new int[ver];
20
21/* function to fill hash table with dummy value
22* dummy value: INT_MIN
23* number of hashtables: ver */
24static void initTable()
25{
26 for (int j = 0; j < MAXN; j++)
27 for (int i = 0; i < ver; i++)
28 hashtable[i][j] = Integer.MIN_VALUE;
29}
30
31/* return hashed value for a key
32* function: ID of hash function according to which
33 key has to hashed
34* key: item to be hashed */
35static int hash(int function, int key)
36{
37 switch (function)
38 {
39 case 1: return key % MAXN;
40 case 2: return (key / MAXN) % MAXN;
41 }
42 return Integer.MIN_VALUE;
43}
44
45/* function to place a key in one of its possible positions
46* tableID: table in which key has to be placed, also equal
47 to function according to which key must be hashed
48* cnt: number of times function has already been called
49 in order to place the first input key
50* n: maximum number of times function can be recursively
51 called before stopping and declaring presence of cycle */
52static void place(int key, int tableID, int cnt, int n)
53{
54 /* if function has been recursively called max number
55 of times, stop and declare cycle. Rehash. */
56 if (cnt == n)
57 {
58 System.out.printf("%d unpositioned\n", key);
59 System.out.printf("Cycle present. REHASH.\n");
60 return;
61 }
62
63 /* calculate and store possible positions for the key.
64 * check if key already present at any of the positions.
65 If YES, return. */
66 for (int i = 0; i < ver; i++)
67 {
68 pos[i] = hash(i + 1, key);
69 if (hashtable[i][pos[i]] == key)
70 return;
71 }
72
73 /* check if another key is already present at the
74 position for the new key in the table
75 * If YES: place the new key in its position
76 * and place the older key in an alternate position
77 for it in the next table */
78 if (hashtable[tableID][pos[tableID]] != Integer.MIN_VALUE)
79 {
80 int dis = hashtable[tableID][pos[tableID]];
81 hashtable[tableID][pos[tableID]] = key;
82 place(dis, (tableID + 1) % ver, cnt + 1, n);
83 }
84 else // else: place the new key in its position
85 hashtable[tableID][pos[tableID]] = key;
86}
87
88/* function to print hash table contents */
89static void printTable()
90{
91 System.out.printf("Final hash tables:\n");
92
93 for (int i = 0; i < ver; i++, System.out.printf("\n"))
94 for (int j = 0; j < MAXN; j++)
95 if(hashtable[i][j] == Integer.MIN_VALUE)
96 System.out.printf("- ");
97 else
98 System.out.printf("%d ", hashtable[i][j]);
99
100 System.out.printf("\n");
101}
102
103/* function for Cuckoo-hashing keys
104* keys[]: input array of keys
105* n: size of input array */
106static void cuckoo(int keys[], int n)
107{
108 // initialize hash tables to a dummy value
109 // (INT-MIN) indicating empty position
110 initTable();
111
112 // start with placing every key at its position in
113 // the first hash table according to first hash
114 // function
115 for (int i = 0, cnt = 0; i < n; i++, cnt = 0)
116 place(keys[i], 0, cnt, n);
117
118 // print the final hash tables
119 printTable();
120}
121
122// Driver Code
123public static void main(String[] args)
124{
125 /* following array doesn't have any cycles and
126 hence all keys will be inserted without any
127 rehashing */
128 int keys_1[] = {20, 50, 53, 75, 100,
129 67, 105, 3, 36, 39};
130
131 int n = keys_1.length;
132
133 cuckoo(keys_1, n);
134
135 /* following array has a cycle and hence we will
136 have to rehash to position every key */
137 int keys_2[] = {20, 50, 53, 75, 100,
138 67, 105, 3, 36, 39, 6};
139
140 int m = keys_2.length;
141
142 cuckoo(keys_2, m);
143}
144}
145
146// This code is contributed by Princi Singh
درهم سازی فاخته در #C
1// C# program to demonstrate working of
2// Cuckoo hashing.
3using System;
4
5class GFG
6{
7
8// upper bound on number of
9// elements in our set
10static int MAXN = 11;
11
12// choices for position
13static int ver = 2;
14
15// Auxiliary space bounded by a small
16// multiple of MAXN, minimizing wastage
17static int [,]hashtable = new int[ver, MAXN];
18
19// Array to store
20// possible positions for a key
21static int []pos = new int[ver];
22
23/* function to fill hash table
24with dummy value
25* dummy value: INT_MIN
26* number of hashtables: ver */
27static void initTable()
28{
29 for (int j = 0; j < MAXN; j++)
30 for (int i = 0; i < ver; i++)
31 hashtable[i, j] = int.MinValue;
32}
33
34/* return hashed value for a key
35* function: ID of hash function
36according to which key has to hashed
37* key: item to be hashed */
38static int hash(int function, int key)
39{
40 switch (function)
41 {
42 case 1: return key % MAXN;
43 case 2: return (key / MAXN) % MAXN;
44 }
45 return int.MinValue;
46}
47
48/* function to place a key in one of
49its possible positions
50* tableID: table in which key
51has to be placed, also equal to function
52according to which key must be hashed
53* cnt: number of times function has already
54been called in order to place the first input key
55* n: maximum number of times function
56can be recursively called before stopping and
57declaring presence of cycle */
58static void place(int key, int tableID,
59 int cnt, int n)
60{
61 /* if function has been recursively
62 called max number of times,
63 stop and declare cycle. Rehash. */
64 if (cnt == n)
65 {
66 Console.Write("{0} unpositioned\n", key);
67 Console.Write("Cycle present. REHASH.\n");
68 return;
69 }
70
71 /* calculate and store possible positions
72 * for the key. Check if key already present
73 at any of the positions. If YES, return. */
74 for (int i = 0; i < ver; i++)
75 {
76 pos[i] = hash(i + 1, key);
77 if (hashtable[i, pos[i]] == key)
78 return;
79 }
80
81 /* check if another key is already present
82 at the position for the new key in the table
83 * If YES: place the new key in its position
84 * and place the older key in an alternate position
85 for it in the next table */
86 if (hashtable[tableID,
87 pos[tableID]] != int.MinValue)
88 {
89 int dis = hashtable[tableID, pos[tableID]];
90 hashtable[tableID, pos[tableID]] = key;
91 place(dis, (tableID + 1) % ver, cnt + 1, n);
92 }
93 else // else: place the new key in its position
94 hashtable[tableID, pos[tableID]] = key;
95}
96
97/* function to print hash table contents */
98static void printTable()
99{
100 Console.Write("Final hash tables:\n");
101
102 for (int i = 0; i < ver;
103 i++, Console.Write("\n"))
104 for (int j = 0; j < MAXN; j++)
105 if(hashtable[i, j] == int.MinValue)
106 Console.Write("- ");
107 else
108 Console.Write("{0} ",
109 hashtable[i, j]);
110
111 Console.Write("\n");
112}
113
114/* function for Cuckoo-hashing keys
115* keys[]: input array of keys
116* n: size of input array */
117static void cuckoo(int []keys, int n)
118{
119 // initialize hash tables to a
120 // dummy value (INT-MIN)
121 // indicating empty position
122 initTable();
123
124 // start with placing every key
125 // at its position in the first
126 // hash table according to first
127 // hash function
128 for (int i = 0, cnt = 0;
129 i < n; i++, cnt = 0)
130 place(keys[i], 0, cnt, n);
131
132 // print the final hash tables
133 printTable();
134}
135
136// Driver Code
137public static void Main(String[] args)
138{
139 /* following array doesn't have
140 any cycles and hence all keys
141 will be inserted without any rehashing */
142 int []keys_1 = {20, 50, 53, 75, 100,
143 67, 105, 3, 36, 39};
144
145 int n = keys_1.Length;
146
147 cuckoo(keys_1, n);
148
149 /* following array has a cycle and
150 hence we will have to rehash to
151 position every key */
152 int []keys_2 = {20, 50, 53, 75, 100,
153 67, 105, 3, 36, 39, 6};
154
155 int m = keys_2.Length;
156
157 cuckoo(keys_2, m);
158}
159}
160
161// 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 -
تعمیم درهم سازی کوکو که در آن از بیش از ۲ تابع درهمسازی جایگزین استفاده شده است برای به کارگیری بخش بزرگتری از جدول درهمسازی به صورت موثر استفاده میشود.
البته در این حالت، سرعت جستجو و درج، قربانی میشوند. برای مثال، اگر از سه تابع هش استفاده شود، امن است که ۹۱٪ بارگذاری شود و همچنان در مرزهای مورد نظر کار کند.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- برنامه تشخیص وجود دور در گراف جهتدار — راهنمای کاربردی
- برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی
- یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
- الگوریتم بازی مار و پله همراه با کد — به زبان ساده
^^