布隆过滤器原理(有眼睛就能看懂)

简介: 作用嘛就是用来过滤非法key,避免缓存穿透(请求直接打到数据库),布隆过滤器底层用的是位数组,不仅节省空间,性能也嘎嘎猛,而且占用内存不会随着使用变大

作用嘛就是用来过滤非法key,避免缓存穿透(请求直接打到数据库),布隆过滤器底层用的是位数组,不仅节省空间,性能也嘎嘎猛,而且占用内存不会随着使用变大

先贴demo后BB

public class MyBloomFilter {
    //你的布隆过滤器容量
    private static final int DEFAULT_SIZE = 2 << 28;
    //bit数组,用来存放key
    private static BitSet bitSet = new BitSet(DEFAULT_SIZE);
    //后面hash函数会用到,用来生成不同的hash值,可随意设置,别问我为什么这么多8,图个吉利
    private static final int[] ints = {1, 6, 16, 38, 58, 68};
    //add方法,计算出key的hash值,并将对应下标置为true
    public void add(Object key) {
        Arrays.stream(ints).forEach(i -> bitSet.set(hash(key, i)));
    }
    //判断key是否存在,true不一定说明key存在,但是false一定说明不存在
    public boolean isContain(Object key) {
         boolean result = true;
        for (int i : ints) {
          //短路与,只要有一个bit位为false,则返回false
            result = result && bitSet.get(hash(key, i));
        }
        return result;
    }
    //hash函数,借鉴了hashmap的扰动算法,强烈建议大家把这个hash算法看懂,这个设计真的牛皮加闪电
    private int hash(Object key, int i) {
        int h;
        return key == null ? 0 : (i * (DEFAULT_SIZE - 1) & ((h = key.hashCode()) ^ (h >>> 16)));
    }
}

测试

    public static void main(String[] args) {
        MyNewBloomFilter myNewBloomFilter = new MyNewBloomFilter();
        myNewBloomFilter.add("张学友");
        myNewBloomFilter.add("郭德纲");
        myNewBloomFilter.add("蔡徐鸡");
        myNewBloomFilter.add(666);
        System.out.println(myNewBloomFilter.isContain("张学友"));//true
        System.out.println(myNewBloomFilter.isContain("张学友 "));//false
        System.out.println(myNewBloomFilter.isContain("张学友1"));//false
        System.out.println(myNewBloomFilter.isContain("郭德纲"));//true
        System.out.println(myNewBloomFilter.isContain("蔡徐老母鸡"));//false
        System.out.println(myNewBloomFilter.isContain(666));//true
        System.out.println(myNewBloomFilter.isContain(888));//false
    }

原理


通过对比hash算法计算出来的下标,注意,我们是对比一组,而不是只看一次,一次hash结果对应一个下标


把同一个key进行多次hash运算,将hash出来的下标放入数组,数组默认全为0,放入元素后该下标就为1,后面判断是否存在元素的时候也是进行同样次数的hash运算,看下结果对应的所有下标是否全为1,若全为1,则代表该key可能存在,若存在不为1的,则说明该key一定不存在;


默认位数组:[0,0,0,0,0,0]

比方说有个已知key的下标是0,2,5

对应位数组:[1,0,1,0,0,1]

判断某个未知key存不存在的时候,假设我们计算出来的下标是0,2,4

对应位数组:[1,0,1,0,1,0]

此时位数组内5对应下标值为0,而已知key位数组的5对应下标位1,说明这两个一定不是同一个key


相反,如果某个key计算出来的下标为[1,0,1,0,0,1],只能说这个key可能存在,因为这个位置可能是其它key计算出来的


如果对上面的hash算法有疑惑,请移步帮你真正理解hashCode和hash算法


demo复制可用,家里有条件的都在编译器上跑一跑,测一测


ok我话讲完


嘤嘤嘤~


相关文章
|
2月前
|
存储 数据采集 缓存
Bitmap 和 布隆过滤器傻傻分不清?你这不应该啊
大家好,我是小富。本文介绍了 Redis 的 Bitmap 和布隆过滤器的区别与关系,包括它们的底层原理、应用场景及优缺点。Bitmap 以 bit 为单位存储数据,适用于记录二值状态,如用户签到、在线状态等。布隆过滤器通过多个哈希函数优化哈希碰撞问题,适用于大规模数据的快速判断,如缓存穿透、邮箱黑名单过滤等。两者都能高效处理大数据量和高并发场景。
|
7月前
|
算法 搜索推荐 程序员
当“基本功”数据结构与算法被图形分解,要还不会就真的没办法了
数据结构与算法并不只是抽象的概念,掌握好的话可以写出更高效、运行得更快的代码,这对于如今盛行的网页和移动应用开发来说尤为重要。如果你最近一-次使用算法是在大学课堂上或求职面试时,那你应该还没见识到它的真正威力。
|
存储 缓存 NoSQL
通俗易懂理解——布隆过滤器
通俗易懂理解——布隆过滤器
143 0
|
消息中间件 存储 缓存
品味布隆过滤器的设计之美 上
品味布隆过滤器的设计之美 上
品味布隆过滤器的设计之美   上
|
数据采集 存储 缓存
一文读懂什么是布隆过滤器
一文读懂什么是布隆过滤器
202 0
|
存储 消息中间件 缓存
品味布隆过滤器的设计之美
布隆过滤器是一个精巧而且经典的数据结构。 你可能没想到: RocketMQ、 Hbase 、Cassandra 、LevelDB 、RocksDB 这些知名项目中都有布隆过滤器的身影。 对于后端程序员来讲,学习和理解布隆过滤器有很大的必要性。来吧,我们一起品味布隆过滤器的设计之美。
品味布隆过滤器的设计之美
|
数据采集 存储 Java
终于看明白布隆过滤器了
布隆过滤器不会出现第一种失误,只可能会有第二种类型的失误。但是布隆过滤器可以通过人为的设计,让第二种类型失误的触发率很低,低到万分之一。
274 0
终于看明白布隆过滤器了
|
存储 缓存 NoSQL
品味布隆过滤器的设计之美 下
品味布隆过滤器的设计之美 下
|
缓存 NoSQL JavaScript
通俗易懂讲布隆过滤器
通俗易懂讲布隆过滤器
|
算法 NoSQL Redis
关于跳表,这么解释你肯定能听懂
如何用 30s 给面试官讲清楚什么是跳表
125 0
关于跳表,这么解释你肯定能听懂