前言
如果要判斷一個元素是否在集合中，一般的思路是保存集合中的所有元素，然后通過比較來確定。鏈表、樹、哈希表（也叫哈希表、哈希表）等數據結構都是這種方式，存儲位置要么是磁盤，要么是內存。很多時候，要么時間換空間，要么空間換時間。
在對響應時間要求比較嚴格的情況下，如果我們有里面，那么隨著集合中元素數量的增加，我們需要的存儲空間越來越大，檢索時間也越來越長，導致內存過多開銷和時間效率變低。
這時候需要考慮的問題是，在數據量比較大的情況下，既能滿足時間要求，又能滿足空間要求，所以我們需要一種時間和空間消耗都比較小的數據結構和算法。布隆過濾器是一種解決方案。
什么是布隆過濾器？
Bloom Filter, 布隆過濾器由 Bloom于 1970 年提出。它實際上是一個長二進制向量和一系列隨機映射函數, 布隆過濾器可用于檢索元素是否在集合中。其優點是空間效率和查詢時間遠超一般算法，缺點是存在一定的誤識別率和刪除難度。根據它的特性，應用場景有如下：
- 爬蟲過濾。
- 郵箱垃圾郵件過濾。
- 黑名單過濾。
- 大數據去重。
- 防止緩存穿透。
布隆過濾器原理
布隆過濾器的原理是當一個元素加入到集合中時，通過K個哈希函數將該元素映射到一個位數組中的K個點，并將它們置為1。檢索時，我們只需要看這些點是否都為1，就可以（大概）知道它是否存在于集合中。如果這些點中的任何一個有0，則檢查的元素一定不存在。如果它們都是1，則被選中的元素很可能在那里。
Bloom Filter與單一哈希函數Bit-Map的區別在于，Bloom Filter使用k個哈希函數，每個字符串對應k個bits，從而降低碰撞概率。
由于Bloom filter只存儲0和1而不存儲具體值，所以在一些機密場合具有先天優勢。位圖的每一位都是一個位，所以通過位圖有10億個位置，位圖的大小為0.12G，插入和查詢的時間復雜度為O(k),k是哈希函數的個數。
布隆過濾器的問題
布隆過濾器之所以能夠在時間和空間上取得比較高的效率，是因為它犧牲了判斷的準確性和刪除的便利性。
- 判斷錯誤
有可能要找的元素不在容器中，但是散列后得到的k個位置都是1。如果布隆過濾器中存儲了黑名單，則可以通過創建白名單來存儲可能被誤判的元素。
對于這個問題，可以通過增加位圖數組的大小（位圖數組越大，占用的內存越大）和減少哈希沖突來解決。但缺點是會增加占用的內存空間。
另一種解決方案是增加散列函數的數量并減少散列沖突。如果同一個鍵值等于一個函數，經過兩個或多個哈希函數得到相等結果的概率自然會降低。然而，這會導致計算效率的降低，因為時間復雜度退化為O(hash times)。
- 難以去除
放置在容器中的元素映射到位數組的 k 個位置中的 1。刪除的時候不能簡單的直接設置為0，這樣可能會影響其他元素的判斷。你可以使用??Counting Bloom Filter??來解決這個問題。
Java中如何使用布隆過濾器
google的guava就提供了這樣的API.
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>22.0</version>
</dependency>
編寫測試代碼
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class GuavaBloomFilter {
public static void main(String[] args) {
int total = 1000000;
// default false positive ratefpp0.03
// fpp:There will always be a false positive rate in a Bloom filter
// Because hash collisions are impossible to avoid 100%.
// Bloom filter calls this misjudgment rate false positive probability，abbreviated as fpp
BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
// Initialize the total bar data into the filter
for (int i = 0; i < total; i++) {
bf.put("" + i);
}
// Determine whether the value exists in the filter
int count = 0;
for (int i = 0; i < total + 10000; i++) {
if (bf.mightContain("" + i)) {
count++;
}
}
System.out.println("Matched quantity " + count);
// Specified misjudgment rate: 1/10,000 to improve matching accuracy
BloomFilter<CharSequence> bfWithFpp = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0001);
for (int i = 0; i < total; i++) {
bfWithFpp.put("" + i);
}
int countFpp = 0;
for (int i = 0; i < total + 10000; i++) {
if (bfWithFpp.mightContain("" + i)) {
countFpp++;
}
}
//The smaller the value of the false positive rate fpp
// the higher the matching accuracy.
// When the value of the false positive rate fpp is reduced
// the storage space required is also larger
// Therefore, in actual use,
// a trade-off needs to be made between the false positive rate and the storage space.
System.out.println("The specified false positive rate has matched the number " + countFpp);// (1000001 - 1000000)/(1000000 + 10000) * 100 ≈ 0.0001
}
}
