filter过滤器_不了解布隆过滤器？一文给你整的明明白白！
海量數(shù)據(jù)處理以及緩存穿透這兩個場景讓我認識了 布隆過濾器 ，我查閱了一些資料來了解它，但是很多現(xiàn)成資料并不滿足我的需求，所以就決定自己總結(jié)一篇關(guān)于布隆過濾器的文章。希望通過這篇文章讓更多人了解布隆過濾器，并且會實際去使用它！
下面我們將分為幾個方面來介紹布隆過濾器：
1.什么是布隆過濾器？
首先，我們需要了解布隆過濾器的概念。
布隆過濾器（Bloom Filter）是一個叫做 Bloom 的老哥于1970年提出的。我們可以把它看作由二進制向量（或者說位數(shù)組）和一系列隨機映射函數(shù)（哈希函數(shù)）兩部分組成的數(shù)據(jù)結(jié)構(gòu)。相比于我們平時常用的的 List、Map 、Set 等數(shù)據(jù)結(jié)構(gòu)，它占用空間更少并且效率更高，但是缺點是其返回的結(jié)果是概率性的，而不是非常準確的。理論情況下添加到集合中的元素越多，誤報的可能性就越大。并且，存放在布隆過濾器的數(shù)據(jù)不容易刪除。
位數(shù)組中的每個元素都只占用 1 bit ，并且每個元素只能是 0 或者 1。這樣申請一個 100w 個元素的位數(shù)組只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空間。
總結(jié)：一個名叫 Bloom 的人提出了一種來檢索元素是否在給定大集合中的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)是高效且性能很好的，但缺點是具有一定的錯誤識別率和刪除難度。并且，理論情況下，添加到集合中的元素越多，誤報的可能性就越大。
2.布隆過濾器的原理介紹
當一個元素加入布隆過濾器中的時候，會進行如下操作：
當我們需要判斷一個元素是否存在于布隆過濾器的時候，會進行如下操作：
舉個簡單的例子：
如圖所示，當字符串存儲要加入到布隆過濾器中時，該字符串首先由多個哈希函數(shù)生成不同的哈希值，然后在對應(yīng)的位數(shù)組的下表的元素設(shè)置為 1（當位數(shù)組初始化時 ，所有位置均為0）。當?shù)诙未鎯ο嗤址畷r，因為先前的對應(yīng)位置已設(shè)置為 1，所以很容易知道此值已經(jīng)存在（去重非常方便）。
如果我們需要判斷某個字符串是否在布隆過濾器中時，只需要對給定字符串再次進行相同的哈希計算，得到值之后判斷位數(shù)組中的每個元素是否都為 1，如果值都為 1，那么說明這個值在布隆過濾器中，如果存在一個值不為 1，說明該元素不在布隆過濾器中。
不同的字符串可能哈希出來的位置相同，這種情況我們可以適當增加位數(shù)組大小或者調(diào)整我們的哈希函數(shù)。
綜上，我們可以得出：布隆過濾器說某個元素存在，小概率會誤判。布隆過濾器說某個元素不在，那么這個元素一定不在。
3.布隆過濾器使用場景
4.通過 Java 編程手動實現(xiàn)布隆過濾器
我們上面已經(jīng)說了布隆過濾器的原理，知道了布隆過濾器的原理之后就可以自己手動實現(xiàn)一個了。
如果你想要手動實現(xiàn)一個的話，你需要：
下面給出一個我覺得寫的還算不錯的代碼（參考網(wǎng)上已有代碼改進得到，對于所有類型對象皆適用）：
import java.util.BitSet;public class MyBloomFilter {/*** 位數(shù)組的大小*/private static final int DEFAULT_SIZE = 2 << 24;/*** 通過這個數(shù)組可以創(chuàng)建 6 個不同的哈希函數(shù)*/private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};/*** 位數(shù)組。數(shù)組中的元素只能是 0 或者 1*/private BitSet bits = new BitSet(DEFAULT_SIZE);/*** 存放包含 hash 函數(shù)的類的數(shù)組*/private SimpleHash[] func = new SimpleHash[SEEDS.length];/*** 初始化多個包含 hash 函數(shù)的類的數(shù)組，每個類中的 hash 函數(shù)都不一樣*/public MyBloomFilter() {// 初始化多個不同的 Hash 函數(shù)for (int i = 0; i < SEEDS.length; i++) {func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);}}/*** 添加元素到位數(shù)組*/public void add(Object value) {for (SimpleHash f : func) {bits.set(f.hash(value), true);}}/*** 判斷指定元素是否存在于位數(shù)組*/public boolean contains(Object value) {boolean ret = true;for (SimpleHash f : func) {ret = ret && bits.get(f.hash(value));}return ret;}/*** 靜態(tài)內(nèi)部類。用于 hash 操作！*/public static class SimpleHash {private int cap;private int seed;public SimpleHash(int cap, int seed) {this.cap = cap;this.seed = seed;}/*** 計算 hash 值*/public int hash(Object value) {int h;return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));}} }測試：
String value1 = "https://javaguide.cn/";String value2 = "https://github.com/Snailclimb";MyBloomFilter filter = new MyBloomFilter();System.out.println(filter.contains(value1));System.out.println(filter.contains(value2));filter.add(value1);filter.add(value2);System.out.println(filter.contains(value1));System.out.println(filter.contains(value2));Output:
false false true true測試：
Integer value1 = 13423;Integer value2 = 22131;MyBloomFilter filter = new MyBloomFilter();System.out.println(filter.contains(value1));System.out.println(filter.contains(value2));filter.add(value1);filter.add(value2);System.out.println(filter.contains(value1));System.out.println(filter.contains(value2));Output:
false false true true5.利用Google開源的 Guava中自帶的布隆過濾器
自己實現(xiàn)的目的主要是為了讓自己搞懂布隆過濾器的原理，Guava 中布隆過濾器的實現(xiàn)算是比較權(quán)威的，所以實際項目中我們不需要手動實現(xiàn)一個布隆過濾器。
首先我們需要在項目中引入 Guava 的依賴：
<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>28.0-jre</version></dependency>實際使用如下：
我們創(chuàng)建了一個最多存放 最多 1500個整數(shù)的布隆過濾器，并且我們可以容忍誤判的概率為百分之（0.01）
// 創(chuàng)建布隆過濾器對象BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(),1500,0.01);// 判斷指定元素是否存在System.out.println(filter.mightContain(1));System.out.println(filter.mightContain(2));// 將元素添加進布隆過濾器filter.put(1);filter.put(2);System.out.println(filter.mightContain(1));System.out.println(filter.mightContain(2));在我們的示例中，當mightContain（） 方法返回true時，我們可以99％確定該元素在過濾器中，當過濾器返回false時，我們可以100％確定該元素不存在于過濾器中。
Guava 提供的布隆過濾器的實現(xiàn)還是很不錯的（想要詳細了解的可以看一下它的源碼實現(xiàn)），但是它有一個重大的缺陷就是只能單機使用（另外，容量擴展也不容易），而現(xiàn)在互聯(lián)網(wǎng)一般都是分布式的場景。為了解決這個問題，我們就需要用到 Redis 中的布隆過濾器了。
6.Redis 中的布隆過濾器
6.1介紹
Redis v4.0 之后有了 Module（模塊/插件） 功能，Redis Modules 讓 Redis 可以使用外部模塊擴展其功能 。布隆過濾器就是其中的 Module。詳情可以查看 Redis 官方對 Redis Modules 的介紹 ：https://redis.io/modules
另外，官網(wǎng)推薦了一個 RedisBloom 作為 Redis 布隆過濾器的 Module,地址：https://github.com/RedisBloom/RedisBloom. 其他還有：
- redis-lua-scaling-bloom-filter （lua 腳本實現(xiàn)）：https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter
- pyreBloom（Python中的快速Redis 布隆過濾器） ：https://github.com/seomoz/pyreBloom
- 《2020最新Java基礎(chǔ)精講視頻教程和學習路線！》
- …
RedisBloom 提供了多種語言的客戶端支持，包括：Python、Java、JavaScript 和 PHP。
6.2使用Docker安裝
如果我們需要體驗 Redis 中的布隆過濾器非常簡單，通過 Docker 就可以了！我們直接在 Google 搜索docker redis bloomfilter 然后在排除廣告的第一條搜素結(jié)果就找到了我們想要的答案（這是我平常解決問題的一種方式，分享一下），具體地址：https://hub.docker.com/r/redislabs/rebloom/ （介紹的很詳細 ）。
具體操作如下：
? ~ docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest ? ~ docker exec -it redis-redisbloom bash root@21396d02c252:/data# redis-cli 127.0.0.1:6379>6.3常用命令一覽
注意： key:布隆過濾器的名稱，item : 添加的元素。另外，BF.RESERVE 命令需要單獨介紹一下：
這個命令的格式如下：
BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]。
下面簡單介紹一下每個參數(shù)的具體含義：
可選參數(shù)：
- expansion：如果創(chuàng)建了一個新的子過濾器，則其大小將是當前過濾器的大小乘以expansion。默認擴展值為2。這意味著每個后續(xù)子過濾器將是前一個子過濾器的兩倍。
6.4實際使用
127.0.0.1:6379> BF.ADD myFilter java (integer) 1 127.0.0.1:6379> BF.ADD myFilter javaguide (integer) 1 127.0.0.1:6379> BF.EXISTS myFilter java (integer) 1 127.0.0.1:6379> BF.EXISTS myFilter javaguide (integer) 1 127.0.0.1:6379> BF.EXISTS myFilter github (integer) 0作者：Snailclimb鏈接：不了解布隆過濾器？一文給你整的明明白白！
來源：github 《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀
總結(jié)
以上是生活随笔為你收集整理的filter过滤器_不了解布隆过滤器？一文给你整的明明白白！的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 顺丰快递单号的规律_顺丰快递单号查询跟踪
- 下一篇： maven deploy plugin_