一文弄明白Redis布隆过滤器
简介
布隆过滤器是一种概率型数据结构（Probabilistic data structures），对插入和查询比较高效，能够计算 “某样东西 一定不存在 或者 可能存在 ”。
- 如果存在那就是可能存在（hash的碰撞）
- 如果不存在那就一定不存在
相比于传统的 List、Set、Map 等数据结构，它更高效插入和查询、占用空间更少，但是缺点是其返回的结果可能是误判存在的，合理设置长度以及hash 函数的个数可以提高准确率。
布隆过滤器原理
- 向布隆过滤器添加元素
key时, 会使用多个hash函数对key进行hash, 算出一个整数索引值，然后对位数据长度进行取模运算，得到一个位置为 1，每个hash函数都会得到一个位置 - 判断
key是否存在，与上述同理，进行hash取模运算，判断数组这几个位置是否都为1，只要有一个位为0，说明这个key不存在。如果这几个位置都为 1 ，并不一定说明一定存在。 - 如果这个位数组比较稀疏，判断正确的概率会很大，反之， 概率会降低
基本用法
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% 准确率的场景
- 只能插入和查询元素，不能删除元素。
阿里云成长空间 753人发布
查看5道真题和解析