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

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
云解析 DNS,旗舰版 1个月
简介: 【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,不影响大局

目录
打赏
0
1
1
0
90
分享
相关文章
Redis游戏积分排行榜项目中通义灵码的应用实战
Redis游戏积分排行榜项目中通义灵码的应用实战
106 4
|
13天前
|
Redis哈希结构在提升数据检索速度中的实践应用
本文详细介绍了 Redis 哈希结构的特点、常见使用场景以及如何在实际应用中利用哈希结构提升数据检索速度。通过合理使用 Redis 哈希结构,可以显著提高系统的性能和响应速度。在实际开发中,结合具体业务需求,灵活运用 Redis 提供的多种数据结构,构建高效的缓存和数据存储解决方案。希望本文能帮助您更好地理解和应用 Redis 哈希结构,提升数据检索速度。
42 18
探秘员工泄密行为防线:基于Go语言的布隆过滤器算法解析
在信息爆炸时代,员工泄密行为对企业构成重大威胁。本文聚焦布隆过滤器(Bloom Filter)这一高效数据结构,结合Go语言实现算法,帮助企业识别和预防泄密风险。通过构建正常操作“指纹库”,实时监测员工操作,快速筛查可疑行为。示例代码展示了如何利用布隆过滤器检测异常操作,并提出优化建议,如调整参数、结合日志分析系统等,全方位筑牢企业信息安全防线,守护核心竞争力。
Vue.js应用结合Redis数据库:实践与优化
将Vue.js应用与Redis结合,可以实现高效的数据管理和快速响应的用户体验。通过合理的实践步骤和优化策略,可以充分发挥两者的优势,提高应用的性能和可靠性。希望本文能为您在实际开发中提供有价值的参考。
56 11
【Azure Redis】部署在AKS中的应用,连接Redis高频率出现timeout问题
查看Redis状态,没有任何异常,服务没有更新,Service Load, CPU, Memory, Connect等指标均正常。在排除Redis端问题后,转向了AKS中。 开始调查AKS的网络状态。最终发现每次Redis客户端出现超时问题时,几乎都对应了AKS NAT Gateway的更新事件,而Redis服务端没有任何异常。因此,超时问题很可能是由于NAT Gateway更新事件导致TCP连接被重置。
|
3月前
|
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
70 5
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
大数据-48 Redis 通信协议原理RESP 事件处理机制原理 文件事件 时间事件 Reactor多路复用
大数据-48 Redis 通信协议原理RESP 事件处理机制原理 文件事件 时间事件 Reactor多路复用
64 2
大数据-46 Redis 持久化 RDB AOF 配置参数 混合模式 具体原理 触发方式 优点与缺点
大数据-46 Redis 持久化 RDB AOF 配置参数 混合模式 具体原理 触发方式 优点与缺点
101 1
【redis】redis的特性和主要应用场景
【redis】redis的特性和主要应用场景
298 2

推荐镜像

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等