【数据结构】布隆过滤器

前言

在使用 Redis 作缓存时，可能出现 “缓存穿透（对不存在于Redis的数据发起请求，恶意或者误操作地使得大量的请求穿透缓存直接访问数据库，导致数据库压力过大）” 问题。为了防止 Redis 缓存穿透，可以使用 “布隆过滤器” 避免大量不存在的 key 直接访问数据库。

1. 什么是布隆过滤器？

布隆过滤器（Bloom Filter）是由 Burton Howard Bloom 于 1970 年提出的 “位数组” 和 “一组哈希函数” 两部分组成，用于检查元素是否存在于指定集合中的数据结构。

优点：高效且性能很好。

位数组中的每个元素都只占用 1 bit，并且每个元素只能是 0 或者 1。申请 100w 个元素的位数组只占用 1000000 Bit / 8 = 125000 字节 = 125000字节 / 1024 ≈ 122 字节的空间。

缺点：具有一定的误判性（错误识别率）和删除难度。理论情况下，添加到集合中的元素越多，误判的可能性越大。

2. 布隆过滤器的原理

2.1 添加元素原理

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

2.2 判断元素存在原理

对给定元素再次进行相同的哈希计算。
得到值之后判断位数组中的每个元素是否都为 1，如果都为 1，则说明这个元素可能存在于布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

为什么说 “位数组” 中的每个元素都为1，这个元素可能存在于布隆过滤器中？

一方面，判断元素存在需要对给定元素进行哈希计算，哈希计算的 “范围” 受 Integer 的MIN_VALUE(-2 ^ 31) 和 MAX_VALUE(2 ^ 31 - 1)影响，范围有限，不同的元素的哈希计算可能出现同一个哈希值。
另一方面，在布隆过滤器 “添加元素” 时，我们会对给定元素进行多次哈希计算避免 “哈希冲突（哈希函数计算得到相同的哈希码）”，所以，两个不同的元素分别进行多次哈希计算，某次计算的哈希码在位数组的指向可能为同一个位置（如图所示）。

故，位数组中的每个元素都为1，这个元素可能存在于布隆过滤器中。
但是，都不为1，这个元素肯定不存在于布隆过滤器中。

这个说法，在后文中 “使用 Java 语言实现布隆过滤器” 有体现

3. 布隆过滤器使用场景

判断给定数据是否存在：
判断一个数字是否存在于 “包含大量数字” 的数字集合中（5 亿）。
防止 “缓存穿透”（判断请求的数据是否有效避免直接绕过缓存请求数据库）。
邮箱的垃圾邮件过滤、黑名单功能等。
去重
爬虫程序对已经爬取过的 URL 去重。

4. 使用 Java 语言实现布隆过滤器

思路：

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

public class MyBloomFilter {
    // ①位数组的长度
    private static final int DEFAULT_SIZE = 2 << 24; //2^24

    // ③初始化位数组
    private BitSet bits =new BitSet(DEFAULT_SIZE);

    // ④一组哈希函数（哈希操作）
    private static final int[] SEEDS = new int[] {3,13,46,71,91,134}; // 散列的种子数组
    private SimpleHash[] hashOps = new SimpleHash[SEEDS.length];

    // ⑤过滤器构造方法
    public MyBloomFilter(){
        for(int i =0;i<hashOps.length;i++){
            hashOps[i] = new SimpleHash(DEFAULT_SIZE,SEEDS[i]);
        }
    }

    // ⑥添加元素
    public void add(Object value){
        for(SimpleHash sh :hashOps){
            bits.set(sh.hash(value),true);
        }
        System.out.println(bits);
    }

    // ⑦判断元素是否存在
    public boolean contains(Object value){
        boolean ret = true;
        for(SimpleHash sh : hashOps){
            ret = ret && bits.get(sh.hash(value));
        }
        return ret;
    }

    // ②哈希操作
    static class SimpleHash{
        private int cap; //容量
        private int seed; //种子

        public SimpleHash(int cap,int seed){
            this.cap = cap;
            this.seed = seed;
        }

        //哈希函数
        public int hash(Object value){
            int h;
            return value == null ? 0 : Math.abs(seed * (cap -1) & ((h =value.hashCode()) ^ (h >>>16)));
        }
    }
}

测试用例

public class BloomFilterTest {
    public static void main(String[] args) {
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        myBloomFilter.add(131);
        myBloomFilter.add(110);
        myBloomFilter.add(120);
        myBloomFilter.add(119);
        myBloomFilter.add(114);
        System.out.println(myBloomFilter.contains(112));

    }
}

测试结果

{2, 129, 130, 131}
{2, 36, 40, 66, 98, 106, 108, 129, 130, 131}
{2, 32, 36, 40, 56, 66, 80, 98, 106, 108, 112, 120, 129, 130, 131}
{2, 32, 36, 37, 40, 49, 56, 66, 80, 82, 98, 106, 108, 112, 114, 115, 117, 120, 129, 130, 131}
{2, 32, 36, 37, 40, 48, 49, 56, 66, 80, 82, 98, 106, 108, 112, 114, 115, 117, 120, 129, 130, 131}
true

在此， “位数组” 中的每个元素都为1，这个元素可能存在于布隆过滤器中的说法得到了验证。