布隆(Bloom Filter)过滤器——全面讲解，发起收藏

这心不属于我

本文已支录于专栏

❤️《Redis之年夜厂必备妙技包》❤️

欢迎列位存眷、三连专主的文章及专栏，齐套Redis进修材料，年夜厂必备妙技！

---

 目次
1、甚么是布隆过滤器
2、布隆过滤器的利用场景
3、布隆过滤器的道理
3.1 数据构造
3.2 空间计较
3.3 增长元素
3.4 查询元素
3.5 修正元素
3.6 删除元素
4、Redis散成布隆过滤器
4.1 版本请求
4.2 装置&编译
4.3 Redis散成
5、Redis中布隆过滤器指令利用
5.1 bf.add
5.2 bf.madd
5.3 bf.exists
5.3 bf.mexists
6、Java当地内乱存利用布隆过滤器
6.1 引进pom依靠
6.2 编写测试代码
6.3 测试结果
6.4 参数阐明
6.5 fpp&expectedInsertions
7、Java散成Redis利用布隆过滤器
7.1 引进pom依靠
7.2 编写测试代码
7.3 测试结果

---

1、甚么是布隆过滤器

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实践上是一个很少的两进造背量战一系列随机映照函数。布隆过滤器能够用于检索一个元素能否正在一个汇合中。它的长处是空间服从战查询工夫皆比普通的算法要好的多，缺陷是有必然的误辨认率战删除艰难。
​
上里那句引见比较片面的形貌了甚么是布隆过滤器，假如仍是没有太好了解的话，就能够把布隆过滤器了解为一个set汇合，我们能够经由过程add往内里增加元素，经由过程contains去判定能否包含某个元素。因为本文报告布隆过滤器时会结合Redis来说解，因而类比为Redis中的Set数据构造会比较好了解，并且Redis中的布隆过滤器利用的指令取Set汇合十分相似（后绝会讲到）。
​
进修布隆过滤器之前有须要先聊下它的劣缺陷，由于好的工具我们才念要嘛！
布隆过滤器的长处：

• 工夫庞大度低，增长战查询元素的工夫庞大为O(N)，（N为哈希函数的个数，凡是状况比较小）
  
• 失密性强，布隆过滤器没有存储元素自己
  
• 存储空间小，假如许可存正在必然的误判，布隆过滤器长短常节流空间的（比拟其他数据构造如Set汇合）
  

布隆过滤器的缺陷：

• 有面必然的误判率，可是能够经由过程调解参数去消沉
  
• 没法获得元素自己
  
• 很易删除元素
  

2、布隆过滤器的利用场景

布隆过滤器能够报告我们 “某样工具必然没有存正在大概大要存正在”，也便是道布隆过滤器道那个数没有存正在则必然没有存，布隆过滤器道那个数存正在大要没有存正在（误判，后绝会讲），**利用那个判定能否存正在的特性能够做许多风趣的工作。

• 处理Redis缓存脱透成绩（口试重面）
  
• 邮件过滤，利用布隆过滤器去做邮件乌名单过滤
  
• 对爬虫网址停止过滤，爬过的没有再爬
  
• 处理消息保举过的没有再保举(相似抖音刷过的往下滑动没有再刷到)
  
• HBase\RocksDB\LevelDB等数据库内乱置布隆过滤器，用于判定数据能否存正在，能够削减数据库的IO恳求
  

3、布隆过滤器的道理

3.1 数据构造

布隆过滤器它实践上是一个很少的两进造背量战一系列随机映照函数。以Redis中的布隆过滤器完成为例，Redis中的布隆过滤器底层是一个年夜型位数组（两进造数组）+多个无偏偏hash函数。
一个年夜型位数组（两进造数组）：

多个无偏偏hash函数：
无偏偏hash函数便是能把元素的hash值计较的比较平均的hash函数，能使得计较后的元素下标比较平均的映照到位数组中。
以下便是一个简朴的布隆过滤器表示图，此中k1、k2代表增长的元素，a、b、c即为无偏偏hash函数，最基层则为两进造数组。

3.2 空间计较

正在布隆过滤器增长元素之前，起首需求初初化布隆过滤器的空间，也便是上里道的两进造数组，除此以外借需求计较无偏偏hash函数的个数。布隆过滤器供给了两个参数，别离是估计参加元素的巨细n，运转的毛病率f。布隆过滤器中有算法按照那两个参数会计算出两进造数组的巨细l，和无偏偏hash函数的个数k。
它们之间的干系比较简朴：

• 毛病率越低，位数组越少，控件占用较年夜
  
• 毛病率越低，无偏偏hash函数越多，计较耗时较少
  

以下地点是一个免费的正在线布隆过滤器正在线计较的网址：

  https://krisives.github.io/bloom-calculator/

3.3 增长元素

往布隆过滤器增长元素，增加的key需求按照k个无偏偏hash函数计较获得多个hash值，然后对数组少度停止与模获得数组下标的地位，然后将对应数组下标的地位的值置为1

• 经由过程k个无偏偏hash函数计较获得k个hash值
  
• 顺次与模数组少度，获得数组索引
  
• 将计较获得的数组索引下标地位数据修正为1
  

比方，key = Liziba，无偏偏hash函数的个数k=3，别离为hash1、hash2、hash3。三个hash函数计较后获得三个数组下标值，并将其值修正为1.
如图所示：

3.4 查询元素

布隆过滤器最年夜的用途便正在于判定某样工具必然没有存正在大概大要存正在，而那个便是查询元素的结果。其查询元素的历程以下：

