前言
我們之前講了Redis的快取雪崩、穿透、擊穿，在文章里我們說了解決快取穿透的辦法之一，就是布隆過濾器，但是上次并沒有講如何使用布隆過濾器，
作為暖男的老哥，給你們補上，請叫我IT老暖男，
什么是布隆過濾器
布隆過濾器（Bloom Filter），是1970年，由一個叫布隆的小伙子提出的，距今已經五十年了，和老哥一樣老，
它實際上是一個很長的二進制向量和一系列隨機映射函式，二進制大家應該都清楚，存盤的資料不是0就是1，默認是0，
主要用于判斷一個元素是否在一個集合中，0代表不存在某個資料，1代表存在某個資料，
懂了嗎？作為暖男的老哥在給你們畫張圖來幫助理解：
布隆過濾器用途
-
解決Redis快取穿透（今天重點講解）
-
在爬蟲時，對爬蟲網址進行過濾，已經存在布隆中的網址，不在爬取，
-
垃圾郵件過濾，對每一個發送郵件的地址進行判斷是否在布隆的黑名單中，如果在就判斷為垃圾郵件，
以上只是簡單的用途舉例，大家可以舉一反三，靈活運用在作業中，
布隆過濾器原理
存入程序
布隆過濾器上面說了，就是一個二進制資料的集合，當一個資料加入這個集合時，經歷如下洗禮（這里有缺點，下面會講）：
-
通過K個哈希函式計算該資料，回傳K個計算出的hash值
-
這些K個hash值映射到對應的K個二進制的陣列下標
-
將K個下標對應的二進制資料改成1，
例如，第一個哈希函式回傳x，第二個第三個哈希函式回傳y與z，那么： X、Y、Z對應的二進制改成1，
如圖所示：
查詢程序
布隆過濾器主要作用就是查詢一個資料，在不在這個二進制的集合中，查詢程序如下：
-
通過K個哈希函式計算該資料，對應計算出的K個hash值
-
通過hash值找到對應的二進制的陣列下標
-
判斷：如果存在一處位置的二進制資料是0，那么該資料不存在，如果都是1，該資料存在集合中，（這里有缺點，下面會講）
洗掉程序
一般不能洗掉布隆過濾器里的資料，這是一個缺點之一，我們下面會分析，
布隆過濾器的優缺點
優點
-
由于存盤的是二進制資料，所以占用的空間很小
-
它的插入和查詢速度是非常快的，時間復雜度是O（K），可以聯想一下HashMap的程序
-
保密性很好，因為本身不存盤任何原始資料，只有二進制資料
缺點
這就要回到我們上面所說的那些缺點了，
添加資料是通過計算資料的hash值，那么很有可能存在這種情況：兩個不同的資料計算得到相同的hash值，
例如圖中的“你好”和“hello”，假如最終算出hash值相同，那么他們會將同一個下標的二進制資料改為1，
這個時候，你就不知道下標為2的二進制，到底是代表“你好”還是“hello”，
由此得出如下缺點：
一、存在誤判
假如上面的圖沒有存"hello"，只存了"你好"，那么用"hello"來查詢的時候，會判斷"hello"存在集合中，
因為“你好”和“hello”的hash值是相同的，通過相同的hash值，找到的二進制資料也是一樣的，都是1，
二、洗掉困難
到這里我不說大家應該也明白為什么吧，作為你們的暖男老哥，還是講一下吧，
還是用上面的舉例，因為“你好”和“hello”的hash值相同，對應的陣列下標也是一樣的，
這時候老哥想去洗掉“你好”，將下標為2里的二進制資料，由1改成了0，
那么我們是不是連“hello”都一起刪了呀，（0代表有這個資料，1代表沒有這個資料）
到這里是不是對布隆過濾器已經明白了，都說了我是暖男，
實作布隆過濾器
有很多種實作方式，其中一種就是Guava提供的實作方式，
一、引入Guava pom配置
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>29.0-jre</version>
</dependency>
復制代碼二、代碼實作
這里我們順便測一下它的誤判率，
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterCase {
/**
* 預計要插入多少資料
*/
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) {
// 插入10萬樣本資料
for (int i = 0; i < size; i++) {
bloomFilter.put(i);
}
// 用另外十萬測驗資料，測驗誤判率
int count = 0;
for (int i = size; i < size + 100000; i++) {
if (bloomFilter.mightContain(i)) {
count++;
System.out.println(i + "誤判了");
}
}
System.out.println("總共的誤判數:" + count);
}
}
復制代碼運行結果：
10萬資料里有947個誤判，約等于0.01%，也就是我們代碼里設定的誤判率：fpp = 0.01，
深入分析代碼
核心BloomFilter.create方法
@VisibleForTesting
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
，，，，
}
復制代碼這里有四個引數：
-
funnel：資料型別(一般是呼叫Funnels工具類中的) -
expectedInsertions：期望插入的值的個數 -
fpp：誤判率(默認值為0.03) -
strategy：哈希演算法
我們重點講一下fpp引數
fpp誤判率
情景一：fpp = 0.01
-
誤判個數：947
-
占記憶體大小：9585058位數
情景二：fpp = 0.03（默認引數）
-
誤判個數：3033
-
占記憶體大小：7298440位數
情景總結
-
誤判率可以通過
fpp引數進行調節 -
fpp越小，需要的記憶體空間就越大：0.01需要900多萬位數，0.03需要700多萬位數，
-
fpp越小，集合添加資料時，就需要更多的hash函式運算更多的hash值，去存盤到對應的陣列下標里，（忘了去看上面的布隆過濾存入資料的程序）
上面的numBits，表示存一百萬個int型別數字，需要的位數為7298440，700多萬位，理論上存一百萬個數，一個int是4位元組32位，需要481000000=3200萬位，如果使用HashMap去存，按HashMap50%的存盤效率，需要6400萬位，可以看出BloomFilter的存盤空間很小，只有HashMap的1/10左右
上面的numHashFunctions表示需要幾個hash函式運算，去映射不同的下標存這些數字是否存在（0 or 1），
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/243459.html
標籤：Java