布隆过滤器原理总结

布隆过滤器

历史问题

经典面试题：32位系统中，对10亿个数字排序

校验规则：贷款表中的客户号在客户表中不存在

客户画像：数据如何存储？

每行一个标签

传统软件适用

每行一个客户

互联网行业适用

布隆过滤器原理

一定要记住：布隆过滤器判断存在的不一定存在，但是判断不存在的一定不存在。

多个hash，增大随机性，减少hash碰撞的概率。

扩大数组范围，使用hash值均匀分布，进一步减少hash碰撞的概率。

布隆过滤器特点

返回的结果是概率性的，不是确切的。只能判断数据是否一定不存在，而无法判断数据是否一定存在。

牺牲数据精度，换区空间和时间

优点

由于存放的不是完整的数据，而是用二进制数组替代，所以占用的空间很少。

基于数组的特性，新增和查询速度极快。

二进制数组存储数据，数据保密性很好

缺点

误判（假阳率）

哈希碰撞：数据不存在，但计算后反馈存在

单纯布隆是解决不了这个问题，只能减小概率

很难进行删除。

源码实现

JAVA

Redis

适用场景

主键是否重复

交易中的客户证件号在客户表不存在

黑名单查询

缓存穿透

整数排序

URL爬虫

判断重复的URL

日活用户

客户画像

减少磁盘IO

利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求