前言
曾經在面試的時候遇到過一個問題，就是如何在100億個數據中判斷某個數據是否存在。當時，我給出的解決方法是，將這100億個數據先存放到hashmap中，然後再進行查詢判斷是否存在某個數。我以為這將是一個漂亮的回答，但說完後，從面試官凝重的表情我看到，這不是他想聽到的結果。
現在看來，將100億個數據先存放到hashmap，然後再判斷是否存在某個數，的確不是一個好方法。首先，寫的性能比較低；其次，所需的內存太大。據統計，100億個數據存入hashmap大概需要幾百G的內存。
那有沒有一個更好的實現方式呢？有，可以使用布隆過濾，即是本文即將介紹的主要內容。
什麼叫布隆過濾
布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制矢量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。
布隆過濾的原理
下圖表示有三個hash函數，比如一個集合中有x，y，z三個元素，分別用三個hash函數映射到二進制序列的某些位上，假設我們判斷w是否在集合中，同樣用三個hash函數來映射，結果發現取得的結果不全為1，則表示w不在集合裡面。
具體的操作流程如下：
第一步：開闢空間
開闢一個長度為m的位數組（或者稱二進制向量），這個不同的語言有不同的實現方式，甚至你可以用文件來實現。
第二步：尋找hash函數
獲取幾個hash函數，前輩們已經發明瞭很多運行良好的hash函數，比如BKDRHash，JSHash，RSHash等等。這些hash函數我們直接獲取就可以了。
第三步：寫入數據
將所需要判斷的內容經過這些hash函數計算，得到幾個值，比如用3個hash函數，得到值分別是1000，2000，3000。之後設置m位數組的第1000，2000，3000位的值位二進制1。
第四步：判斷
接下來就可以判斷一個新的內容是不是在我們的集合中。判斷的流程和寫入的流程是一致的。
布隆過濾的PHP實現
由於Redis實現了setbit和getbit操作，天然適合實現布隆過濾器，redis也有布隆過濾器插件，所以這裡使用php+redis實現布隆過濾器。
首先定義一個hash函數集合類，這些hash函數不一定都用到，實際上32位hash值的用3個就可以了，具體的數量可以根據你的位序列總量和你需要存入的量決定，上面已經給出最佳值。
接著就是連接redis來進行操作
上面定義的是一個抽象類，如果要使用，可以根據具體的業務來使用。比如下面是一個過濾重複內容的過濾器。
參考
https://blog.csdn.net/leeafay/article/details/78681534
http://imhuchao.com/1271.html
閱讀更多 編碼之道 的文章
