Redis基础篇——布隆过滤器

不太精确的set结构,使用contains方法判断对象是否存在时可能误判。
只要参数设置合理,精确度就相对足够精确。
只会误判存在,不会误判不存在。
一种数据结构,由一串很长的二进制向量组成,可以看成一个二进制数组,当做一个容器,初始默认值都是0。

1、使用场景

(1)爬虫:判断某个url是否已经爬过了;
(2)垃圾邮箱的过滤;
(3)判断新增的10W个号码,是否已经存在于10亿个号码池里了。

2、操作

bf.add
bf.exists
添加:
通过多个hash函数计算出多个index,将对应位置都置为1。
判断存在:
①把数据用这些hash函数都计算一次,只要有一个为0,就表示数据不存在;
②那么能不能说,如果一个数据的这些hash函数计算结果都是1,是不是就说明数据是存在的?答案是不能,因为多个数据可能这些hash函数计算结果一样。
所以说,布隆过滤器只能判断数据的不存在,不能判断存在。

3、优缺点

(1)二进制数组,占用内存小,插入、查询都快;
(2)数据越多,误判率越高,无法判断数据的存在,无法删除数据。

4、redis实现

(1)bitmap

另外写了一篇。

(2)Redisson

另外写了一篇。

上一篇:LeetCode热题100 1.两数之和


下一篇:使用pointcloud_to_laserscan包实现三维转二维