之前在網上看到過這么一段話👇

Data structures are nothing different. They are like the bookshelves of your application where you can organize your data. Different data structures will give you different facility and benefits. To properly use the power and accessibility of the data structures you need to know the trade-offs of using one.

這段話的大意就是：數據結構沒有什么不同，在應用程序中他們就像是可以組織數據的書架，不同的數據結構將為您提供不同的便利和好處，你需要仔細權衡自己的需求之后妥善的使用它們。布隆過濾器就是踐行這句話的代表，那么今天就和大家深入淺出的聊聊布隆過濾器（Bloom Filter）。

布隆過濾器（Bloom Filter）

還是老規矩，學習一個新知識之前，我們需要了解他的基本概念👇

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。

我們在布隆過濾器的基本概念中可以看到這么一句話，布隆過濾器可以用于檢索一個元素是否在一個集合中。有些小伙伴可能會問：我們直接用 HashMap 去檢索元素不就行了嗎，為什么還要用布隆過濾器呢？HashMap 確實可以幫助我們實現這個功能，而且 HashMap 通過一次運算就能確定某個元素的位置，也就可以幫助我們檢查某個元素是否在一個集合中。那么我們接下來再思考一個問題：如果這個元素集合中有十億個隨機數，那我們怎樣來判斷某個數是否存在呢？

如果元素集合中包含了十億個隨機數的話，那么首先就會給我們帶來空間上的問題，按一個隨機數占4個子節計算的話，這十億個隨機數就要占用將近4G的存儲空間，空間消耗就非常大，這時候就需要用到布隆過濾器（Bloom Filter）來幫助我們解決這個問題了。

🍓🍓布隆過濾器的基本思想🍓🍓

上面我們提到了元素集合中包含了十億個隨機數，如果直接存儲這十億個元素的話就需要占用很大的空間，所以我們肯定不能直接存儲元素。那么我們該怎樣存儲呢？存儲方式也是十分巧妙的，可以采用位數組的方式，不直接存儲元素，而是存儲元素是否存在的狀態，這樣就可以節約大量的存儲空間~（也不知道大神們是怎么想到這么巧妙的辦法的😂）

下面我們就一起看看布隆過濾器是怎么判斷一個元素是否在一個集合中的👇

🥝 ① 🥝 現在有一個集合和一個初始狀態都為0的位數組

🥝 ② 🥝 集合中的元素經過N個散列函數計算出元素在數組當中的位置，并且將數組中對應位置的0改成1

🥝 ③ 🥝 如果此時需要判斷元素X是否存在，那么元素X也會經過這N個散列函數的運算而得到數組中的若干個位置，如果得到的若干個位置中的值均為1，那么則證明元素X很可能存在與集合當中，反之則證明元素X一定不存在于集合當中。如下圖所示，此時元素X經過N個散列元素計算出的位置上所存儲的值不都是1，那么就證明元素X不存在集合中。

🍓🍓布隆過濾器的特性🍓🍓

在上面我們講到了布隆過濾器的思想，在第③點中有這樣一句話：如果得到的若干個位置中的值均為1，那么則證明元素X 很可能 存在與集合當中。為什么說全都是1的情況是很可能存在，而不是一定存在呢？這就和哈希函數的特點有關系了...

我們都知道哈希函數是可以將任意大小的輸入數據轉換成特定大小的輸出數據的函數（轉換后的數據稱為哈希值），哈希函數還有以下兩個特點：

• 如果根據同一個哈希函數得到的哈希值不同，那么這兩個哈希值的原始輸入值肯定不同。
• 如果根據同一個哈希函數得到的兩個哈希值相等，兩個哈希值的原始輸入值有可能相等，有可能不相等。

這就類似于 Java 中兩個對象的 HashCode 相等，但是對象本身不一定相等的道理。說白了，通過散列函數計算后得到位數組上映射點的值全都是1，不一定是要查詢的這個變量之前存進來時設置的，也有可能是其他元素映射的點。這也就引出了布隆過濾器的一個特性：存在一定的誤判。

在英雄聯盟里，你可以完全信任布隆，但是寫代碼時還是得提防著點😂

那么我們能不能刪除位數組中的元素呢？很顯然是不行的，因為在位數組上的同一個點有可能有多個輸入值映射，如果刪除了會影響布隆過濾器里其他元素的判斷結果。這也就是布隆過濾器的另一個特性：不能刪除布隆過濾器里的元素。

