布隆过滤器原理总结
2021-07-09 17:27:34 34 举报AI智能生成
布隆过滤器原理总结
作者其他创作
大纲/内容
历史问题
经典面试题：32位系统中，对10亿个数字排序
校验规则：贷款表中的客户号在客户表中不存在
客户画像：数据如何存储？
每行一个标签
传统软件适用
每行一个客户
互联网行业适用
布隆过滤器原理
一定要记住：布隆过滤器判断存在的不一定存在，但是判断不存在的一定不存在。
多个hash，增大随机性，减少hash碰撞的概率。
扩大数组范围，使用hash值均匀分布，进一步减少hash碰撞的概率。
布隆过滤器特点
返回的结果是概率性的，不是确切的。只能判断数据是否一定不存在，而无法判断
数据是否一定存在。
数据是否一定存在。
牺牲数据精度，换区空间和时间
优点
由于存放的不是完整的数据，而是用二进制数组替代，所以占用的空间很少。
基于数组的特性，新增和查询速度极快。
二进制数组存储数据，数据保密性很好
缺点
误判（假阳率）
哈希碰撞：数据不存在，但计算后反馈存在
单纯布隆是解决不了这个问题，只能减小概率
很难进行删除。
源码实现
JAVA
Redis
适用场景
主键是否重复
交易中的客户证件号在客户表不存在
黑名单查询
缓存穿透
整数排序
URL爬虫
判断重复的URL
日活用户
客户画像
减少磁盘IO
利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不
存在的话，我们可以不用进行后续昂贵的查询请求
存在的话，我们可以不用进行后续昂贵的查询请求
0 条评论
下一页
