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

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

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

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