Java技術棧

www.javastack.cn

打開網(wǎng)站看更多優(yōu)質文章

作者：CodeBear的園子

www.cnblogs.com/CodeBear/p/10911177.html

本文是站在小白的角度去討論布隆過濾器，如果你是科班出身，或者比較聰明，又或者真正想完全搞懂布隆過濾器的可以移步。

不知道從什么時候開始，本來默默無聞的布隆過濾器一下子名聲大燥，仿佛身在互聯(lián)網(wǎng)，做著開發(fā)的，無人不知，無人不曉，哪怕對技術不是很關心的小伙伴也聽過它的名號。

我也花了不少時間去研究布隆過濾器，看了不少博客，無奈不是科班出身，又沒有那么聰明的頭腦，又比較懶...經(jīng)過“放棄，拿起，放棄，拿起”的無限輪回，應該算是了解了布隆過濾器的核心思想，所以想給大家分享下。

布隆過濾器的應用

我們先來看下布隆過濾器的應用場景，讓大家知道神奇的布隆過濾器到底能做什么。

緩存穿透

我們經(jīng)常會把一部分數(shù)據(jù)放在Redis等緩存，比如產(chǎn)品詳情。這樣有查詢請求進來，我們可以根據(jù)產(chǎn)品Id直接去緩存中取數(shù)據(jù)，而不用讀取數(shù)據(jù)庫，這是提升性能最簡單，最普遍，也是最有效的做法。面試常問，緩存三大問題及解決方案！一般的查詢請求流程是這樣的：先查緩存，有緩存的話直接返回，如果緩存中沒有，再去數(shù)據(jù)庫查詢，然后再把數(shù)據(jù)庫取出來的數(shù)據(jù)放入緩存，一切看起來很美好。但是如果現(xiàn)在有大量請求進來，而且都在請求一個不存在的產(chǎn)品Id，會發(fā)生什么？既然產(chǎn)品Id都不存在，那么肯定沒有緩存，沒有緩存，那么大量的請求都懟到數(shù)據(jù)庫，數(shù)據(jù)庫的壓力一下子就上來了，還有可能把數(shù)據(jù)庫打死。雖然有很多辦法都可以解決這問題，但是我們的主角是“布隆過濾器”，沒錯，“布隆過濾器”就可以解決(緩解)緩存穿透問題。至于為什么說是“緩解”，看下去你就明白了。

大量數(shù)據(jù)，判斷給定的是否在其中

現(xiàn)在有大量的數(shù)據(jù)，而這些數(shù)據(jù)的大小已經(jīng)遠遠超出了服務器的內存，現(xiàn)在再給你一個數(shù)據(jù)，如何判斷給你的數(shù)據(jù)在不在其中。

如果服務器的內存足夠大，那么用HashMap是一個不錯的解決方案，理論上的時間復雜度可以達到O(1)，但是現(xiàn)在數(shù)據(jù)的大小已經(jīng)遠遠超出了服務器的內存，所以無法使用HashMap，這個時候就可以使用“布隆過濾器”來解決這個問題。但是還是同樣的，會有一定的“誤判率”。

什么是布隆過濾器

布隆過濾器是一個叫“布隆”的人提出的，它本身是一個很長的二進制向量，既然是二進制的向量，那么顯而易見的，存放的不是0，就是1。

現(xiàn)在我們新建一個長度為16的布隆過濾器，默認值都是0，就像下面這樣：

現(xiàn)在需要添加一個數(shù)據(jù)：

我們通過某種計算方式，比如Hash1，計算出了Hash1(數(shù)據(jù))=5，我們就把下標為5的格子改成1，就像下面這樣：

我們又通過某種計算方式，比如Hash2，計算出了Hash2(數(shù)據(jù))=9，我們就把下標為9的格子改成1，就像下面這樣：

還是通過某種計算方式，比如Hash3，計算出了Hash3(數(shù)據(jù))=2，我們就把下標為2的格子改成1，就像下面這樣：

這樣，剛才添加的數(shù)據(jù)就占據(jù)了布隆過濾器“5”，“9”，“2”三個格子。

可以看出，僅僅從布隆過濾器本身而言，根本沒有存放完整的數(shù)據(jù)，只是運用一系列隨機映射函數(shù)計算出位置，然后填充二進制向量。

這有什么用呢？比如現(xiàn)在再給你一個數(shù)據(jù)，你要判斷這個數(shù)據(jù)是否重復，你怎么做？

你只需利用上面的三種固定的計算方式，計算出這個數(shù)據(jù)占據(jù)哪些格子，然后看看這些格子里面放置的是否都是1，如果有一個格子不為1，那么就代表這個數(shù)字不在其中。

這很好理解吧，比如現(xiàn)在又給你了剛才你添加進去的數(shù)據(jù)，你通過三種固定的計算方式，算出的結果肯定和上面的是一模一樣的，也是占據(jù)了布隆過濾器“5”，“9”，“2”三個格子。

但是有一個問題需要注意，如果這些格子里面放置的都是1，不一定代表給定的數(shù)據(jù)一定重復，也許其他數(shù)據(jù)經(jīng)過三種固定的計算方式算出來的結果也是相同的。這也很好理解吧，比如我們需要判斷對象是否相等，是不可以僅僅判斷他們的哈希值是否相等的。

也就是說布隆過濾器只能判斷數(shù)據(jù)是否一定不存在，而無法判斷數(shù)據(jù)是否一定存在。

