布隆过滤器原理及实现

概述

在缓存穿透的解决方案中，有个方案是使用布隆过滤器,可以把它理解成一个集合类型的数据结构，用来判断一个数据是否在这个集合中存在。那么很多人会想用HashSet等类型的数据结构不可以么？HashSet和布隆过滤器存的量级不同,布隆过滤器可以存大量的数据。何为大量？HashSet、HashMap这些类型所存的数据量，跟你分配给jvm的内存空间有关，如果太大了超出了怎么办？那就可以考虑使用布隆过滤器。

布隆过滤器

布隆过滤器是一个叫“布隆”的人提出的。我们可以把它看作由二进制向量（或者说位数组）和一系列随机映射函数（哈希函数）两部分组成的数据结构。如下图:

长度为16的布隆过滤器

可以看出，它其实就是一个位数组，位数组中的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1。这样申请一个 100w 个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空间。

布隆过滤器的原理

当一个元素加入布隆过滤器中的时候，会进行如下操作:

使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）
根据得到的哈希值，在位数组中把对应下标的值置为 1

当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作:

对该元素进行相同的哈希计算，得到哈希值（有几个哈希函数得到几个哈希值）
然后通过哈希值查找在位数组中的位置，判断位数组中的该位置的元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中

布隆过滤器的原理

如上图所示，当字符串存储要加入到布隆过滤器中时，该字符串首先由多个哈希函数生成不同的哈希值，然后在对应的位数组的下表的元素设置为 1（当位数组初始化时，所有位置均为0）。当第二次存储相同字符串时，因为先前的对应位置已设置为1，所以很容易知道此值已经存在（去重非常方便）。

布隆过滤器使用场景

判断给定数据是否存在：除了文章开头提到的缓存穿透外，还有比如判断一个数字是否在于包含大量数字的数字集中（数字集很大，5亿以上！）、邮箱的垃圾邮件过滤、黑名单功能、车辆套牌判断等等
去重：比如消息队列的消息是否重复消费、接口幂等判断等等

布隆过滤器的实现

Google开源的 Guava中自带的布隆过滤器BloomFilter

首先,需要在pom文件中加入guava依赖

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

代码中使用,这里就直接在一个SpringBoot项目中使用了,创建BloomFilterController类

/**
 * @ClassName BloomFilterController
 * @Description //布隆过滤器测试
 * @Author singleZhang
 * @Email 405780096@qq.com
 * @Date 2020/12/25 0025 上午 10:44
 **/
@RestController
@RequestMapping("/bloom")
public class BloomFilterController {
    private final static BloomFilter<Integer> filter = BloomFilter.create(
            Funnels.integerFunnel(),
            1500,
            0.01);
    static {
        System.out.println("布隆过滤器初始化");
        for (Integer i=0;i<10;i++) {
            filter.put(i);
        }
    }

    @GetMapping("/test")
    public void test(){

            // 判断指定元素是否存在
            System.out.println(filter.mightContain(1));
            System.out.println(filter.mightContain(2));
            // 将元素添加进布隆过滤器
            boolean x = filter.put(1);
            boolean y = filter.put(2);
            System.out.println("x=" + x);
            System.out.println("y="+ y);
    }
}

执行结果如下

布隆过滤器判断结果

当 mightContain() 方法返回 true 时，我们可以 99％确定该元素在过滤器中，当过滤器返回 false 时，我们可以 100％确定该元素不存在于过滤器中。
具体实现可以阅读以下Guava中BloomFilter类的源码,来加深印象。
※注:Guava的布隆过滤器有一个重大的缺陷就是只能单机使用（另外，容量扩展也不容易），而现在互联网一般都是分布式的场景

通过java代码,自定义实现布隆过滤器

如果你想要手动实现一个的话，你需要：

一个合适大小的位数组保存数据
几个不同的哈希函数
添加元素到位数组（布隆过滤器）的方法实现
判断给定元素是否存在于位数组（布隆过滤器）的方法实现。

创建一个布隆过滤器类BloomFilter

package com.zhxin.threadLab.bloomfilter;

import java.util.BitSet;

/**
 * @ClassName BloomFilter
 * @Description //简单布隆过滤器实现
 * @Author singleZhang
 * @Email 405780096@qq.com
 * @Date 2020/12/25 0025 上午 11:15
 **/
public class BloomFilter {

    /**
     * 位数组的大小 33554432
     */
    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 函数的类的数组
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];
    /**
     * 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
     */
    public BloomFilter() {
        // 初始化多个不同的 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)));
        }
    }

    //测试
    public static void main(String[] args){

        // Test1
        String value1 = "xxxxxxx";
        String value2 = "yyyyyyy";
        BloomFilter filter = new BloomFilter();
        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));

        //Test2
        Integer value3 = 13423;
        Integer value4 = 22131;
        BloomFilter filter2 = new BloomFilter();
        System.out.println(filter.contains(value3));
        System.out.println(filter.contains(value4));
        filter.add(value3);
        filter.add(value4);
        System.out.println(filter.contains(value3));
        System.out.println(filter.contains(value4));

    }
}

运行结果如下

测试结果

Redis 使用Jedis实现布隆过滤器

准备一个jedis工具类JedisUtils，具体关注布隆过滤器部分setBloomFilterKey、getBloomFilterValue两个方法

/**
 * @ClassName JedisUtils
 * @Description //Jedis工具类
 * @Author singleZhang
 * @Email 405780096@qq.com
 * @Date 2020/12/25 0025 上午 11:51
 **/
public class JedisUtils {

