使用 HyperLogLog 數據結構來進行估數，它非常有價值，可以解決很多精確度不高的統計需求。

但是如果我們想知道某一個值是不是已經在 HyperLogLog 結構裡面了，它就無能為力了，它只提供了 pfadd 和 pfcount 方法，沒有提供 pfcontains 這種方法。

有個使用場景，現在新聞客戶端的推送，需要有一個去重功能，推送過的就不能再推送了。

那麼如何實現這種去重功能？

你可能會想在後臺數據庫裡保存一下看過的列表，但是當用戶數太多，而且用戶看到的列表也非常大的時候，性能可能會成為問題。

實際上，如果歷史記錄存儲在關係數據庫裡，去重就需要頻繁地對數據庫進行 exists 查詢，當系統併發量很高時，數據庫是很難扛住壓力的。

你可能又想到了緩存，但是如此多的歷史記錄全部緩存起來，那得浪費多大存儲空間啊？而且這個存儲空間是隨著時間線性增長，你撐得住一個月，你能撐得住幾年麼？但是不緩存的話，性能又跟不上，這該怎麼辦？

這個時候就要介紹今天的主角了--布隆過濾器

布隆過濾器是這樣一個神奇的東西，他是專門用來解決這種去重問題的，而且所需的內存相比set可以節省90%。

可以把它理解成一個不怎麼精確的set。

你可以問他A存不存在？當他說不存在時，這肯定不存在。當他說存在時，也有可能是不存在的。這是因為可能存在一個和A很像的A1，導致布隆過濾器產生了誤判。

套用到新聞推送去重的場景，我們把用戶看過的新聞存起來，推送時，通過查一下是否看過，說沒看過的，肯定就沒看過，可以推送。

Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之後才正式登場。布隆過濾器作為一個插件加載到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。

布隆過濾器有二個基本指令，bf.add 添加元素，bf.exists 查詢元素是否存在，它的用法和 set 集合的 sadd 和 sismember 差不多。注意 bf.add 只能一次添加一個元素，如果想要一次添加多個，就需要用到 bf.madd 指令。同樣如果需要一次查詢多個元素是否存在，就需要用到 bf.mexists 指令。

Java 客戶端 Jedis-2.x 沒有提供指令擴展機制，可以使用 lettuce

誤判率大約 1% 多點。你也許會問這個誤判率還是有點高啊，有沒有辦法降低一點？答案是有的。 我們上面使用的布隆過濾器只是默認參數的布隆過濾器，它在我們第一次 add 的時候自動創建。Redis 其實還提供了自定義參數的布隆過濾器，需要我們在 add 之前使用bf.reserve指令顯式創建。如果對應的 key 已經存在，bf.reserve會報錯。

bf.reserve有三個參數，分別是 key, error_rate和initial_size。錯誤率越低，需要的空間越大。initial_size參數表示預計放入的元素數量，當實際數量超出這個數值時，誤判率會上升。 所以需要提前設置一個較大的數值避免超出導致誤判率升高。如果不使用 bf.reserve，默認的error_rate是 0.01，默認的initial_size是 100。

布隆過濾器的initial_size估計的過大，會浪費存儲空間，估計的過小，就會影響準確率，用戶在使用之前一定要儘可能地精確估計好元素數量，還需要加上一定的冗餘空間以避免實際元素可能會意外高出估計值很多。 布隆過濾器的error_rate越小，需要的存儲空間就越大，對於不需要過於精確的場合，error_rate設置稍大一點也無傷大雅。比如在新聞去重上而言，誤判率高一點只會讓小部分文章不能讓合適的人看到，文章的整體閱讀量不會因為這點誤判率就帶來巨大的改變。

布隆過濾器的原理

大體上是這樣的，布隆過濾器會開闢一個大型的位數組，另外有多個不同的hash函數，比如這裡有f、g、h三個hash函數。每次來一個值，都對其key執行所有的hash函數，將得到的值對位數組長度進行取模得到一個位置。將所有的位置置為1

這樣下一個值過來判斷是否存在時，同樣也進行多個hash函數，得到位置。如果位置中有一個不是1，那這個值一定是不存在的。

全都是1說明高度相似，是極有可能存在的。

如果這個位數組比較稀疏，判斷正確的概率就會很大，如果這個位數組比較擁擠，判斷正確的概率就會降低。具體的概率計算公式比較複雜，感興趣可以閱讀擴展閱讀，非常燒腦。

布隆過濾器的其它應用

在爬蟲系統中，我們需要對 URL 進行去重，已經爬過的網頁就可以不用爬了。但是 URL 太多了，幾千萬幾個億，如果用一個集合裝下這些 URL 地址那是非常浪費空間的。這時候就可以考慮使用布隆過濾器。它可以大幅降低去重存儲消耗，只不過也會使得爬蟲系統錯過少量的頁面。

布隆過濾器在 NoSQL 數據庫領域使用非常廣泛，我們平時用到的 HBase、Cassandra 還有 LevelDB、RocksDB 內部都有布隆過濾器結構，布隆過濾器可以顯著降低數據庫的 IO 請求數量。當用戶來查詢某個 row 時，可以先通過內存中的布隆過濾器過濾掉大量不存在的 row 請求，然後再去磁盤進行查詢。

郵箱系統的垃圾郵件過濾功能也普遍用到了布隆過濾器，因為用了這個過濾器，所以平時也會遇到某些正常的郵件被放進了垃圾郵件目錄中，這個就是誤判所致，概率很低。