布隆过滤器

布隆过滤器

特点

1. 判断key不存在，就是百分百不存在

2. 判断key存在，则有一定的误判几率，如果hash的越分散，位数组容量越大，那么误判概率越小

原理

1. 首先有一个位数组（该数组中只能存放0和1），位数组中每个元素的初始值都为0

2. 然后准备多个hash函数，目的是增加分散度，避免碰撞概率过大

3. 每一个hash函数都对key进行hash算法得到其在位数组中的位置，如果我设定了6个哈希函数，那么我就要进行6次hash计算，得到6个位数组中的位置，在对应位数组中的位置，把元素值设为1

4. 如何判断一个值是否在布隆过滤器（也就是位数组中呢）中，那么就对该值进行存储时一样的hash算法，得到对应的6个位数组中位置，然后取出对应位置的元素，判断该元素是否为1，如果有一个不为1，那么该值肯定不在布隆过滤器中，如果都为1，那么可能在布隆过滤器中（不能保证百分百存在），因为不同字符串hash出来的位置可能是相同的，这种情况就可以适当调整位数组的大小或者调整我们的hash哈数来减少碰撞的概率

java方式实现

import java.util.BitSet; 
public class MyBloomFilter {
 //位数组的容量
 private static final int DEFAULT_SIZE = 2 << 24;
 /*** 通过这个数组可以创建 6 个不同的哈希函数 */ 
 private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};    /*** 位数组。数组中的元素只能是 0 或者 1 */ 
 private BitSet bits = new BitSet(DEFAULT_SIZE); 
 /*** 存放包含 hash 函数的类的数组，即该数组中放的都是hash哈数 */
 private SimpleHash[] func = new SimpleHash[SEEDS.length]; 
 /*** 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样 */ public MyBloomFilter() { 
 // 初始化多个不同的 Hash 函数 
 for (int i = 0; i < SEEDS.length; i++) { 
 func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]); 
 } 
 }
 /*** 添加元素到位数组 */ 
 public void add(Object value) { 
 for (SimpleHash f : func) {
 bits.set(f.hash(value), true); 
   } 
 }
 /*** 判断指定元素是否存在于位数组 */ 
 public boolean contains(Object value) {
 boolean ret = true; 
 for (SimpleHash f : func) { 
 ret = ret && bits.get(f.hash(value)); 
 }
 return ret; 
 }
 /*** 静态内部类。用于 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))); 
    } 
   } 
}

谷歌开源Guava的布隆过滤器（缺陷就是只能单机使用，且容量扩展不容易）

1. 导入依赖

    <groupId>com.google.guava</groupId> 
    <artifactId>guava</artifactId> 
    <version>28.0-jre</version> 
   </dependency></pre>
   

2. 实现(创建一个最多存放 1500个整数的布隆过滤器,并且我们可以容忍误判的概率为百分之0.01)

    // 创建布隆过滤器对象 
    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));

Redis中的布隆过滤器

• 介绍

  1. Redis4.0之后有了Module（模块/插件） 功能，Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 ：https://redis.io/modules。另外，官网推荐了一个RedisBloom 作为 Redis 布隆过滤器的 Module,地址：https://github.com/RedisBloom/RedisBloom。其他还有：redis-lua-scaling-bloom-filter （lua 脚本实现）：https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter
     pyreBloom（Python中的快速Redis 布隆过滤器） ：https://github.com/seomoz/pyreBloom
     ......
     RedisBloom 提供了多种语言的客户端支持，包括：Python、Java、JavaScript 和 PHP。

• 使用docker安装

  1. 如果我们需要体验 Redis 中的布隆过滤器非常简单，通过 Docker 就可以了！我们直接在 Google 搜索

     docker redis bloomfifilter 然后在排除广告的第一条搜素结果就找到了我们想要的答案（这是我平常解

     决问题的一种方式，分享一下），具体地址：https://hub.docker.com/r/redislabs/rebloom/ （介绍的

     很详细 ）。

  2. 命令操作：

     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>
  

  • 常用命令一览(注意： key:布隆过滤器的名称，item : 添加的元素)

    1. BF.ADD ：将元素添加到布隆过滤器中，如果该过滤器尚不存在，则创建该过滤器。格式：BF.ADD {key} {item} 。

    2. BF.MADD : 将一个或多个元素添加到“布隆过滤器”中，并创建一个尚不存在的过滤器。该命令的操作方式 BF.ADD 与之相同，只不过它允许多个输入并返回多个值。格式： BF.MADD {key} {item} [item ...] 。

    3. BF.EXISTS : 确定元素是否在布隆过滤器中存在。格式： BF.EXISTS {key} {item} 。

    4. BF.MEXISTS ： 确定一个或者多个元素是否在布隆过滤器中存在格式： BF.MEXISTS {key} {item} [item ...] 。

  • BF.RESERVE 命令:BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] 。

    1. key：布隆过滤器的名称

    2. error_rate :误报的期望概率。这应该是介于0到1之间的十进制值。例如，对于期望的误报率0.1％（1000中为1），error_rate应该设置为0.001。该数字越接近零，则每个项目的内存消耗越大，并且每个操作的CPU使用率越高。

    3. capacity: 过滤器的容量。当实际存储的元素个数超过这个值之后，性能将开始下降。实际的降级将取决于超出限制的程度。随着过滤器元素数量呈指数增长，性能将线性下降。

    4. 可选参数：expansion：如果创建了一个新的子过滤器，则其大小将是当前过滤器的大小乘以 expansion 。默认扩展值为2。这意味着每个后续子过滤器将是前一个子过滤器的两倍。

  • 使用案例

      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</pre>
  

解决redis缓存穿透问题：Redis缓存雪崩和缓存穿透解决方案-布隆过滤器（总结)_java_liuyuan的博客-CSDN博客