所以我們就可以總結出布隆過濾器的優缺點👇

🍎優點🍎：在空間和時間方面，都有著巨大的優勢。因為不是存完整的數據，是一個二進制向量，能節省大量的內存空間，時間復雜度方面，由于計算時是根據散列函數計算查詢的，那么假設有N個散列函數，那么時間復雜度就是O(N)；同時在存儲元素時存儲的不是元素本身，而是二進制向量，所以在一些對保密性要求嚴格的場景有一定優勢。

🍌缺點🍌：存在一定的誤判（存進布隆過濾器里的元素越多，誤判率越高）；不能刪除布隆過濾器里的元素，隨著使用的時間越來越長，因為不能刪除，存進里面的元素越來越多，導致占用內存越來越多，誤判率越來越高，最后不得不重置。

🍓🍓布隆過濾器的應用🍓🍓

我們都聽說過“緩存穿透”，那我們應該如何解決緩存穿透呢？沒錯，就是通過布隆過濾器來解決這個問題💪。

緩存穿透的問題主要是因為傳進來的 Key 值在 Redis 中是不存在的，那么就會直接打在數據庫上，從而增大數據庫的壓力。針對這種情況，可以在 Redis 前加上布隆過濾器，預先把數據庫中的數據加入到布隆過濾器中，在查詢 Redis 之前先通過布隆過濾器判斷 Key 值是否存在，如果不存在就直接返回，如果 Key 值存在的話，則按照原來的流程繼續執行。

解決緩存穿透利用的就是布隆過濾器判斷結果為不存在的話就一定不存在這一個特點，但是由于布隆過濾器有一定的誤判，所以并不能說完全解決緩存穿透，但是能很大程度緩解緩存穿透的問題。

🍓🍓模擬實現布隆過濾器🍓🍓

最后貼上一段代碼，來模擬實現一下布隆過濾器👇

import java.util.BitSet;/*** @description: MyBloomFilter* @author: 莊霸.liziye* @create: 2022-04-01 16:50**/
public class MyBloomFilter {/*** 一個長度為10億的比特位*/private static final int DEFAULT_SIZE = 256 << 22;/*** 為了降低錯誤率，使用加法hash算法，所以定義一個8個元素的質數數組*/private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};/*** 相當于構建8個不同的hash算法*/private static HashFunction[] functions = new HashFunction[seeds.length];/*** 初始化布隆過濾器的bitmap,即位數組*/private static BitSet bitset = new BitSet(DEFAULT_SIZE);/*** 添加數據** @param value 需要加入的值*/public static void add(String value) {if (value != null) {for (HashFunction f : functions) {//計算 hash 值并修改 bitmap 中相應位置為 truebitset.set(f.hash(value), true);}}}/*** 判斷相應元素是否存在* @param value 需要判斷的元素* @return 結果*/public static boolean contains(String value) {if (value == null) {return false;}boolean ret = true;for (HashFunction f : functions) {ret = bitset.get(f.hash(value));//一個 hash 函數返回 false 則跳出循環if (!ret) {break;}}return ret;}/*** 測試*/public static void main(String[] args) {for (int i = 0; i < seeds.length; i++) {functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);}//添加1億個元素for (int i = 0; i < 100000000; i++) {add(String.valueOf(i));}String id = "123456789";add(id);System.out.println("元素 123456789 是否存在：" + contains(id));System.out.println("元素 234567890 是否存在：" + contains("234567890"));}
}class HashFunction {private int size;private int seed;public HashFunction(int size, int seed) {this.size = size;this.seed = seed;}public int hash(String value) {int result = 0;int len = value.length();for (int i = 0; i < len; i++) {result = seed * result + value.charAt(i);}int r = (size - 1) & result;return (size - 1) & result;}
}復制代碼

作者：不肯過江東丶
鏈接：https://juejin.cn/post/7083294020323000356
來源：稀土掘金
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

---------------------
作者：栗少
來源：CSDN
原文：https://blog.csdn.net/weixin_38556197/article/details/124111236
版權聲明：本文為作者原創文章，轉載請附上博文鏈接！
內容解析By：CSDN,CNBLOG博客文章一鍵轉載插件