當Guava項目發布版本11.0時，新添加的功能之一是BloomFilter類。 BloomFilter是唯一的數據結構，用于指示元素是否包含在集合中。 使BloomFilter有趣的是，它將指示元素是否絕對不包含或可能包含在集合中。

永遠不會出現假陰性的特性使BloomFilter成為用作保護條件的絕佳候選者，以幫助防止執行不必要和昂貴的操作。 雖然BloomFilters最近獲得了很好的曝光，但使用它意味著滾動自己的瀏覽器或通過Google搜索代碼。 滾動自己的BloomFilter的麻煩在于獲取正確的哈希函數來制作過濾器
有效。 考慮到Guava使用Murmur Hash來實現，我們現在有一個有效的BloomFilter有用，而只是一個圖書館而已。

BloomFilter速成課程

BloomFilters本質上是位向量。 在較高級別，BloomFilters以下列方式工作：

1. 將元素添加到過濾器。
2. 將其哈希幾次，然后將索引與哈希結果匹配的位設置為1。

測試元素是否在集合中時，請遵循相同的哈希過程，并檢查這些位是否設置為1或0。此過程是BloomFilter如何保證元素不存在的方法。 如果未設置位，則根本不可能將元素包含在集合中。 但是，肯定答案表示元素在集合中或發生哈希沖突。 可以在此處找到BloomFilter的更詳細描述，并在此處找到有關BloomFilters的良好教程。 根據Wikipedia的說法，Google在BigTable中使用BloomFilters來避免對不存在的項目進行磁盤查找。 另一個有趣的用法是使用BloomFilter來優化sql Querry 。

使用番石榴BloomFilter

通過調用BloomFilter類上的static方法create來創建Guava BloomFilter，
傳遞一個Funnel對象和一個int表示預期的插入次數。 漏斗也是Guava 11中的新功能，它是一個可以將數據發送到Sink的對象。 下面的示例是默認實現，其誤報百分比為3％。 Guava提供了一個Funnels類，其中包含兩個靜態方法，這些方法提供Funnel接口的實現，用于將CharSequence或字節數組插入到過濾器中。

//Creating the BloomFilter
BloomFilter bloomFilter = BloomFilter.create(Funnels.byteArrayFunnel(), 1000);//Putting elements into the filter
//A BigInteger representing a key of some sort
bloomFilter.put(bigInteger.toByteArray());//Testing for element in set
boolean mayBeContained = bloomFilter.mayContain(bitIntegerII.toByteArray());

更新：基于路易斯·沃瑟曼的評論，以下是如何使用自定義Funnel實現為BigIntegers創建BloomFilter的方法：

//Create the custom filter
class BigIntegerFunnel implements Funnel<BigInteger> {@Overridepublic void funnel(BigInteger from, Sink into) {into.putBytes(from.toByteArray());}}//Creating the BloomFilter
BloomFilter bloomFilter = BloomFilter.create(new BigIntegerFunnel(), 1000);//Putting elements into the filter
//A BigInteger representing a key of some sort
bloomFilter.put(bigInteger);//Testing for element in set
boolean mayBeContained = bloomFilter.mayContain(bitIntegerII);

注意事項

正確估計預期插入的數量至關重要。 當插入過濾器的次數接近或超過預期的數目時，BloomFilter開始填滿，結果將產生更多的誤報，直至無用之地。 還有另一個版本的BloomFilter.create方法，該方法帶有一個附加參數，雙精度表示所需的錯誤命中概率級別（必須大于0且小于1）。 錯誤命中概率的級別會影響用于存儲或搜索元素的哈希數。 所需的百分比越低，執行的哈希數越高。

結論

BloomFilter是開發人員可以在其工具箱中使用的有用項。 現在，Guava項目使在需要時開始使用BloomFilter變得非常簡單。 希望您喜歡這篇文章。 歡迎提出有用的意見和建議。

參考文獻

• Guava BloomFilter的單元測試演示 。
• BloomFilter類
• 您想了解的所有關于BloomFilters的信息 。
• BloomFilter教程 。
• Wikipedia上的BloomFilter 。

參考：來自我們的JCG合作伙伴 Bill Bejeck的Google Guava BloomFIlter，來自“ 隨機思考編碼”博客。

翻譯自: https://www.javacodegeeks.com/2012/12/google-guava-bloomfilter.html