這是一道面試題： 如何在海量數據（如億級數據）中判斷某個數據是否存在？
回想一下，在java中我們可以使用列表、集合等數據結構來存放數據，如hashmap，然後判斷某個數據是否存在，但在此問題中顯然不適用，因為上億的數據在內存較小的計算機中無法存放。
通常我們有以下解決思路：
- 將海量數據分散存儲到多個文件中去，依次將每個文件載入內存進行判定；
- 使用多台機器進行分布式計算，每台機器完成各自任務；
- 使用布隆過濾器（Bloom Filter）。
本篇主要介紹第三種方法： 布隆過濾器 。
我們先熟悉一下 位圖 的概念。
位圖也叫 位數組 ， 可以看成 是一個數組，每個 數組 單元只 存儲「0 」或者「1」，每個 單元 大小為 1bit 。
正是因為位圖所需內存較小，所以這裡可派上用場。
上文說了，位圖存放的是0和1，那麼怎麼和實際數據對應起來呢？很自然能想到使用 哈希函數 。
如圖，將人名存進位圖時，可使用hash函數，將人名映射到對應的位圖單元中，並將該單元數值置為1，0則代表沒有數據映射到該單元，即該單元沒有存放數據。
然而 hash衝突 是不可避免的，圖中可看到「潘金蓮」和「武松」散列到了同一個數組單元。這就出現了一個問題： 假如我們要存儲的數據中有「潘金蓮」，沒有「武松」，當我們對「武松」進行哈希後發現其對應位置為1，於是認為「武松」存在於該數據集中，顯然這個結果是錯誤的，因為1是潘金蓮的映射結果。
那麼怎麼解決這個問題呢？因為hash衝突不可避免，所以我們只能儘量減少衝突的發生。
一般有兩種思路：
- 對位圖擴容，使用容量更大的位圖；
- rehash。
事實上，大名鼎鼎的 布隆過濾器（Bloom Filter） 使用的便是這兩種思路。看下百度百科給出的定義。
布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的 二進位 向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。
簡單而言，布隆過濾器就是 位圖+一系列隨機映射函數 。
如上圖，使用了三個互相獨立的hash函數，對每條數據都進行三次哈希，並將對應單元置為1.
這樣能減少hash衝突的發生，當然hash函數的個數以及位圖的容量是視情況而定的。
布隆過濾器的優點：
1.每個單元只占1bit ， 所用空間小；
2.使用哈希直接查找 ， 查詢時間短 。
布隆過濾器的 缺點：
1.由於hash衝突的存在 ，有一定的 誤判率 ；
2.由於hash衝突的存在 ， 刪除數據較為困難 。
先看誤判率。
其實與剛才「武松和潘金蓮」的問題類似： 假設「吳用」並不在數據集中，但它的位置已被其它數據置為1，那麼判定結果會錯誤。
但如果「吳用」對應的某個位置為0，那麼「吳用」必定不存在，因為如果存在，與其對應的所有位置都為1.
由此可得下面兩條結論：
布隆過濾器判斷數據存在，那麼它可能存在也可能不存在 。
布隆過濾器判斷數據不存在，那麼它必定不存在。
再看刪除數據。
這個也好理解，舉個栗子。
「吳用」和「宋江」都映射到號位置，現在想要刪除「吳用」，那麼號位置到底要不要置為0呢？如果置為0，那麼「宋江」就不高興了，如果不變，顯然又會增加對「吳用」的誤判率（已經被刪除，但該位置還是1）。
在後來的改進中，對位圖的每個單元增加了 計數器 ，計數器初始值為0，每映射一個數據，計數器加1，每刪除一個數據，計數器減1。這樣在刪除數據時，只要計數器 當前值 大於1，該單元就不置為0.
布隆過濾器的應用場景有很多，典型的有Redis的緩存穿透、爬蟲時URL去重、垃圾郵件的判別等。