按理來說，介紹完了新增、查詢的流程，就要介紹刪除的流程了，但是很遺憾的是布隆過濾器是很難做到刪除數(shù)據(jù)的，為什么？你想想，比如你要刪除剛才給你的數(shù)據(jù)，你把“5”，“9”，“2”三個格子都改成了0，但是可能其他的數(shù)據(jù)也映射到了“5”，“9”，“2”三個格子啊，這不就亂套了嗎？

相信經(jīng)過我這么一介紹，大家對布隆過濾器應該有一個淺顯的認識了，至少你應該清楚布隆過濾器的優(yōu)缺點了：

• 優(yōu)點：由于存放的不是完整的數(shù)據(jù)，所以占用的內存很少，而且新增，查詢速度夠快；

• 缺點：隨著數(shù)據(jù)的增加，誤判率隨之增加；無法做到刪除數(shù)據(jù)；只能判斷數(shù)據(jù)是否一定不存在，而無法判斷數(shù)據(jù)是否一定存在。

可以看到，布隆過濾器的優(yōu)點和缺點一樣明顯。

在上文中，我舉的例子二進制向量長度為16，由三個隨機映射函數(shù)計算位置，在實際開發(fā)中，如果你要添加大量的數(shù)據(jù)，僅僅16位是遠遠不夠的，為了讓誤判率降低，我們還可以用更多的隨機映射函數(shù)、更長的二進制向量去計算位置。

guava實現(xiàn)布隆過濾器

現(xiàn)在相信你對布隆過濾器應該有一個比較感性的認識了，布隆過濾器核心思想其實并不難，難的在于如何設計隨機映射函數(shù)，到底映射幾次，二進制向量的長度設置為多少比較好，這可能就不是一般的開發(fā)可以駕馭的了。

好在Google大佬給我們提供了開箱即用的組件，來幫助我們實現(xiàn)布隆過濾器，現(xiàn)在就讓我們看看怎么Google大佬送給我們的“禮物”吧。

首先在pom引入“禮物”：

<dependency>
??<groupId>com.google.guavagroupId>
??<artifactId>guavaartifactId>
??<version>19.0version>
dependency>

然后就可以測試啦：

private?static?int?size = 1000000;//預計要插入多少數(shù)據(jù)private?static?double?fpp = 0.01;//期望的誤判率private?static?BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);public?static?void?main(String[] args) {//插入數(shù)據(jù)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("總共的誤判數(shù):"?+ count);
}

代碼簡單分析：

我們定義了一個布隆過濾器，有兩個重要的參數(shù)，分別是 我們預計要插入多少數(shù)據(jù)，我們所期望的誤判率，誤判率不能為0。

我向布隆過濾器插入了0-1000000，然后用1000000-2000000來測試誤判率。

運行結果：

1999501誤判了1999567誤判了1999640誤判了1999697誤判了1999827誤判了1999942誤判了
總共的誤判數(shù):10314

現(xiàn)在總共有100萬數(shù)據(jù)是不存在的，誤判了10314次，我們計算下誤判率：

和我們定義的期望誤判率0.01相差無幾。

redis實現(xiàn)布隆過濾器

上面使用guava實現(xiàn)布隆過濾器是把數(shù)據(jù)放在本地內存中，無法實現(xiàn)布隆過濾器的共享，我們還可以把數(shù)據(jù)放在redis中，用 redis來實現(xiàn)布隆過濾器，我們要使用的數(shù)據(jù)結構是bitmap，你可能會有疑問，redis支持五種數(shù)據(jù)結構：String，List，Hash，Set，ZSet，沒有bitmap呀。沒錯，實際上bitmap的本質還是String。

可能有小伙伴會說，納尼，布隆過濾器還沒介紹完，怎么又出來一個bitmap，沒事，你可以把bitmap就理解為一個二進制向量。

要用redis來實現(xiàn)布隆過濾器，我們需要自己設計映射函數(shù)，自己度量二進制向量的長度，這對我來說，無疑是一個不可能完成的任務，只能借助搜索引擎，下面直接放出代碼把。

public?class?RedisMain?{static?final int?expectedInsertions = 100;//要插入多少數(shù)據(jù)static?final double?fpp = 0.01;//期望的誤判率//bit數(shù)組長度private?static?long?numBits;//hash函數(shù)數(shù)量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 + "可能重復");
????????}
????}/**
?????* 根據(jù)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函數(shù)個數(shù)private?static?int?optimalNumOfHashFunctions(long?n, long?m)?{return?Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
????}//計算bit數(shù)組長度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可能重復本篇博客到這里就結束了，謝謝大家。寫作不易，堅持更難，如大家喜歡就幫忙推送給其他人！最近熱文：1、Tomcat 又爆出高危漏洞！8.5 ～ 10 中招…2、Spring Boot 干掉了 Maven 擁抱 Gradle！3、打破你的認知，數(shù)字除以0一定會崩潰嗎？4、寫了個全局變量的bug，被同事們打臉！5、Java 14 祭出神器，Lombok 被干掉了？6、為什么 Redis 單線程能達到百萬+QPS？7、Spring Boot 2.3 優(yōu)雅關閉新姿勢，真香！8、玩大發(fā)了，Tomcat 8.5 升級有坑…9、我天！xx.equals(null) 是什么騷操作？？10、Spring Boot 2.3.1 發(fā)布， 10 個新特性！掃碼關注Java技術棧公眾號干貨。

點擊「」獲取面試題大全～

總結

以上是生活随笔為你收集整理的java 布隆过滤器_牛逼哄哄的布隆过滤器，到底有什么用？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。