什麼是布隆過濾器
本質上布隆過濾器是一種資料結構，比較巧妙的機率型資料結構（probabilistic data structure），特點是高效地插入和查詢，可以用來告訴你 “某樣東西一定不存在或者可能存在”。相比于傳統的 List、Set、Map 等資料結構，它更高效、占用空間更少，但是缺點是其傳回的結果是機率性的，而不是确切的
實作原理
HashMap 的問題
講述布隆過濾器的原理之前，我們先思考一下，通常你判斷某個元素是否存在用的是什麼？應該蠻多人回答 HashMap 吧，确實可以将值映射到 HashMap 的 Key，然後可以在 O(1) 的時間複雜度内傳回結果，效率奇高。但是 HashMap 的實作也有缺點，例如存儲容量占比高，考慮到負載因子的存在，通常空間是不能被用滿的，而一旦你的值很多例如上億的時候，那 HashMap 占據的記憶體大小就變得很可觀了
還比如說你的資料集存儲在遠端伺服器上，本地服務接受輸入，而資料集非常大不可能一次性讀進記憶體建構 HashMap 的時候，也會存在問題
布隆過濾器資料結構
布隆過濾器是一個 bit 向量或者說 bit 數組，長這樣：
如果我們要映射一個值到布隆過濾器中，我們需要使用多個不同的哈希函數生成多個哈希值，并對每個生成的哈希值指向的 bit 位置 1，例如針對值 “baidu” 和三個不同的哈希函數分别生成了哈希值 1、4、7，則上圖轉變為：
我們現在再存一個值 “tencent”，如果哈希函數傳回 3、4、8 的話，圖繼續變為：
值得注意的是，4 這個 bit 位由于兩個值的哈希函數都傳回了這個 bit 位，是以它被覆寫了。現在我們如果想查詢 “dianping” 這個值是否存在，哈希函數傳回了 1、5、8三個值，結果我們發現 5 這個 bit 位上的值為 0，說明沒有任何一個值映射到這個 bit 位上，是以我們可以很确定地說 “dianping” 這個值不存在。而當我們需要查詢 “baidu” 這個值是否存在的話，那麼哈希函數必然會傳回 1、4、7，然後我們檢查發現這三個 bit 位上的值均為 1，那麼我們可以說 “baidu” 存在了麼？答案是不可以，隻能是 “baidu” 這個值可能存在。
這是為什麼呢？答案跟簡單，因為随着增加的值越來越多，被置為 1 的 bit 位也會越來越多，這樣某個值 “taobao” 即使沒有被存儲過，但是萬一哈希函數傳回的三個 bit 位都被其他值置位了 1 ，那麼程式還是會判斷 “taobao” 這個值存在
支援删除麼
傳統的布隆過濾器并不支援删除操作。但是名為 Counting Bloom filter 的變種可以用來測試元素計數個數是否絕對小于某個門檻值，它支援元素删除。可以參考文章 Counting Bloom Filter 的原理和實作
如何選擇哈希函數個數和布隆過濾器長度
很顯然，過小的布隆過濾器很快所有的 bit 位均為 1，那麼查詢任何值都會傳回“可能存在”，起不到過濾的目的了。布隆過濾器的長度會直接影響誤報率，布隆過濾器越長其誤報率越小。另外，哈希函數的個數也需要權衡，個數越多則布隆過濾器 bit 位置位 1 的速度越快，且布隆過濾器的效率越低；但是如果太少的話，那我們的誤報率會變高
k 為哈希函數個數，m 為布隆過濾器長度，n 為插入的元素個數，p 為誤報率
如何選擇适合業務的 k 和 m 值呢，這裡直接貼一個公式：
如何推導這個公式這裡隻是提一句，因為對于使用來說并沒有太大的意義，你讓一個高中生來推會推得很快。k 次哈希函數某一 bit 位未被置為 1 的機率為：
插入n個元素後依舊為 0 的機率和為 1 的機率分别是：
标明某個元素是否在集合中所需的 k 個位置都按照如上的方法設定為 1，但是該方法可能會使算法錯誤的認為某一原本不在集合中的元素卻被檢測為在該集合中（False Positives），該機率由以下公式确定
最佳實踐
常見的适用常見有，利用布隆過濾器減少磁盤 IO 或者網絡請求，因為一旦一個值必定不存在的話，我們可以不用進行後續昂貴的查詢請求
另外，既然你使用布隆過濾器來加速查找和判斷是否存在，那麼性能很低的哈希函數不是個好選擇，推薦 MurmurHash、Fnv 這些
大Value拆分
Redis 因其支援 setbit 和 getbit 操作，且純記憶體性能高等特點，是以天然就可以作為布隆過濾器來使用。但是布隆過濾器的不當使用極易産生大 Value，增加 Redis 阻塞風險，是以生成環境中建議對體積龐大的布隆過濾器進行拆分