布隆过滤器

布隆过滤器

特点

  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博客

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,335评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,895评论 3 387
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,766评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,918评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,042评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,169评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,219评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,976评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,393评论 1 304
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,711评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,876评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,562评论 4 336
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,193评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,903评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,142评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,699评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,764评论 2 351

推荐阅读更多精彩内容

  • 什么是 BloomFilter 布隆过滤器(英语:Bloom Filter)是 1970 年由布隆提出的。它实际上...
    JavaKeeper_海星阅读 743评论 0 0
  • 一、什么是布隆过滤器? 布隆过滤器可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着...
    王知无阅读 1,395评论 1 8
  • 什么是 BloomFilter 布隆过滤器(英语:Bloom Filter)是 1970 年由布隆提出的。它实际上...
    AnyL8023阅读 453评论 0 0
  • 表情是什么,我认为表情就是表现出来的情绪。表情可以传达很多信息。高兴了当然就笑了,难过就哭了。两者是相互影响密不可...
    Persistenc_6aea阅读 124,604评论 2 7
  • 16宿命:用概率思维提高你的胜算 以前的我是风险厌恶者,不喜欢去冒险,但是人生放弃了冒险,也就放弃了无数的可能。 ...
    yichen大刀阅读 6,042评论 0 4