布隆过滤器原理和使用场景

布隆过滤器原理和使用场景

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，主要用于判断一个元素是否在一个集合中。虽然它可能会产生误判（即把不属于集合的元素误判为属于集合），但绝对不会把属于集合的元素误判为不属于集合。这种特性使得布隆过滤器在大数据处理、缓存系统、网络爬虫等领域有着广泛的应用。

什么是布隆过滤器

布隆过滤器使用一个较大的位数组来保存所有数据，数组中的每个元素都只占用1位，且只能是0或1（代表false或true）。它主要用于检索元素是否存在于大集合中。

缺点是：有一定的错误识别率。

原理介绍

布隆过滤器的核心原理包括：

• 数据结构：由二进制数组和多个哈希函数组成
• 添加元素：通过多个哈希函数计算得到多个位数组位置，将这些位置设为1
• 查询元素：进行相同的哈希计算，判断数组中每个位置的元素是否都为1。如果都为1，则可能存在；如果有一个值不为1，则一定不存在。

不同的字符串可能哈希出来的位置相同，这种情况可以通过适当增加位数组大小或者调整哈希函数来解决。

综上，我们可以得出：布隆过滤器说某个元素存在，小概率会误判；布隆过滤器说某个元素不在，那么这个元素一定不在。

使用场景

布隆过滤器主要应用于以下场景：

• 判断给定数据是否存在
• 缓存穿透防护（拦截不存在的数据请求，避免频繁查询数据库）
• 邮箱垃圾邮件过滤（判断一个邮件地址是否在垃圾邮件列表中）
• 黑名单功能（判断一个IP或者手机号等是否在黑名单中）
• 去重
• 爬虫URL去重（爬给定网址时对已爬过的URL去重）
• 对巨量QQ号、订单号去重
• 抖音推荐功能，推荐的视频不重复

具体实现（Java手写）

了解了布隆过滤器的原理，可以手动实现一个，关键步骤有：

• 一个合适大小的位数组
• 几个不同的哈希函数
• 添加元素到位数组的方法实现
• 查询方法，即判断元素是否在位数组的方法实现

下面是具体的Java代码实现：

import java.util.BitSet;

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((cap - 1) & seed * ((h = value.hashCode()) ^ (h >>> 16)));
        }
    }
}

中间件实现

Guava实现的布隆过滤器

Guava中布隆过滤器的实现算是比较权威的，缺陷是只能单机使用。要想在分布式场景使用，需要用Redis的布隆过滤器。

具体代码实现可以自行搜索。

Redis的布隆过滤器

Redis官网推荐了一个RedisBloom作为Redis布隆过滤器的Module，地址：https://github.com/RedisBloom/RedisBloom。除此之外，还有其他模块的布隆过滤器。

基础操作命令

实际使用：

127.0.0.1:6379> BF.ADD myFilter java
(integer) 1
127.0.0.1:6379> BF.ADD myFilter javag
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter java
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter javag
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0

本文原文来自阿里云开发者社区