布隆過濾器： 我說它不存在，它 百分之兩百 不存在！
（我說它存在，可能我有說錯的時候...）
前言：
該篇文章将會使用最精簡易懂的文字以及小圖來給大家介紹講解（不對哈希政策計算進行詳解）
一.布隆過濾器有啥用？
二.布隆過濾器原理是什麼？
三.java中怎麼使用布隆過濾器？
本篇文章内容可能較多，是以還請耐心。
一. 布隆過濾器 有啥用
簡單兩點叙述：
1. 存值
存值，就是把值存進去， 類似于我們很常用的map，set等；
2.檢驗值是否存在
檢驗，也就是我們想知道某個值是否存在于布隆過濾器裡面，調用相關的檢驗方法，我們會得知一個結果。
特别注意：
布隆過濾器校驗值的結果， 如果傳回結果是 false ，不存在， 那麼是肯定不存在的！
但是如果傳回結果是true，存在，也許有機率是誤報的。
為啥？ 看下面的實作原理你就能明白。
原理是什麼
首先，從上邊介紹的布隆過濾器作用來說，就是個存東西的容器。
但是這個容器有也有自己的特點，
1. 它是一個有固定的大小的，也就是一開始設定它能放多少東西。
2.校驗元素的準确率（指 true 存在的準确率），是會随着存的東西越多而準确率會慢慢降低
怎麼才能更好地了解這個所謂的原理？
我選擇根據布隆過濾器的作用角度去給大家講解。
首先是存值的原理
既然是可以存放值，然後後面又能校驗存在與否，那麼這個存值顯然不是直接丢進去就好，是需要通過算法計算的。
那麼這裡我不對這個算法進行深入地介紹，但是我會以我的圖文方式告訴你，過程和結果。
模拟場景
一個完全是空的布隆過濾器，是一個由m個二進制位構成的數組，這裡我們假設就是m=5個構成的。
預設一開始，這5個二進制位，簡單了解為位置， 都是綁定着一個辨別 0.
那麼接下來看怎麼存值。
布隆過濾器存值，實際上不是存的 真實值，而且通過算法計算後，存入對應的辨別。
過程簡述，也就是布隆過濾器拿到我們傳入的值， 它會将這個值，使用 K個 哈希函數去進行算法計算，計算完後，
會得出K個 二進制位的辨別 0或者1 ，然後對應位置就會存入這個辨別0或者1.
存值過程舉例說明：
我們需要存入的值為 ‘JCTest’ ，
布隆過濾器會采取相關的 計算公式，來算出 需要使用幾個 哈希函數，也就是K的數量：
（m是數組長度，n是插入的元素個數，k是hash函數的個數）
公式大家可以簡單了解下， 我們現在假設 K 是 3.
也就是說 ‘JCTest’ 需要經過3個哈希函數計算 h1 ，h2，h3。
那麼經過算法計算後， 得出的結果是：
二進制 位置 是 一
二進制 位置 是 三
二進制 位置 是 五
那麼這時候，對應的圖會變成這樣：
一，三，五 位置的辨別此刻會綁定上1
同樣，我們存入第二個值 ‘BFTest’，假設也是需要經過 3個哈希函數，
計算出的二進制位 分别是 二 ，三，五， 那麼此刻的布隆過濾器如：
到這裡，其實我們已經了解了這個布隆過濾器的存值方式， 直白的說就是，每個值對于它來說，都會轉化成幾個位置的 1 ，隻要你往裡面存，它就會把位置變成1 ,直到所有位置都變成1了，那麼就不能再存了(大家不用擔心這個位置會不會很快就都變成1，因為我這裡隻是舉例了5個位置，後面的使用介紹環節會告訴你存上百萬都不是問題，因為這些m值，K值，都會根據我設定的存入個數size和期待誤判率進行算法生成的。)
接下來講解布隆過濾器的校驗值存在與否的原理：
很簡單，其實也是我們告訴布隆過濾器一個值， 它也會通過K計算公式，取出一定數量的哈希函數，也是計算出很多個位置，
然後去一個個位置監測，如果每個位置都是1，這時候 它會傳回true，告訴我們，這個值存在；
而如果隻要存在一個位置是0，這時候，它會傳回 false，告訴我們，這個值不存在。
校驗舉例說明：
如果我們想校驗一個值 ，‘JCTest’，
布隆過濾器通過公式計算得出它準備使用三個函數 h1,h2,h3，
然後計算出對應的二進制位 一，三 ，五 ，接着去檢查對應的位置上綁定的辨別，如果都是1，那麼就會傳回存在 true。
誤判舉例說明：
那怎麼會誤判呢？
那就是例如，我們傳入一個需要校驗的值，‘Test’，布隆過濾器通過相關函數算出，位置恰好也是一，二，三 ，那我們實際上根本沒存過Test，
但是因為我們之前存JCtest 和 BFTest 導緻了相關的位置都綁定了辨別1，是以這時候布隆過濾器就産生了誤判現象。（這個機率不高其實，接下來的實用介紹會了解到）
PS： 也是因為這種校驗的政策，是以隻要在校驗的時候，檢測到一個對應的位置不為1，那麼毫無疑問！這個值是百分之兩百不存在的！
怎麼使用布隆過濾器
了解了布隆過濾器的作用和原理後，那麼我們接下來在java中使用它。
該篇就不去手動實作布隆過濾器了，因為 在GoogleGuavalibrary中Google為我們提供了一個布隆過濾器的實作。
是以我們第一步，導入jar包：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>19.0</version>
</dependency> 然後建一個BloomFilterTest.class ：
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
/**
* @Author : JCccc
* @CreateTime : 2020/3/31
* @Description :
**/
public class BloomFilterTest {
private static int size = 1000000;//預計要插入多少資料
private static double fpp = 0.01;//期望的誤判率
public static void main(String[] args) {
//存入的是字元串
BloomFilter<CharSequence> bloomFilterStr = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), size, fpp);
for (int i = 0; i < size; i++) {
bloomFilterStr.put("test" + i);
}
boolean containsValue1 = bloomFilterStr.mightContain("test1");
boolean containsValue2 = bloomFilterStr.mightContain("test34");
boolean containsValue3 = bloomFilterStr.mightContain("test1000001");
System.out.println(containsValue1);
System.out.println(containsValue2);
System.out.println(containsValue3);
}
} 校驗結果：
然後再試下，使用布隆過濾器存入數字：
BloomFilter<Integer> bloomFilterInt = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
for (int i=0; i<size;i++){
bloomFilterInt.put(i);
}
boolean containsValue4 = bloomFilterInt.mightContain(1);
boolean containsValue5 = bloomFilterInt.mightContain(2);
boolean containsValue6 = bloomFilterInt.mightContain(10000002);
System.out.println(containsValue4);
System.out.println(containsValue5);
System.out.println(containsValue6); 結果：
可以看到以上兩存值&校驗的測試都是準确無誤的，那麼我們大規模的存值檢查，看看存在的誤判現象：
我們剛剛往 bloomFilterInt 這個過濾器裡面存入了0到1000000 個數字值，
那麼接下來我們直接從1000000開始去累加到2000000，去進行校驗，
我們明确知道 這時候的布隆過濾器裡面有1百萬個值，而我們的1000000到2000000除了‘1000000’其實都是不存在的，都應該傳回false。
接下來我們用代碼來模拟下這個判斷存在 的誤判現象：
int size = 1000000;//預計要插入多少資料
double fpp = 0.01;//期望的誤判率
BloomFilter<Integer> bloomFilterInt = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
for (int i=0; i<size;i++){
bloomFilterInt.put(i);
}
int count = 0;
for (int i = 1000000; i < 2000000; i++) {
if (bloomFilterInt.mightContain(i)) {
count++;
System.out.println(i + "誤判了");
}
}
System.out.println("總共的誤判數:" + count); 結果：
在這一百萬個數值的布隆過濾器裡面，再校驗一百萬次，存在的誤判數是10314次。
是以咱們使用布隆過濾器進行值的存入和校驗時，
我們應該更偏向使用 它傳回的false 進行結合業務做操作，因為它的判斷如果傳回fasle，那是百分之兩百可信的！
當然其實true誤報的情況，機率也是非常小的，在一定的業務場景也能使用的其實。
ps：
例如，我們先到布隆過濾器查詢一個訂單是否存在，不存在就當失敗訂單處理；
存在的話，我們再去資料庫擷取詳情資訊進行訂單的後續操作。
這時候隻需要我們再接收到訂單存入資料庫的時候，把單獨的訂單号存入布隆過濾器即可。
就算布隆過濾器誤判了，我們再去資料庫查詢訂單時，加上多一步校驗存在與否即可。
這樣就可以減輕每個訂單都需要查資料庫的壓力。
（其實有過了解redis使用的小夥伴，就明顯知道布隆過濾器配和redis使用會非常不錯，可以一定程度防止緩存穿透，這些我有時間會在我的redis欄目寫一篇對緩存穿透和緩存雪崩的介紹和解決思路相關的文章）
那麼這篇普及布隆過濾器就先到這吧。