• 经由过程k个无偏偏hash函数计较获得k个hash值
  
• 顺次与模数组少度，获得数组索引
  
• 判定索引处的值能否局部为1，假如局部为1则存正在（这类存正在大要是误判），假如存正在一个0则肯定没有存正在
  

闭于误判，实在十分好了解，hash函数正在怎样好，也没法完整避免hash抵触，也便是道大要会存正在多个元素计较的hash值是不异的，那末它们与模数组少度后的到的数组索引也是不异的，那便是误判的缘故原由。比方李子捌战李子柒的hash值与模后获得的数组索引皆是1，但实在那里只要李子捌，假如此时判定李子柒正在没有正在那里，误判便呈现啦！因而布隆过滤器最年夜的缺陷误判只需明白其判定元素能否存正在的道理便很简单大白了！
3.5 修正元素

无
​
3.6 删除元素

布隆过滤器对元素的删除没有太撑持，今朝有一些变形的特定布隆过滤器撑持元素的删除！闭于为何对删除没有太撑持，实在也十分好了解，hash抵触一定存正在，删除必定是很灾难的！
​
4、Redis散成布隆过滤器

4.1 版本请求

• 保举版本6.x，最低4.x版本，能够经由过程以下号令检察版本：
  

1. redis-server -v

复造代码

• 插件装置，网上年夜部门保举v1.1.1，文章写的时分v2.2.6曾经是release版本了，用户本人挑选，地点齐鄙人里(2.2.6民网引见道是1.0版本的保护版本，假如没有念利用新的功用，无需晋级！)
  

v1.1.1

  https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz

v2.2.6

  https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz

4.2 装置&编译

以下装置局部正在指定目次下完成，能够挑选一个契合的同一目次停止硬件装置战办理。
4.2.1 下载插件紧缩包

1. wget https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz

复造代码

4.2.2 解压

1. tar -zxvf v2.2.6.tar.gz

复造代码

4.2.3 编译插件

1. cd RedisBloom-2.2.6/
2. make

复造代码

编译胜利后看到redisbloom.so文件便可
​
4.3 Redis散成

4.3.1 Redis设置文件修正

• 正在redis.conf设置文件中参加如RedisBloom的redisbloom.so文件的地点
  
• 假如是散群则每一个设置文件中皆需求参加redisbloom.so文件的地点
  
• 增加完成后需求重启redis
  

1. loadmodule /usr/local/soft/RedisBloom-2.2.6/redisbloom.so

复造代码

redis.conf设置文件中预置了loadmodule的设置项，我们能够间接正在那里修正，后绝修正会愈加便利。

保留退出后必然要记得重启Redis！
保留退出后必然要记得重启Redis！
保留退出后必然要记得重启Redis！

4.3.2 测试能否胜利
Redis散成布隆过滤器的次要指令以下：

• bf.add 增加一个元素
  
• bf.exists 判定一个元素能否存正在
  
• bf.madd 增加多个元素
  
• bf.mexists 判定多个元素能否存正在
  

毗邻客户端停止测试，假如指令有用则证实散成胜利

假如呈现以下状况(error) ERR unknown command ，能够经由过程以下办法查抄：

• SHUTDOWN Redis真例，再重启真例，再次测试
  
• 查抄设置文件能否设置redisbloom.so文件地点准确
  
• 查抄Redis的版本能否太低
  

5、Redis中布隆过滤器指令利用

5.1 bf.add

bf.add暗示增加单个元素，增加胜利返回1

1. 127.0.0.1:6379> bf.add name liziba
2. (integer) 1

复造代码

5.2 bf.madd

bf.madd暗示增加多个元素

1. 127.0.0.1:6379> bf.madd name liziqi lizijiu lizishi
2. 1) (integer) 1
3. 2) (integer) 1
4. 3) (integer) 1

复造代码

5.3 bf.exists

bf.exists暗示判定元素能否存正在，存正在则返回1，没有存正在返回0

1. 127.0.0.1:6379> bf.mexists name liziba
2. 1) (integer) 1

复造代码

5.3 bf.mexists

bf.mexists暗示判定多个元素能否存正在，存正在的返回1，没有存正在的返回0

1. 127.0.0.1:6379> bf.mexists name liziqi lizijiu liziliu
2. 1) (integer) 1
3. 2) (integer) 1
4. 3) (integer) 0

复造代码

6、Java当地内乱存利用布隆过滤器

利用布隆过滤器的方法有许多，另有许多年夜佬本人脚写的，我那里利用的是谷歌guava包中完成的布隆过滤器，这类方法的布隆过滤器是正在当地内乱存中完成。
6.1 引进pom依靠

1. <dependency>
2.   <groupId>com.谷歌.guava</groupId>
3.   <artifactId>guava</artifactId>
4.   <version>29.0-jre</version>
5. </dependency>

复造代码

6.2 编写测试代码

[code]package com.lizba.bf;import com.谷歌.common.hash.BloomFilter;import com.谷歌.common.hash.Funnels;/** *  *        布隆过滤器测试代码 * 
 * * @Author: Liziba * @Date: 2021/8/29 14:51 */public class BloomFilterTest {    /** 估计插进的数据 */    private static Integer expectedInsertions = 10000000;    /** 误判率 */    private static Double fpp = 0.01;    /** 布隆过滤器 */    private static BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);    public static void main(String[] args) {        // 插进 1万万数据        for (int i = 0; i