一文弄明白Redis布隆过滤器

简介

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

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

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

布隆过滤器原理

一文弄明白Redis布隆过滤器

  • 向布隆过滤器添加元素 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% 准确率的场景
  • 只能插入和查询元素,不能删除元素。


 

 

上一篇:xctf攻防世界 MISC高手进阶区 easycap


下一篇:Wireshark实验