Redis布隆过滤器原理及应用场景「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

1、布隆过滤器是什么？（判断某个key一定不存在）

1. 本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构
2. 特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。
3. 相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

使用：

1. 布隆过滤器在NoSQL数据库领域中应用的非常广泛

2. 当用户来查询某一个row时，可以先通过内存中的布隆过滤器过滤掉大量不存在的row请求，然后去再磁盘进行查询

3. 布隆过滤器说某个值不存在时，那肯定就是不存在，可以显著降低数据库IO请求数量

2、应用场景

1）场景1（给用户推荐新闻）

1. 当用户看过的新闻，肯定会被过滤掉，对于没有看多的新闻，可能会过滤极少的一部分（误判）。
2. 这样可以完全保证推送给用户的新闻都是无重复的。

2）场景2（爬虫url去重）

1. 在爬虫系统中，我们需要对url去重，已经爬取的页面不再爬取
2. 当url高达几千万时，如果一个集合去装下这些URL地址非常浪费空间
3. 使用布隆过滤器可以大幅降低去重存储消耗，只不过也会使爬虫系统错过少量页面

3、布隆过滤器原理

1. 每个布隆过滤器对应到Redis的数据结构是一个大型的数组和几个不一样的无偏hash函数
2. 如下图：f、g、h就是这样的hash函数（无偏差指让hash映射到数组的位置比较随机）

添加：值到布隆过滤器

• 1）向布隆过滤器添加key,会使用 f、g、h hash函数对key算出一个整数索引，然后对长度取余
• 2）每个hash函数都会算出一个不同的位置，把算出的位置都设置成1就完成了布隆过滤器添加过程

查询：布隆过滤器值

• 1）当查询某个key时，先用hash函数算出一个整数索引，然后对长度取余
• 2）当你有一个不为1时肯定不存在这个key，当全部都为1时可能有这个key
• 3）这样内存中的布隆过滤器过滤掉大量不存在的row请求，然后去再磁盘进行查询，减少IO操作

删除：不支持

• 1）目前我们知道布隆过滤器可以支持 add 和 isExist 操作
• 2）如何解决这个问题，答案是计数删除，但是计数删除需要存储一个数值，而不是原先的 bit 位，会增大占用的内存大小。
• 3）增加一个值就是将对应索引槽上存储的值加一，删除则是减一，判断是否存在则是看值是否大于0。

在这里插入图片描述

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。