【redis】布隆过滤器(Bloom Filter)原理解析与应用

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: 【redis】布隆过滤器(Bloom Filter)原理解析与应用

布隆过滤器(Bloom Filter),是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。


Bloom Filter原理

当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任

何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。

比如数据库的id现在有:1、2、3

那就用id:1 为例子他在上图中经过三次hash之后,把三次原本值0的地方改为1

下次我进来查询如果id也是1 那我就把1拿去三次hash 发现跟上面的三个位置完全一样,那就能证明过滤器中有1的

应用场景

1.大数据判断是否存在

HashMap可以判断某个元素是否存,可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高。但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多例如上亿的时候,那 HashMap 占据的内存大小就变得很可观了。这时候我们就需要考虑布隆过滤器了。

2.解决缓存穿透

布隆过滤器(Bloom Filter)提前将数据库的数据hash存到过滤器中,然后当redis没有这个key,请求来的时候先去布隆过滤器x次hash这个key,看是否都为1(都为1说明很大概率有这个key),如果是缓存穿透,就是数据库和redis都没有这个数据的话,布隆过滤器很大概率也没有,这样就能过滤掉绝大部分的没有得值

如何实现

引入依赖

 <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>19.0</version>
        </dependency>

代码

   private static int size = 1000000;//预计要插入多少数据
 
    private static double fpp = 0.01;//期望的误判率
 
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
 
    public static void main(String[] args) {
        //插入数据
        for (int i = 0; i < 1000000; i++) {
            bloomFilter.put(i);
        }
        int count = 0;
        for (int i = 1000000; i < 2000000; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
                System.out.println(i + "误判了");
            }
        }
        System.out.println("总共的误判数:" + count);
    }

经过测试,误判率大概在0.01,不影响大局

目录
相关文章
|
5天前
|
缓存 NoSQL Java
在 Spring Boot 应用中使用 Spring Cache 和 Redis 实现数据查询的缓存功能
在 Spring Boot 应用中使用 Spring Cache 和 Redis 实现数据查询的缓存功能
22 0
|
6天前
|
消息中间件 运维 监控
Linux命令lsipc:深入解析与实战应用
`lsipc` (通常指 `ipcs`) 是Linux命令,用于查看系统中的IPC资源,包括消息队列、信号量和共享内存。它显示详细信息,支持过滤,并且需要相应权限。示例用法:显示共享内存(`-m`)、查询消息队列(`-q -i ID`)、查看关联进程(`-m -p`)。注意权限、操作影响及定期监控。结合`ipcrm`等工具可进行更深入管理。
|
7天前
|
Java 开发者 Spring
深入解析这两种扩展机制的工作原理和用法
深入解析这两种扩展机制的工作原理和用法
|
7天前
|
数据处理 C语言
深入解析x86架构:X86, X86_32和X86_64的差异与应用
深入解析x86架构:X86, X86_32和X86_64的差异与应用
13 0
|
7天前
|
存储 缓存 Java
滚雪球学Java(64):LinkedHashSet原理及实现解析
【6月更文挑战第18天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
15 1
滚雪球学Java(64):LinkedHashSet原理及实现解析
|
2天前
|
前端开发 小程序 Java
深入解析Java Servlet与JSP:构建高效服务器端应用
【6月更文挑战第23天】Java Servlet和JSP是Web开发的关键技术,用于构建高效服务器端应用。Servlet处理HTTP请求,执行业务逻辑,而JSP专注于动态HTML生成。两者结合,借助MVC架构,实现逻辑与视图分离,提高代码可读性和性能。尽管有新框架出现,Servlet和JSP仍是许多项目的基础。
|
1天前
|
数据采集 算法 BI
解析numpy中的iscomplex方法及实际应用
在 NumPy 中,iscomplex 函数用于检查数组中的每个元素是否为复数。这个函数在处理包含复数数据的数组时非常有用,尤其是在科学计算和工程领域,这些领域经常需要区分实数和复数。 在数学和工程领域,复数是一种基本的数值类型,它们扩展了实数系统,包含了实部和虚部。在 NumPy 中,复数由 numpy.complex128 或 numpy.complex64 类型表示。numpy.iscomplex 函数提供了一种简便的方式来检查数组中的元素是否为复数。这对于数据类型判断、数据清洗和后续的数值分析非常重要。
|
2天前
|
NoSQL Linux 程序员
Linux objdump命令:深入解析与实战应用
`objdump`是Linux下的反汇编工具,用于将二进制文件转换为汇编代码,便于理解程序底层。它可以反汇编目标文件、可执行文件和库,支持多种参数,如显示符号表(-t)、反汇编代码(-d)、源代码与汇编混合视图(-S)。在实践中,结合-g编译选项和特定段(-j)反汇编,能辅助调试和分析。使用时注意包含调试信息,选择适当参数,并与其他工具(如gdb)配合使用。
|
3天前
|
关系型数据库 MySQL 数据库连接
蓝易云 - PHP基本语法解析与应用指南
以上只是PHP基本语法的简要概述,要深入了解和掌握PHP,你需要阅读更多的教程和参考资料,并通过实践来提高你的技能。
16 2
|
4天前
|
数据可视化 搜索推荐 atlas
DataV Atlas深度解析与实战应用:打造个性化地理信息可视化
阿里云DataV的Atlas功能专注于地理信息可视化,提供范围选择、边界生成和层级展示等工具,助用户轻松创建专业地图应用。通过代码示例展示了如何用Geo组件展示中国省份销售数据,强调了数据安全和性能优化的重要性。DataV Atlas简化了复杂地理信息的展示,提升了数据洞察的直观性和美感。【6月更文挑战第19天】
376 3

推荐镜像

更多