作者：CodeBear的園子
www.cnblogs.com/CodeBear/p/10911177.html
本文是站在小白的角度去討論布隆過濾器，如果你是科班出身，或者比較聰明，又或者真正想完全搞懂布隆過濾器的可以移步，
不知道從什么時候開始，本來默默無聞的布隆過濾器一下子名聲大燥，仿佛身在互聯網，做著開發的，無人不知，無人不曉，哪怕對技術不是很關心的小伙伴也聽過它的名號，
我也花了不少時間去研究布隆過濾器，看了不少博客，無奈不是科班出身，又沒有那么聰明的頭腦，又比較懶...經過“放棄，拿起，放棄，拿起”的無限輪回，應該算是了解了布隆過濾器的核心思想，所以想給大家分享下，
布隆過濾器的應用
我們先來看下布隆過濾器的應用場景，讓大家知道神奇的布隆過濾器到底能做什么，
快取穿透
我們經常會把一部分資料放在Redis等快取，比如產品詳情，這樣有查詢請求進來，我們可以根據產品Id直接去快取中取資料，而不用讀取資料庫，這是提升性能最簡單，最普遍，也是最有效的做法，面試常問，快取三大問題及解決方案！
一般的查詢請求流程是這樣的：先查快取，有快取的話直接回傳，如果快取中沒有，再去資料庫查詢，然后再把資料庫取出來的資料放入快取，一切看起來很美好，
但是如果現在有大量請求進來，而且都在請求一個不存在的產品Id，會發生什么？既然產品Id都不存在，那么肯定沒有快取，沒有快取，那么大量的請求都懟到資料庫，資料庫的壓力一下子就上來了，還有可能把資料庫打死，
雖然有很多辦法都可以解決這問題，但是我們的主角是“布隆過濾器”，沒錯，“布隆過濾器”就可以解決（緩解）快取穿透問題，至于為什么說是“緩解”，看下去你就明白了，
大量資料，判斷給定的是否在其中
現在有大量的資料，而這些資料的大小已經遠遠超出了服務器的記憶體，現在再給你一個資料，如何判斷給你的資料在不在其中，
如果服務器的記憶體足夠大，那么用HashMap是一個不錯的解決方案，理論上的時間復雜度可以達到O(1)，但是現在資料的大小已經遠遠超出了服務器的記憶體，所以無法使用HashMap，這個時候就可以使用“布隆過濾器”來解決這個問題，但是還是同樣的，會有一定的“誤判率”，
什么是布隆過濾器
布隆過濾器是一個叫“布隆”的人提出的，它本身是一個很長的二進制向量，既然是二進制的向量，那么顯而易見的，存放的不是0，就是1，
現在我們新建一個長度為16的布隆過濾器，默認值都是0，就像下面這樣：
現在需要添加一個資料：
我們通過某種計算方式，比如Hash1，計算出了Hash1(資料)=5，我們就把下標為5的格子改成1，就像下面這樣：
我們又通過某種計算方式，比如Hash2，計算出了Hash2(資料)=9，我們就把下標為9的格子改成1，就像下面這樣：
還是通過某種計算方式，比如Hash3，計算出了Hash3(資料)=2，我們就把下標為2的格子改成1，就像下面這樣：
這樣，剛才添加的資料就占據了布隆過濾器“5”，“9”，“2”三個格子，
可以看出，僅僅從布隆過濾器本身而言，根本沒有存放完整的資料，只是運用一系列隨機映射函式計算出位置，然后填充二進制向量，
這有什么用呢？比如現在再給你一個資料，你要判斷這個資料是否重復，你怎么做？
你只需利用上面的三種固定的計算方式，計算出這個資料占據哪些格子，然后看看這些格子里面放置的是否都是1，如果有一個格子不為1，那么就代表這個數字不在其中，
這很好理解吧，比如現在又給你了剛才你添加進去的資料，你通過三種固定的計算方式，算出的結果肯定和上面的是一模一樣的，也是占據了布隆過濾器“5”，“9”，“2”三個格子，
但是有一個問題需要注意，如果這些格子里面放置的都是1，不一定代表給定的資料一定重復，也許其他資料經過三種固定的計算方式算出來的結果也是相同的，這也很好理解吧，比如我們需要判斷物件是否相等，是不可以僅僅判斷他們的哈希值是否相等的，
也就是說布隆過濾器只能判斷資料是否一定不存在，而無法判斷資料是否一定存在，
按理來說，介紹完了新增、查詢的流程，就要介紹洗掉的流程了，但是很遺憾的是布隆過濾器是很難做到洗掉資料的，為什么？你想想，比如你要洗掉剛才給你的資料，你把“5”，“9”，“2”三個格子都改成了0，但是可能其他的資料也映射到了“5”，“9”，“2”三個格子啊，這不就亂套了嗎？
相信經過我這么一介紹，大家對布隆過濾器應該有一個淺顯的認識了，至少你應該清楚布隆過濾器的優缺點了：
-
優點：由于存放的不是完整的資料，所以占用的記憶體很少，而且新增，查詢速度夠快；
-
缺點：隨著資料的增加，誤判率隨之增加；無法做到洗掉資料；只能判斷資料是否一定不存在，而無法判斷資料是否一定存在，
可以看到，布隆過濾器的優點和缺點一樣明顯，
在上文中，我舉的例子二進制向量長度為16，由三個隨機映射函式計算位置，在實際開發中，如果你要添加大量的資料，僅僅16位是遠遠不夠的，為了讓誤判率降低，我們還可以用更多的隨機映射函式、更長的二進制向量去計算位置，
guava實作布隆過濾器
現在相信你對布隆過濾器應該有一個比較感性的認識了，布隆過濾器核心思想其實并不難，難的在于如何設計隨機映射函式，到底映射幾次，二進制向量的長度設定為多少比較好，這可能就不是一般的開發可以駕馭的了，
好在Google大佬給我們提供了開箱即用的組件，來幫助我們實作布隆過濾器，現在就讓我們看看怎么Google大佬送給我們的“禮物”吧，
首先在pom引入“禮物”：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>19.0</version>
</dependency>
然后就可以測驗啦：
private static int size = 1000000;//預計要插入多少資料
private static double fpp = 0.01;//期望的誤判率
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
public static void main(String[] args) {
//插入資料
for (int i = 0; i < 1000000; i++) {
bloomFilter.put(i);
}
int count = 0;
for (int i = 1000000; i < 2000000; i++) {
if (bloomFilter.mightContain(i)) {
count++;
System.out.println(i + "誤判了");
}
}
System.out.println("總共的誤判數:" + count);
}
代碼簡單分析：
我們定義了一個布隆過濾器，有兩個重要的引數，分別是 我們預計要插入多少資料，我們所期望的誤判率，誤判率不能為0，
我向布隆過濾器插入了0-1000000，然后用1000000-2000000來測驗誤判率，
運行結果：
1999501誤判了
1999567誤判了
1999640誤判了
1999697誤判了
1999827誤判了
1999942誤判了
總共的誤判數:10314
現在總共有100萬資料是不存在的，誤判了10314次，我們計算下誤判率：
和我們定義的期望誤判率0.01相差無幾，
redis實作布隆過濾器
上面使用guava實作布隆過濾器是把資料放在本地記憶體中，無法實作布隆過濾器的共享，我們還可以把資料放在redis中，用 redis來實作布隆過濾器，我們要使用的資料結構是bitmap，你可能會有疑問，redis支持五種資料結構：String，List，Hash，Set，ZSet，沒有bitmap呀，沒錯，實際上bitmap的本質還是String，
可能有小伙伴會說，納尼，布隆過濾器還沒介紹完，怎么又出來一個bitmap，沒事，你可以把bitmap就理解為一個二進制向量，
要用redis來實作布隆過濾器，我們需要自己設計映射函式，自己度量二進制向量的長度，這對我來說，無疑是一個不可能完成的任務，只能借助搜索引擎，下面直接放出代碼把，
public class RedisMain {
static final int expectedInsertions = 100;//要插入多少資料
static final double fpp = 0.01;//期望的誤判率
//bit陣列長度
private static long numBits;
//hash函式數量
private static int numHashFunctions;
static {
numBits = optimalNumOfBits(expectedInsertions, fpp);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
}
public static void main(String[] args) {
Jedis jedis = new Jedis("192.168.0.109", 6379);
for (int i = 0; i < 100; i++) {
long[] indexs = getIndexs(String.valueOf(i));
for (long index : indexs) {
jedis.setbit("codebear:bloom", index, true);
}
}
for (int i = 0; i < 100; i++) {
long[] indexs = getIndexs(String.valueOf(i));
for (long index : indexs) {
Boolean isContain = jedis.getbit("codebear:bloom", index);
if (!isContain) {
System.out.println(i + "肯定沒有重復");
}
}
System.out.println(i + "可能重復");
}
}
/**
* 根據key獲取bitmap下標
*/
private static long[] getIndexs(String key) {
long hash1 = hash(key);
long hash2 = hash1 >>> 16;
long[] result = new long[numHashFunctions];
for (int i = 0; i < numHashFunctions; i++) {
long combinedHash = hash1 + i * hash2;
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
result[i] = combinedHash % numBits;
}
return result;
}
private static long hash(String key) {
Charset charset = Charset.forName("UTF-8");
return Hashing.murmur3_128().hashObject(key, Funnels.stringFunnel(charset)).asLong();
}
//計算hash函式個數
private static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
//計算bit陣列長度
private static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
}
運行結果：
88可能重復
89可能重復
90可能重復
91可能重復
92可能重復
93可能重復
94可能重復
95可能重復
96可能重復
97可能重復
98可能重復
99可能重復
本篇博客到這里就結束了，謝謝大家，寫作不易，堅持更難，如大家喜歡就幫忙推送給其他人！
關注公眾號Java技術堆疊回復"面試"獲取我整理的2020最全面試題及答案，
推薦去我的博客閱讀更多：
1.Java JVM、集合、多執行緒、新特性系列教程
2.Spring MVC、Spring Boot、Spring Cloud 系列教程
3.Maven、Git、Eclipse、Intellij IDEA 系列工具教程
4.Java、后端、架構、阿里巴巴等大廠最新面試題
覺得不錯，別忘了點贊+轉發哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/144237.html
標籤：Java