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

本文涉及的产品
云原生网关 MSE Higress,422元/月
MSE Nacos/ZooKeeper 企业版试用,1600元额度,限量50份
容器镜像服务 ACR,镜像仓库100个 不限时长
简介: 布隆过滤器(Bloom Filter)是一种高效的空间节省型数据结构,用于判断元素是否存在于集合中。它通过多个哈希函数将元素映射到位数组,查询时检查对应位是否全为1。优点是空间效率高,缺点是有一定误判率。典型应用场景包括缓存穿透防护、垃圾邮件过滤、黑名单管理及去重等。Java实现中使用BitSet和自定义哈希函数,而Guava和Redis也提供了布隆过滤器的实现。

1.什么是布隆过滤器

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

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

2.原理介绍

核心原理:

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

布隆过滤器原理.png

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

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

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

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

基础操作命令

命令 作用 示例
BF.ADD 向布隆过滤器添加单个元素,若key不存在则自动创建(默认参数:error_rate=0.01, capacity=100)。 BF.ADD user_filter "user:1001"
BF.MADD 批量添加多个元素到布隆过滤器。 BF.MADD user_filter "user:1002" "user:1003"
BF.EXISTS 判断单个元素是否可能存在于过滤器中(返回1可能存在,0一定不存在)。 BF.EXISTS user_filter "user:1001"
BF.MEXISTS 批量判断多个元素是否存在。 BF.MEXISTS user_filter "user:1001" "invalid_user"

实际使用:

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
相关文章
|
8月前
|
人工智能 自然语言处理 前端开发
VSCode AI提效工具,通义灵码前端开发体验
通义灵码2.0是一款强大的VS Code插件,安装简便,图标易记。其亮点包括接入deepseek-v3/r1模型,支持智能问答、AI编程、代码优化及贴图提问;多语言和编辑器支持;个性化使用满足不同需求。个人版完全免费,节省12%开发时间。对比1.0版本,2.0在功能实现上更加完善,尤其在前端项目中表现出色,根据需求描述生成完整项目结构和详细代码,极大提升开发效率。
558 0
|
8月前
|
敏捷开发 存储 数据可视化
产品经理的效率秘籍:科学梳理产品需求
产品梳理旨在解决信息混乱、需求不清等问题,使产品架构清晰、目标明确、执行高效。通过厘清产品定位、优化需求管理、提高执行效率和加强团队协作,企业可以减少沟通成本,提升整体效率。关键步骤包括确定产品架构、规范需求管理和建立任务管理机制。借助工具如板栗看板,可实现需求可视化、高效任务拆解及顺畅的团队协作,确保产品梳理顺利落地。定期复盘和优化,引导团队使用协同工具,并加强跨部门协同,是成功的关键。
|
8月前
|
人工智能 自然语言处理 数据可视化
AutoAgents:比LangChain更激进的AI开发神器!自然语言生成AI智能体军团,1句话搞定复杂任务
AutoAgents 是基于大型语言模型的自动智能体生成框架,能够根据用户设定的目标自动生成多个专家角色的智能体,通过协作完成复杂任务。支持动态生成智能体、任务规划与执行、多智能体协作等功能。
1441 91
|
8月前
|
人工智能 自然语言处理 程序员
体验通义灵码的AI程序员:用Python+Tkinter实现表单向config.ini写入与读取
本文介绍了如何利用通义灵码的AI程序员快速开发一个基于Python和Tkinter的表单应用程序,实现对config.ini文件的读写。通过简单的自然语言描述,通义灵码能自动生成代码框架、自动补全功能代码,并提供错误检测与修复建议,极大提高了开发效率。开发者只需安装必要库(如configparser)并配置VSCode插件TONGYI Lingma,即可轻松创建包含多个输入项和按钮的表单界面。运行程序后,用户可以编辑表单并保存数据到config.ini文件中,再次启动时数据会自动加载显示。这一过程展示了AI在编程中的高效性和灵活性,为开发者提供了全新的开发方式。
305 3
|
8月前
|
Java 关系型数据库 MySQL
ssm063基于SSM框架的德云社票务系统的设计与实现(文档+源码)_kaic
基于SSM框架的德云社票务系统旨在解决传统相声订票方式费时费力的问题,提供便捷的在线订票平台。系统采用Java技术、MySQL数据库,结合B/S架构,确保数据安全性和操作简便性。用户可轻松查询、预订相声票务信息,管理员则能高效管理票务和会员信息。该系统功能齐全、运行稳定,适用于现代信息化生活需求,有效提升德云社的票务管理效率与用户体验。
|
8月前
|
存储 缓存 分布式计算
【赵渝强老师】Spark RDD的缓存机制
Spark RDD通过`persist`或`cache`方法可将计算结果缓存,但并非立即生效,而是在触发action时才缓存到内存中供重用。`cache`方法实际调用了`persist(StorageLevel.MEMORY_ONLY)`。RDD缓存可能因内存不足被删除,建议结合检查点机制保证容错。示例中,读取大文件并多次调用`count`,使用缓存后执行效率显著提升,最后一次计算仅耗时98ms。
163 0
【赵渝强老师】Spark RDD的缓存机制
|
7月前
|
存储 大数据 BI
场景题:有40亿个QQ号如何去重?仅1GB内存
在处理大数据去重问题时,如40亿QQ号的去重(仅1GB内存),可采用Bitmap和布隆过滤器两种方法。Bitmap利用位图存储,每个QQ号占1位,总需512MB内存,适用于整型数据;布隆过滤器通过多个哈希函数计算下标,适合字符串或对象去重,但存在误判率。在线人员统计等场景也可使用类似思路,将ID作为偏移值标记在线状态或视频存在性。
233 3
|
8月前
|
前端开发 Java 数据库连接
Spring框架初识
Spring 是一个分层的轻量级开源框架,核心功能包括控制反转(IOC)和面向切面编程(AOP)。主要模块有核心容器、Spring 上下文、AOP、DAO、ORM、Web 模块和 MVC 框架。它通过 IOC 将配置与代码分离,简化开发;AOP 提供了声明性事务管理等增强功能。
135 21
Spring框架初识
|
8月前
|
自然语言处理 开发者
GDC2025 | 探索最前沿的开源大模型技术与创新,2025全球开发者先锋大会,上海见!
2025全球开发者先锋大会将于2月21-23日在徐汇盛大召开!大会以“模塑全球 无限可能”为主题,定位“社区的社区”,旨在促进基模、垂模、语料、算力、基金、开发者、软件服务等产业生态深度对接。
318 0