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

作者：卷福同学

2025-02-19
湖北
本文字数：1741 字
阅读完需：约 6 分钟

1.什么是布隆过滤器

Bloom Filter 会使用一个较大的 bit 数组来保存所有的数据，数组中的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1（代表 false 或者 true），用于检索元素是否存在于大集合中的数据结构。

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

2.原理介绍

核心原理：

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

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

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

3.使用场景

主要是两种场景：

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

4.具体实现（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)));        }
    }}

复制代码

5.中间件实现

Guava 实现的布隆过滤器

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

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

Redis 的布隆过滤器

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

除此之外，还有其他模块的布隆过滤器。

实际使用：

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

复制代码

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/f2e094dd490d0911d63d1fa09】。文章转载请联系作者。

卷福同学

关注

一个在福报厂修福报的程序员 2020-04-30 加入

阿里巴巴Java资深开发，终身学习者，持续文章撰写者，福报厂卷着。目前主要从事地图领域相关业务，负责100万QPS的系统，有丰富的高并发高可用经验

发布

暂无评论

创作场景