布穀鳥哈希最早於2001 年由Rasmus Pagh 和Flemming Friche Rodler 提出。該哈希方法是為了解決哈希衝突的問題而提出，利用較少計算換取了較大空間。名稱源於該哈希方法行為類似於布穀鳥在別的鳥巢中下蛋，並將別的鳥蛋擠出的行為。它具有占用空間小、查詢迅速等特性，可用於Bloom filter 和記憶體管理。
基本介紹
- 中文名：Cuckoo hash
- 提出時間：2001 年
- 提出者：Rasmus Pagh
- 用途：解決哈希衝突的問題
算法描述,圖例,其他,
算法描述
算法使用兩個不同哈希函式計算對應key 的位置。
1. 當兩個哈希任意位置為空，則選擇一個位置插入
2. 當兩個哈希有位置為空時，則插入到空位置
3. 當兩個哈希位置均不為空時，隨機選擇兩者之一的位置上key 踢出，計算踢出的key 另一個哈希值對應的位置進行插入，轉至2執行（即當再次插入位置為空時插入，仍舊不為空時，再踢出這個key）
圖例
1. 插入key1 兩個位置均為空,則插入任意位置.
2. 插入後
3. 插入key2 兩個位置有一個位置為空,則插入空的位置中
4. 插入後效果
5. 新插入keyi 發現對應兩個位置均被占據
6. 隨機選擇一個位置提出所在位置的key（key1），將踢出的key 放置在另一個哈希結果對應的位置上
7. 如果踢出的key（key1）又占據/踢出了其他key（keyj）的位置，則反覆執行上面的過程直到結束
其他
1. Cuckoo hash 有兩種變形。一種通過增加哈希函式進一步提高空間利用率；另一種是增加哈希表，每個哈希函式對應一個哈希表，每次選擇多個張表中空餘位置進行放置。三個哈希表可以達到80% 的空間利用率。
2. Cuckoo hash 的過程可能因為反覆踢出無限循環下去，這時候就需要進行一次循環踢出的限制，超過限制則認為需要添加新的哈希函式。
3. 在SOSP 11 的SLIT 文章中有使用Cuckoo hash。
增加哈希表過程如下：
當新插入一個key hashA 在上面哈希表位置和hashB 在下面哈希表的位置分別被key1 和keyx 占據，任選一個key 提出（這裡選擇key1）。
計算key1 hashB 的值然後插入到下面的hashB 對應的哈希表中。
