背景： 有三个基本操作必须由 哈希表 （或字典）：
null
- 查找（键）： 回来 符合事实的 如果桌子上有钥匙，还有吗 错误的
- 插入（键）： 如果尚未存在项“key”，则将其添加到表中
- 删除（键）： 从表中删除“键”
即使我们有一张大桌子来存放钥匙，也很可能发生碰撞。使用 生日悖论 ：由于只有23人，两个人共享同一出生日期的概率为50%！有三种解决哈希冲突的一般策略：
尽管上述解决方案提供了O（1）的预期查找成本，但在简单链接中，开放寻址（使用线性探测）中查找的预期最坏情况成本是Ω（logn）和Θ（logn/logn）（来源： 斯坦福德讲稿 ).为了缩小预期时间和最坏情况预期时间之间的差距，使用了两种方法：
- 多项选择哈希 ：为每个元素在哈希表中的位置提供多个选择
- 重新定位哈希 ：允许哈希表中的元素在放置后移动
布谷鸟哈希： 布谷鸟哈希将多项选择和重新定位的思想结合在一起，保证了0（1）个最坏情况下的查找时间！
- 多项选择： 我们给你一把钥匙 两个选择 这个 h1（键）和h2（键）用于驻留。
- 重新安置 ：h1（键）和h2（键）可能被占用。这可以通过模仿布谷鸟来解决： 孵化时，它会将其他卵或幼崽推出巢外 类似地，将新密钥插入布谷鸟哈希表可能会将旧密钥推送到不同的位置。这就给我们留下了重新放置旧密钥的问题。
- 如果旧钥匙的备用位置为空，则没有问题。
- 否则，旧密钥将替换另一个密钥。这会一直持续到程序找到一个空缺职位或进入一个周期。在循环的情况下，将选择新的哈希函数，并对整个数据结构进行“重新哈希”。布谷鸟成功之前可能需要多次复生。
插入 即使考虑到重新灰化的可能性，只要密钥数保持在哈希表容量的一半以下，即负载因子低于50%，也很可能会出现O（1）（摊销）。
删除 是O（1）最坏情况，因为它只需要检查哈希表中的两个位置。 插图
输入：
{20, 50, 53, 75, 100, 67, 105, 3, 36, 39}
散列函数：
h1(key) = key%11h2(key) = (key/11)%11
让我们从插入 20 在h1（20）确定的第一个表中的可能位置：
下一步： 50
下一步： 53 .h1（53）=9。但9点20分已经到了。我们将表1中的53和表2中的20放在h2（20）处
下一步： 75 .h1（75）=9。但是53已经在9点了。我们将表1中的75和表2中的53放在h2（53）处
下一步： 100 .h1（100）=1。
下一步： 67 .h1（67）=1。但100已经在1点了。我们在表1中放置67，在表2中放置100
下一步： 105 .h1（105）=6。但6点50分已经到了。我们在h2（50）=4时，将105置于表1中，将50置于表2中。现在有53人流离失所。h1（53）=9。75位移：h2（75）=6。
下一步： 3. .h1（3）=3。
下一步： 36 .h1（36）=3。h2（3）=0。
下一步： 39 .h1（39）=6。h2（105）=9。h1（100）=1。h2（67）=6。h1（75）=9。h2（53）=4。h1（50）=6。h2（39）=3。 在这里，新键39在稍后对place 105的递归调用中被替换，它替换了place 105。
实施： 下面是布谷鸟哈希的实现
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" , key); printf ( "Cycle present. REHASH." ); 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:" ); for ( int i=0; i<ver; i++, printf ( "" )) for ( int j=0; j<MAXN; j++) (hashtable[i][j]==INT_MIN)? printf ( "- " ): printf ( "%d " , hashtable[i][j]); printf ( "" ); } /* 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
// 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" , key); System.out.printf( "Cycle present. REHASH." ); 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:" ); for ( int i = 0 ; i < ver; i++, System.out.printf( "" )) 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( "" ); } /* 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" , key); Console.Write( "Cycle present. REHASH." ); 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:" ); for ( int i = 0; i < ver; i++, Console.Write( "" )) for ( int j = 0; j < MAXN; j++) if (hashtable[i, j] == int .MinValue) Console.Write( "- " ); else Console.Write( "{0} " , hashtable[i, j]); Console.Write( "" ); } /* 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 |
Javascript
<script> // Javascript program to demonstrate working of // Cuckoo hashing. // upper bound on number of elements in our set let MAXN = 11; // choices for position let ver = 2; // Auxiliary space bounded by a small multiple // of MAXN, minimizing wastage let hashtable = new Array(ver); for ( var i = 0; i < hashtable.length; i++) { hashtable[i] = new Array(2); } // Array to store possible positions for a key let pos = Array(ver).fill(0); /* function to fill hash table with dummy value * dummy value: let_MIN * number of hashtables: ver */ function initTable() { for (let j = 0; j < MAXN; j++) for (let i = 0; i < ver; i++) hashtable[i][j] = Number.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 */ function hash( function , key) { switch ( function ) { case 1: return key % MAXN; case 2: return (Math.floor(key / MAXN)) % MAXN; } return Number.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 */ function place(key, tableID, cnt, n) { /* if function has been recursively called max number of times, stop and declare cycle. Rehash. */ if (cnt == n) { document.write(key + " unpositioned" + "<br/>" ); document.write( "Cycle present. REHASH." + "<br/>" ); return ; } /* calculate and store possible positions for the key. * check if key already present at any of the positions. If YES, return. */ for (let 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]] != Number.MIN_VALUE) { let 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 */ function printTable() { document.write( "Final hash tables:" + "<br/>" ); for (let i = 0; i < ver; i++, document.write( "<br/>" )) for (let j = 0; j < MAXN; j++) if (hashtable[i][j] == Number.MIN_VALUE) document.write( "- " ); else document.write(hashtable[i][j] + " " ); document.write( "<br/>" ); } /* function for Cuckoo-hashing keys * keys[]: input array of keys * n: size of input array */ function cuckoo(keys, n) { // initialize hash tables to a dummy value // (let-MIN) indicating empty position initTable(); // start with placing every key at its position in // the first hash table according to first hash // function for (let i = 0, cnt = 0; i < n; i++, cnt = 0) place(keys[i], 0, cnt, n); // print the final hash tables printTable(); } // Driver program /* following array doesn't have any cycles and hence all keys will be inserted without any rehashing */ let keys_1 = [20, 50, 53, 75, 100, 67, 105, 3, 36, 39]; let n = keys_1.length; cuckoo(keys_1, n); /* following array has a cycle and hence we will have to rehash to position every key */ let keys_2 = [20, 50, 53, 75, 100, 67, 105, 3, 36, 39, 6]; let m = keys_2.length; cuckoo(keys_2, m); </script> |
输出：
Final hash tables:- 100 - 36 - - 50 - - 75 - 3 20 - 39 53 - 67 - - 105 - 105 unpositionedCycle present. REHASH.Final hash tables:- 67 - 3 - - 39 - - 53 - 6 20 - 36 50 - 75 - - 100 -
使用两个以上可选哈希函数的布谷鸟哈希法的推广可以有效地利用哈希表的大部分容量，同时牺牲一些查找和插入速度。示例：如果我们使用3个哈希函数，则可以安全地加载91%，并且仍在预期范围内运行。
本文由 亚什·瓦里亚尼。 如果你喜欢GeekSforgeks，并且想贡献自己的力量，你也可以写一篇文章，然后把你的文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
