Redis-bloom filter

对比

和hyperloglog相比 bloomfilter占用空间大

多了contains方法

优点

1. 不存储元素本身(某些保密场景也很好用)
2. 存储空间和插入/查询时间都是On

缺点

误算,不能删除元素(因为无法百分百确定元素在不在)

使用场景

新闻客户端实现推荐去重;
查询犯罪历史啥的,还可以保密.

介绍

redis4.0 之后支持插件支持布隆过滤器
支持显示创建布隆过滤器 使用bf.server创建.

原理

图 -- 网上随便搜都能在找到

添加元素的原理

1. 将要添加的元素给k个hash函数
2. 得到对应于位数组上的k个位置
3. 将这k个位置设置成 1

查询元素原理

1. 将要查询的元素给k个hash函数
2. 得到对应数组的k个元素
3. 如果k个位置中有一个为0,则肯定不在集合中
   4.如果k个位置全部为1,则有可能在集合中

bf.server 的三个参数:

默认值; error_rate =0.01 ,initial_size=100;
key:这个不用说了.
initial_size: 预计放入的元素数量,实际数量超过这个数量,误判率会上升.
error_rate:预期的误判率.
错误率越低,需要的空间越大.

127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2
(integer) 1
127.0.0.1:6379> bf.exists codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0
127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0