來源：www.cnblogs.com/Courage129/p/14337466.html
大家都知道,在計算機中,IO一直是一個瓶頸,很多框架以及技術甚至硬體都是為了降低IO操作而生,今天聊一聊過濾器,先說一個場景:
我們業務后端涉及資料庫,當請求訊息查詢某些資訊時,可能先檢查快取中是否有相關資訊,有的話回傳,如果沒有的話可能就要去資料庫里面查詢,這時候有一個問題,如果很多請求是在請求資料庫根本不存在的資料,那么資料庫就要頻繁回應這種不必要的IO查詢,如果再多一些,資料庫大多數IO都在回應這種毫無意義的請求操作,那么如何將這些請求阻擋在外呢?過濾器由此誕生:
布隆過濾器
布隆過濾器(Bloom Filter)大概的思路就是,當你請求的資訊來的時候,先檢查一下你查詢的資料我這有沒有,有的話將請求壓給資料庫,沒有的話直接回傳,是如何做到的呢?
如圖,一個bitmap用于記錄,bitmap原始數值全都是0,當一個資料存進來的時候,用三個Hash函式分別計算三次Hash值,并且將bitmap對應的位置設定為1,上圖中,bitmap 的1,3,6位置被標記為1,這時候如果一個資料請求過來,依然用之前的三個Hash函式計算Hash值,如果是同一個資料的話,勢必依舊是映射到1,3,6位,那么就可以判斷這個資料之前存盤過,如果新的資料映射的三個位置,有一個匹配不上,假如映射到1,3,7位,由于7位是0,也就是這個資料之前并沒有加入進資料庫,所以直接回傳，
布隆過濾器的問題
上面這種方式,應該你已經發現了,布隆過濾器存在一些問題:
第一方面,布隆過濾器可能誤判:
假如有這么一個情景,放入資料包1時,將bitmap的1,3,6位設定為了1,放入資料包2時將bitmap的3,6,7位設定為了1,此時一個并沒有存過的資料包請求3,做三次哈希之后,對應的bitmap位點分別是1,6,7,這個資料之前并沒有存進去過,但是由于資料包1和2存入時將對應的點設定為了1,所以請求3也會壓倒資料庫上,這種情況,會隨著存入的資料增加而增加，
第二方面,布隆過濾器沒法洗掉資料,洗掉資料存在以下兩種困境:
一是,由于有誤判的可能,并不確定資料是否存在資料庫里,例如資料包3，
二是,當你洗掉某一個資料包對應位圖上的標志后,可能影響其他的資料包,例如上面例子中,如果洗掉資料包1,也就意味著會將bitmap1,3,6位設定為0,此時資料包2來請求時,會顯示不存在,因為3,6兩位已經被設定為0，
布隆過濾器增強版
為了解決上面布隆過濾器的問題,出現了一個增強版的布隆過濾器(Counting Bloom Filter),這個過濾器的思路是將布隆過濾器的bitmap更換成陣列,當陣列某位置被映射一次時就+1,當洗掉時就-1,這樣就避免了普通布隆過濾器洗掉資料后需要重新計算其余資料包Hash的問題,但是依舊沒法避免誤判，
布谷鳥過濾器
為了解決布隆過濾器不能洗掉元素的問題, 論文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鳥過濾器，相比布谷鳥過濾器，布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支持反向操作（洗掉）以及不支持計數，
查詢性能弱是因為布隆過濾器需要使用多個 hash 函式探測位圖中多個不同的位點，這些位點在記憶體上跨度很大，會導致 CPU 快取行命中率低，
空間效率低是因為在相同的誤判率下，布谷鳥過濾器的空間利用率要明顯高于布隆，空間上大概能節省 40% 多，不過布隆過濾器并沒有要求位圖的長度必須是 2 的指數，而布谷鳥過濾器必須有這個要求，從這一點出發，似乎布隆過濾器的空間伸縮性更強一些，
不支持反向洗掉操作這個問題著實是擊中了布隆過濾器的軟肋，在一個動態的系統里面元素總是不斷的來也是不斷的走，布隆過濾器就好比是印跡，來過來就會有痕跡，就算走了也無法清理干凈，比如你的系統里本來只留下 1kw 個元素，但是整體上來過了上億的流水元素，布隆過濾器很無奈，它會將這些流失的元素的印跡也會永遠存放在那里，隨著時間的流失，這個過濾器會越來越擁擠，直到有一天你發現它的誤判率太高了，不得不進行重建，
布谷鳥過濾器在論文里聲稱自己解決了這個問題，它可以有效支持反向洗掉操作，而且將它作為一個重要的賣點，傭訓你們放棄布隆過濾器改用布谷鳥過濾器，
為啥要取名布谷鳥呢?
有個成語，「鳩占鵲巢」,布谷鳥也是,布谷鳥從來不自己筑巢，它將自己的蛋產在別人的巢里，讓別人來幫忙范訓，待小布谷鳥破殼而出之后，因為布谷鳥的體型相對較大，它又將養母的其它孩子（還是蛋）從巢里擠走 —— 從高空摔下夭折了，
布谷鳥哈希
最簡單的布谷鳥哈希結構是一維陣列結構，會有兩個 hash 演算法將新來的元素映射到陣列的兩個位置，如果兩個位置中有一個位置為空，那么就可以將元素直接放進去，但是如果這兩個位置都滿了，它就不得不「鳩占鵲巢」，隨機踢走一個，然后自己霸占了這個位置，
p1 = hash1(x) % l
p2 = hash2(x) % l
復制代碼
不同于布谷鳥的是，布谷鳥哈希演算法會幫這些受害者（被擠走的蛋）尋找其它的窩，因為每一個元素都可以放在兩個位置，只要任意一個有空位置，就可以塞進去，所以這個傷心的被擠走的蛋會看看自己的另一個位置有沒有空，如果空了，自己挪過去也就皆大歡喜了，但是如果這個位置也被別人占了呢？好，那么它會再來一次「鳩占鵲巢」，將受害者的角色轉嫁給別人，然后這個新的受害者還會重復這個程序直到所有的蛋都找到了自己的巢為止，
布谷鳥哈希的問題
但是會遇到一個問題，那就是如果陣列太擁擠了，連續踢來踢去幾百次還沒有停下來，這時候會嚴重影響插入效率，這時候布谷鳥哈希會設定一個閾值，當連續占巢行為超出了某個閾值，就認為這個陣列已經幾乎滿了，這時候就需要對它進行擴容，重新放置所有元素，
還會有另一個問題，那就是可能會存在擠兌回圈，比如兩個不同的元素，hash 之后的兩個位置正好相同，這時候它們一人一個位置沒有問題，但是這時候來了第三個元素，它 hash 之后的位置也和它們一樣，很明顯，這時候會出現擠兌的回圈，不過讓三個不同的元素經過兩次 hash 后位置還一樣，這樣的概率并不是很高，除非你的 hash 演算法太挫了，
布谷鳥哈希演算法對待這種擠兌回圈的態度就是認為陣列太擁擠了，需要擴容（實際上并不是這樣），
優化
上面的布谷鳥哈希演算法的平均空間利用率并不高，大概只有 50%，到了這個百分比，就會很快出現連續擠兌次數超出閾值，這樣的哈希演算法價值并不明顯，所以需要對它進行改良，
改良的方案之一是增加 hash 函式，讓每個元素不止有兩個巢，而是三個巢、四個巢，這樣可以大大降低碰撞的概率，將空間利用率提高到 95%左右，
另一個改良方案是在陣列的每個位置上掛上多個座位，這樣即使兩個元素被 hash 在了同一個位置，也不必立即「鳩占鵲巢」，因為這里有多個座位，你可以隨意坐一個，除非這多個座位都被占了，才需要進行擠兌，很明顯這也會顯著降低擠兌次數，這種方案的空間利用率只有 85%左右，但是查詢效率會很高，同一個位置上的多個座位在記憶體空間上是連續的，可以有效利用 CPU 高速快取，
所以更加高效的方案是將上面的兩個改良方案融合起來，比如使用 4 個 hash 函式，每個位置上放 2 個座位，這樣既可以得到時間效率，又可以得到空間效率，這樣的組合甚至可以將空間利用率提到高 99%，這是非常了不起的空間效率，
布谷鳥過濾器
布谷鳥過濾器和布谷鳥哈希結構一樣，它也是一維陣列，但是不同于布谷鳥哈希的是，布谷鳥哈希會存盤整個元素，而布谷鳥過濾器中只會存盤元素的指紋資訊（幾個bit，類似于布隆過濾器），這里過濾器犧牲了資料的精確性換取了空間效率，正是因為存盤的是元素的指紋資訊，所以會存在誤判率，這點和布隆過濾器如出一轍，
首先布谷鳥過濾器還是只會選用兩個 hash 函式，但是每個位置可以放置多個座位，這兩個 hash 函式選擇的比較特殊，因為過濾器中只能存盤指紋資訊，當這個位置上的指紋被擠兌之后，它需要計算出另一個對偶位置，而計算這個對偶位置是需要元素本身的，我們來回憶一下前面的哈希位置計算公式，
fp = fingerprint(x)
p1 = hash1(x) % l
p2 = hash2(x) % l
我們知道了 p1 和 x 的指紋，是沒辦法直接計算出 p2 的，
特殊的 hash 函式
布谷鳥過濾器巧妙的地方就在于設計了一個獨特的 hash 函式，使得可以根據 p1 和 元素指紋 直接計算出 p2，而不需要完整的 x 元素，
fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp) // 異或
從上面的公式中可以看出，當我們知道 fp 和 p1，就可以直接算出 p2，同樣如果我們知道 p2 和 fp，也可以直接算出 p1 —— 對偶性，
p1 = p2 ^ hash(fp)
所以我們根本不需要知道當前的位置是 p1 還是 p2，只需要將當前的位置和 hash(fp) 進行異或計算就可以得到對偶位置，而且只需要確保 hash(fp) != 0 就可以確保 p1 != p2，如此就不會出現自己踢自己導致死回圈的問題，
也許你會問為什么這里的 hash 函式不需要對陣列的長度取模呢？實際上是需要的，但是布谷鳥過濾器強制陣列的長度必須是 2 的指數，所以對陣列的長度取模等價于取 hash 值的最后 n 位，在進行異或運算時，忽略掉低 n 位 之外的其它位就行，將計算出來的位置 p 保留低 n 位就是最終的對偶位置，
近期熱文推薦：
1.1,000+ 道 Java面試題及答案整理(2022最新版)
2.勁爆！Java 協程要來了，，，
3.Spring Boot 2.x 教程，太全了！
4.別再寫滿屏的爆爆爆炸類了，試試裝飾器模式，這才是優雅的方式！！
5.《Java開發手冊（嵩山版）》最新發布，速速下載！
覺得不錯，別忘了隨手點贊+轉發哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/497793.html
標籤：其他