Redis布隆过滤器
2023-04-18 15:02:37 时间
简介
布隆过滤器是一种概率型数据结构(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% 准确率的场景
- 只能插入和查询元素,不能删除元素。
相关文章
- 直接在代码里面对list集合进行分页
- .NET Framework 4.5新特性详解
- 大数据的简要介绍
- 大数据的由来
- 高斯混合模型的自然梯度变量推理
- timing-wheel 仿Kafka实现的时间轮算法
- 使用Navicat软件连接自建数据库(Linux系统)
- 那一天,我被Redis主从架构支配的恐惧
- Redis 深入了解键的过期时间
- C#使用委托调用实现用户端等待闪屏
- 基于流计算 Oceanus 和 Elasticsearch Service 构建百亿级实时监控系统
- GRAND | 转录调控网络预测数据库
- JFreeChart API中文文档
- 临床相关突变查询数据库
- TIGER | 人类胰岛基因变化查询数据库
- 视频边缘计算网关EasyNVR在视频整体监控解决方案中的应用分析
- Apache Arrow - 大数据在数据湖后的下一个风向标
- 常见的电商数据指标体系
- AKShare-艺人数据-艺人流量价值
- MySQL中多表联合查询与子查询的这些区别,你可能不知道!