谷歌guava

當(dāng)Guava項(xiàng)目發(fā)布版本11.0時(shí)，新添加的功能之一是BloomFilter類。 BloomFilter是唯一的數(shù)據(jù)結(jié)構(gòu)，用于指示元素是否包含在集合中。 使BloomFilter有趣的是，它將指示元素是否絕對(duì)不包含或可能包含在集合中。

永遠(yuǎn)不會(huì)出現(xiàn)假陰性的特性使BloomFilter成為用作警戒條件的絕佳候選者，以幫助防止執(zhí)行不必要和昂貴的操作。 雖然BloomFilters最近獲得了很好的曝光，但使用它意味著滾動(dòng)自己的瀏覽器或通過(guò)Google搜索代碼。 滾動(dòng)自己的BloomFilter的麻煩在于獲取正確的哈希函數(shù)來(lái)制作過(guò)濾器

有效。 考慮到Guava使用Murmur Hash來(lái)實(shí)現(xiàn)，我們現(xiàn)在就擁有了一個(gè)有效的BloomFilter的有用性，而該庫(kù)只是一個(gè)庫(kù)。

BloomFilter速成課程

BloomFilters本質(zhì)上是位向量。 在較高級(jí)別，BloomFilters以下列方式工作：

將元素添加到過(guò)濾器。

將其哈希幾次，然后將索引與哈希結(jié)果匹配的位設(shè)置為1。

測(cè)試元素是否在集合中時(shí)，請(qǐng)遵循相同的哈希過(guò)程，并檢查這些位是否設(shè)置為1或0。此過(guò)程是BloomFilter如何保證元素不存在的方法。 如果未設(shè)置這些位，則根本不可能將該元素放入集合中。 但是，肯定答案表示元素在集合中或發(fā)生哈希沖突。 可以在此處找到有關(guān)BloomFilter的更詳細(xì)的描述，并在此處找到有關(guān)BloomFilters的良好教程。 根據(jù)Wikipedia的說(shuō)法，Google在BigTable中使用BloomFilters來(lái)避免對(duì)不存在的項(xiàng)目進(jìn)行磁盤查找。 另一個(gè)有趣的用法是使用BloomFilter優(yōu)化SQL查詢 。

使用番石榴BloomFilter

通過(guò)調(diào)用BloomFilter類上的static方法create來(lái)創(chuàng)建Guava BloomFilter，
傳遞一個(gè)Funnel對(duì)象和一個(gè)int表示預(yù)期的插入次數(shù)。 漏斗也是Guava 11中的新功能，它是一個(gè)可以將數(shù)據(jù)發(fā)送到Sink的對(duì)象。 以下示例是默認(rèn)實(shí)現(xiàn)，并且誤報(bào)的百分比為3％。 Guava提供了一個(gè)Funnels類，其中包含兩個(gè)靜態(tài)方法，這些方法提供Funnel接口的實(shí)現(xiàn)，用于將CharSequence或字節(jié)數(shù)組插入到過(guò)濾器中。

//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());

更新：基于路易斯·沃瑟曼的評(píng)論，以下是如何使用自定義Funnel實(shí)現(xiàn)為BigIntegers創(chuàng)建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);

注意事項(xiàng)

正確估計(jì)預(yù)期插入的數(shù)量至關(guān)重要。 當(dāng)插入過(guò)濾器的次數(shù)接近或超過(guò)預(yù)期的數(shù)目時(shí)，BloomFilter開(kāi)始填滿，結(jié)果將產(chǎn)生更多的誤報(bào)，直至無(wú)用之地。 還有另一個(gè)版本的BloomFilter.create方法，該方法帶有一個(gè)附加參數(shù)，雙精度表示所需的錯(cuò)誤命中概率級(jí)別（必須大于0且小于1）。 錯(cuò)誤命中概率的級(jí)別會(huì)影響用于存儲(chǔ)或搜索元素的哈希數(shù)。 所需的百分比越低，執(zhí)行的哈希數(shù)越高。

結(jié)論

BloomFilter是開(kāi)發(fā)人員可以在其工具箱中使用的有用項(xiàng)。 現(xiàn)在，Guava項(xiàng)目使在需要時(shí)開(kāi)始使用BloomFilter變得非常簡(jiǎn)單。 希望您喜歡這篇文章。 歡迎提出有用的意見(jiàn)和建議。

參考資料

• Guava BloomFilter的單元測(cè)試演示 。
• BloomFilter類
• 您想知道的所有關(guān)于BloomFilters的信息 。
• BloomFilter教程 。
• Wikipedia上的BloomFilter 。

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

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

谷歌guava

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的谷歌guava_Google Guava BloomFilter的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。