当前位置： 首页>后端>正文

布隆过滤器原理及实现

后端2024-05-05 11:04:30

概述

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

布隆过滤器

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

布隆过滤器原理及实现,第1张
长度为16的布隆过滤器

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

布隆过滤器的原理

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

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

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

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

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

布隆过滤器使用场景

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

布隆过滤器的实现

  1. 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);
    }
}

执行结果如下


布隆过滤器原理及实现,第3张
布隆过滤器判断结果

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

  1. 通过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));

    }
}

运行结果如下


布隆过滤器原理及实现,第4张
测试结果
  1. 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;
    }
}
  1. 另外Redisson也有布隆过滤器的实现RedissonBloomFilter,这里就不展开了

总结

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


https://www.xamrdz.com/backend/3ht1942726.html

相关文章：