布隆过滤器

布隆过滤器

leo 706 2021-04-10

布隆过滤器

布隆过滤器（Bloom Filter）是一种来检索元素是否在给定大集合中的数据结构，这种数据结构是高效且性能很好的，但缺点是具有一定的错误识别率和删除难度。并且，理论情况下，添加到集合中的元素越多，误报的可能性就越大。

它由位数组和一系列哈希函数构成。初始时位数组的值全为0。

布隆过滤器原理

加入元素

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

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

判断元素是否存在

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

  1. 使用布隆过滤器中的哈希函数对该元素值进行计算；
  2. 得到多个哈希值之后判断位数组中的对应为位置元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

由于不同的元素值通过相同的哈希函数可能为得到相同的哈希值，所以布隆过滤器在判断元素存在时为存在误判的情况，但判断元素不存在时是确定的。

使用场景

  1. 判断给定数据是否存在于一个大量数据集合中：比如判断一个数字是否存在于包含大量数字的数字集中（数字集很大，5亿以上！）、 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等、邮箱的垃圾邮件过滤、黑名单功能等等。
  2. 去重：比如爬给定网址的时候对已经爬取过的 URL 去重。

Java 实现布隆过滤器

可以自己实现，也可以使用 Guava 提供的实现。

package top.zysite.bloom.filter;

import java.util.BitSet;

/**
 * 布隆过滤器
 *
 * @author Leo
 * @create 2020/12/25 15:12
 **/
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 函数的类的数组
     */
    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)));
        }

    }
}

测试：

package top.zysite.bloom.filter;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import org.junit.Test;

/**
 * 布隆过滤器测试类
 *
 * @author Leo
 * @create 2020/12/25 15:15
 **/
public class MyBloomFilterTest {

    /**
     * 测试自己实现的布隆过滤器
     */
    @Test
    public void testMyBloomFilter() {
        //创建布隆过滤器对象
        MyBloomFilter myBloomFilter = new MyBloomFilter();

        String str1 = "MyBloomFilterTest";
        String str2 = "testMyBloomFilter";

        System.out.println(myBloomFilter.contains(str1));
        System.out.println(myBloomFilter.contains(str2));

        //将元素放入布隆过滤器
        myBloomFilter.add(str1);
        myBloomFilter.add(str2);

        System.out.println(myBloomFilter.contains(str1));
        System.out.println(myBloomFilter.contains(str2));
    }

    /**
     * 测试 Guava 提供的布隆过滤器
     */
    @Test
    public void testGuavaBloomFilter(){
        // 创建布隆过滤器对象
        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));
    }

}

使用 Guava 提供的实现需引入以下依赖：

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

Redis 中使用布隆过滤器

Redis v4.0 之后有了 Module（模块/插件） 功能，Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。

官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module 地址：https://github.com/RedisBloom/RedisBloom

根据项目的 Readme 可以快速入门。

Algorithm Redis