Redis布隆过滤器

简介

布隆过滤器是一种概率型数据结构（Probabilistic data structures），对插入和查询比较高效，能够计算 “某样东西 一定不存在 或者 可能存在 ”。

• 如果存在那就是可能存在（hash的碰撞）
• 如果不存在那就一定不存在

相比于传统的 List、Set、Map 等数据结构，它更高效插入和查询、占用空间更少，但是缺点是其返回的结果可能是误判存在的，合理设置长度以及hash 函数的个数可以提高准确率。

布隆过滤器原理

• 向布隆过滤器添加元素 key 时, 会使用多个 hash 函数对 key 进行 hash, 算出一个整数索引值，然后对位数据长度进行取模运算，得到一个位置为 1，每个 hash 函数都会得到一个位置
• 判断 key 是否存在，与上述同理，进行 hash 取模运算，判断数组这几个位置是否都为1，只要有一个位为0，说明这个 key 不存在。如果这几个位置都为 1 ，并不一定说明一定存在。
• 由于不用的 key, 可能占用相同的位置，所以如果这个位数组比较稀疏，判断正确的概率会很大，反之， 概率会降低

基本用法

127.0.0.1:6379> bf.add days day1
(integer) 1 
127.0.0.1:6379> bf.add days day2
(integer) 1 
127.0.0.1:6379> bf.exists days day1
(integer) 1 
127.0.0.1:6379> bf.exists days day2
(integer) 1 
127.0.0.1:6379> bf.exists days day3
(integer) 0 
127.0.0.1:6379> bf.madd days day4 day5 day6 
1)(integer) 1 
2)(integer) 1 
3)(integer) 1 
127.0.0.1:6379> bf.mexists days day4 day5 day6 day7 
1)(integer) 1 
2)(integer) 1 
3)(integer) 1 
4)(integer) 0

Redis还提供了自定义参数布隆过滤器，参数如下：

• error_rate： 错误率，数值越小，所需空间越大，默认值：0.01
• initial_size： 预计放入元素的数量，当数量超过这个值后，误判率会上升，默认值：100

优缺点

布隆过滤器的优点显而易见：

• 不需要存储数据，只用比特表示，因此在空间占用率上有巨大的优势
• 检索效率搞，插入和查询的时间复杂度都为 O(K)（K 表示哈希函数的个数）
• 哈希函数之间相互独立，可以在硬件指令层次并行计算，因此效率较高。

缺点：

• 存在不确定的因素，无法判断一个元素是否一定存在，所以不适合要求 100% 准确率的场景
• 只能插入和查询元素，不能删除元素。