    private static Logger logger = LoggerFactory.getLogger(JedisUtils.class);
    private static String ADDR = "127.0.0.1";
    private static String AUTH = "123123";
    private static int PORT = 6379;
    private static int MAX_ACTIVE = 300;
    private static int MAX_IDLE = 200;
    private static int MAX_WAIT = 10000;
    private static int TIMEOUT = 10000;
    private static boolean TEST_ON_BORROW = true;
    private static JedisPool jedisPool = null;
    static {
        try {
            init();
        } catch (Exception e) {
            logger.error("初始化Redis出错，" + e);
        }
    }
    private synchronized static void init() {
        JedisPoolConfig config = new JedisPoolConfig();
        config.setMaxIdle(MAX_IDLE);
        config.setMaxWaitMillis(MAX_WAIT);
        config.setTestOnBorrow(TEST_ON_BORROW);
        config.setMaxTotal(MAX_ACTIVE);
        jedisPool = new JedisPool(config, ADDR, PORT, TIMEOUT, AUTH);
    }

    /** 布隆过滤器 **/
    /**
     * 根据索引从bitmap中获取值
     * @param bitIndex bitset的索引值
     * @return
     */
    public static boolean getBloomFilterValue(String key,int bitIndex) {
        Jedis jedis = null;
        boolean flag = false;
        try {
            jedis = getResource();
            flag = jedis.getbit(key, bitIndex);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if(null != jedis) {
                jedis.close();
            }
        }
        return flag;
    }
    /**
     * 在bitset中设置key和value
     * @param bitIndex
     * @param b
     */
    public static void setBloomFilterKey(String key,int bitIndex, boolean b) {
        Jedis jedis = null;
        try {
            jedis = getResource();
            jedis.setbit(key, bitIndex, b);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if(null != jedis) {
                jedis.close();
            }
        }
    }
}

准备一个对象工具类ObjectUtils

/**
 * @ClassName ObjectUtils
 * @Description //对象工具类
 * @Author singleZhang
 * @Email 405780096@qq.com
 * @Date 2020/12/25 0025 上午 11:58
 **/
public class ObjectUtils {
    
    /**
     * 序列化
     * */
    public static byte[] serialize(Object object) {
        ObjectOutputStream oos = null;
        ByteArrayOutputStream baos = null;
        try {
            if (object != null){
                baos = new ByteArrayOutputStream();
                oos = new ObjectOutputStream(baos);
                oos.writeObject(object);
                return baos.toByteArray();
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    /**
     * 反序列化
     * */
    public static Object unserialize(byte[] bytes) {
        ByteArrayInputStream bais = null;
        try {
            if (bytes != null && bytes.length > 0){
                bais = new ByteArrayInputStream(bytes);
                ObjectInputStream ois = new ObjectInputStream(bais);
                return ois.readObject();
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }
}

接下来实现一个布隆过滤器BloomFilterUtil

/**
 * @ClassName BloomFilterUtil
 * @Description //布隆过滤器工具类
 * @Author singleZhang
 * @Email 405780096@qq.com
 * @Date 2020/12/25 0025 上午 11:47
 **/
public class BloomFilterUtil {

    // 布隆过滤器key1
    private static final String USER_ID_BIT_SET = "user_id_strhash_bloomfilter";
    // 初始化集合长度
    private static final int length = Integer.MAX_VALUE;
    // 准备hash计算次数
    private static final int HASH_LENGTH = 5;
    /**
     * 准备自定义哈希算法需要用到的质数，因为一条数据需要hash计算5次 且5次的结果要不一样
     */
    private static int[] primeNums = new int[] { 17, 19, 29, 31, 37 };
    /**
     * 添加元素到bitSet中
     * @param key
     */
    public static void addKey(String key) {
        for (int i : primeNums) {
            // 计算hashcode
            int hashcode = hash(key, i);
            // 计算映射在bitset上的位置
            int bitIndex = hashcode & (length - 1);
            JedisUtils.setBloomFilterKey(USER_ID_BIT_SET, bitIndex, true);
        }
    }
    
    /**
     * 判断bitSet中是否有被查询的的key(经过hash处理之后的)
     * @param key
     * @return
     */
    public static boolean hasKey(String key) {
        for (int i : primeNums) {
            // 计算hashcode
            int hashcode = hash(key, i);
            // 计算映射在bitset上的位置
            int bitIndex = hashcode & (length - 1);
            // 只要有一个位置对应不上，则返回false
            if (!JedisUtils.getBloomFilterValue(USER_ID_BIT_SET, bitIndex)) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * 自定义hash函数
     * @param key
     * @param prime
     * @return
     */
    private static int hash(String key,int prime) {
        int h = 0;
        char[] value = key.toCharArray();
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = prime * h + val[i];
            }
        }
        return h;
    }
}

另外Redisson也有布隆过滤器的实现RedissonBloomFilter,这里就不展开了

总结

布隆过滤器在开发中还是比较实用的，如果是用于分布式系统中，推荐使用redis或redisson的实现方式。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,968评论 6赞 482
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,601评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 153,220评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,416评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,425评论 5赞 374
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,144评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,432评论 3赞 401
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,088评论 0赞 261
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,586评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,028评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,137评论 1赞 334
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,783评论 4赞 324
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,343评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,333评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,559评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,595评论 2赞 355
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,901评论 2赞 345

布隆过滤器原理及实现

概述

布隆过滤器

布隆过滤器的原理

布隆过滤器使用场景

布隆过滤器的实现

总结

推荐阅读更多精彩内容