布隆過濾器
（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。loom Filter是一種空間效率很高的随機資料結構，它實際上是由一個很長的二進制向量和一系列随機映射函數組成，布隆過濾器可以用于可以快速且空間效率高的判斷一個元素是否屬于一個集合；用來實作資料字典，或者集合求交集：
一般來講，計算機中的集合是用哈希表（hash table）來存儲的，其好處是快速準确，缺點是費存儲空間。當集合較小時，這個問題不顯著，但是當集合巨大時，哈希表的存儲效率低就顯現出來了。
概念
集合表示和元素查詢
下面我們具體來看Bloom Filter是如何用位數組表示集合的。初始狀态時，Bloom Filter是一個包含m位的位數組，每一位都置為0。
如果想判斷一個元素是不是在一個集合内，一般想到的是将所有元素儲存起來，然後通過比較确定。連結清單，數等資料結構都是這種思路。但是随着集合中元素的增加，需要的存儲空間越來越大，檢索速度越來越慢。
不過世界上還有一種叫作散清單（又叫哈希表，Hash table）的資料結構。它可以通過一個Hash函數将一個元素映射到一個位陣列中的一個點，這樣一來我們隻要看看這個點是不是 1就知道可以集合中有沒有它了。這就是布隆過濾器的基本思想。
Hash面臨的問題是沖突。假設Hash函數是良好的，如果我們的位陣列長度為m個點，那麼如果想将沖突率降低到1%，這個散清單隻能容納m/100個元素，顯然這就不叫空間有效了，解決的方法也很簡單，就是使用多個Hash函數，如果它們有一個說元素不在集合中，那肯定就不在，如果它們都說在，雖然有一定可能性它們在說謊，不過直覺上判斷這種事情的機率還是比較低的。
布隆過濾器處理流程
布隆過濾器應用很廣泛，比如垃圾郵件過濾，爬蟲的url過濾，防止緩存擊穿等等。下面就來說說布隆過濾器的一個完整流程，相信讀者看到這裡應該能明白布隆過濾器是怎樣工作的。
第一步：開辟空間
開辟一個長度為m的位數組（或者稱二進制向量），這個不同的語言有不同的實作方式，甚至你可以用檔案來實作。
第二步：尋找hash函數
擷取幾個hash函數，前輩們已經發明了很多運作良好的hash函數，比如BKDRHash，JSHash，RSHash等等。這些hash函數我們直接擷取就可以了。
第三步：寫入資料
将所需要判斷的内容經過這些hash函數計算，得到幾個值，比如用3個hash函數，得到值分别是1000，2000，3000。之後設定m位數組的第1000，2000，3000位的值位二進制1。
第四步：判斷
接下來就可以判斷一個新的内容是不是在我們的集合中。判斷的流程和寫入的流程是一緻的。
誤判問題
布隆過濾器雖然很高效（寫入和判斷都是O(1)，所需要的存儲空間極小），但是缺點也非常明顯，那就是會誤判。當集合中的元素越來越多，二進制序列中的1的個數越來越多的時候，判斷一個字元串是否在集合中就很容易誤判，原本不在集合裡面的字元串會被判斷在集合裡面。
數學推導
布隆過濾器原理十分簡單，但是hash函數個數怎麼去判斷，誤判率有多少？
假設二進制序列有m位，那麼經過當一個字元串hash到某一位的機率為：
1
也就是說目前位被反轉為1的機率：
(1)=1
那麼這一位沒有被反轉的機率為：
(0)=1−1
假設我們存入n各元素，使用k個hash函數，此時沒有被翻轉的機率為：
(0)=(1−1)
那什麼情況下我們會誤判呢，就是原本不應該被翻轉的位，結果翻轉了，也就是
(誤判)=1−(1−1)
由于隻有k個hash函數同時誤判了，整體才會被誤判，最後誤判的機率為
(誤判)=(1−(1−1))
要使得誤判率最低，那麼我們需要求誤判與m、n、k之間的關系，現在假設m和n固定，我們計算一下k。可以首先看看這個式子：
(1−1)
由于我們的m很大，通常情況下我們會用2^32來作為m的值。上面的式子中含有一個重要極限
lim→∞(1+1)=
是以誤判率的式子可以寫成
(誤判)=(1−()−/)
接下來令=−/，兩邊同時取對數，求導，得到：
′1=(1−)+(−)1−
讓′=0，則等式後面的為0，最後整理出來的結果是
(1−)(1−)=
計算出來的k為2，約等于0.693，将k代入p(誤判)，我們可以得到機率和m、n之間的關系，最後的結果
(1/2)2，約等于0.6185/
以上我們就得出了最佳hash函數個數以及誤判率與mn之前的關系了。
有需要交流的小夥伴可以點選這裡加本人QQ：luke
最好的貴人
就是拼命努力的自己。