大白话布隆过滤器又能和面试官扯皮了.docx
《大白话布隆过滤器又能和面试官扯皮了.docx》由会员分享，可在线阅读，更多相关《大白话布隆过滤器又能和面试官扯皮了.docx（6页珍藏版）》请在冰点文库上搜索。
大白话布隆过滤器又能和面试官扯皮了
前言
近期在做推荐系统中已读内容去重的相关内容，刚好用到了布隆过滤器，于是写了一篇文章记录分享一下。
文章的篇幅不是很长，主要讲了布隆过滤器的核心思想，目录如下：
什么是布隆过滤器？
布隆过滤器是由一个长度为m比特的位数组与k个哈希函数组成的数据结构。
比特数组均初始化为0，所有哈希函数都可以分别把输入数据尽量均匀地散列。
当插入一个元素时，将其数据通过k个哈希函数转换成k个哈希值，这k个哈希值将作为比特数组的下标，并将数组中的对应下标的值置为1。
当查询一个元素时，同样会将其数据通过k个哈希函数转换成k个哈希值（数组下标），查询数组中对应下标的值，如果有一个下标的值为0表明该元素一定不在集合中，如果全部下标的值都为1，表明该元素有可能在集合中。
至于为什么有可能在集合中？
因为有可能某个或者多个下标的值为1是受到其他元素的影响，这就是所谓的假阳性，下文会详细讲述。
无法删除一个元素，为什么呢？
因为你删除的元素的哈希值可能和集合中的某个元素的哈希值有相同的，一旦删除了这个元素会导致其他的元素也被删除。
下图示出一个m=18,k=3的布隆过滤器示例。
集合中的x、y、z三个元素通过3个不同的哈希函数散列到位数组中。
当查询元素w时，因为有一个比特为0，因此w不在该集合中。
假阳性概率的计算
假阳性是布隆过滤器的一个痛点，因此需要不择一切手段来使假阳性的概率降低，此时就需要计算一下假阳性的概率了。
假设我们的哈希函数选择比特数组中的比特时，都是等概率的。
当然在设计哈希函数时，也应该尽量满足均匀分布。
在比特数组长度m的布隆过滤器中插入一个元素，它的其中一个哈希函数会将某个特定的比特置为1。
因此，在插入元素后，该比特仍然为0的概率是：
现有k个哈希函数，并插入n个元素，自然就可以得到该比特仍然为0的概率是：
反过来讲，它已经被置为1的概率就是：
也就是说，如果在插入n个元素后，我们用一个不在集合中的元素来检测，那么被误报为存在于集合中的概率（也就是所有哈希函数对应的比特都为1的概率）为：
当n比较大时，根据极限公式，可以近似得出假阳性率：
所以，在哈希函数个数k一定的情况下有如下结论：
1.比特数组长度m越大，假阳性率越低。
2.已插入元素的个数n越大，假阳性率越高。
优点
用比特数组表示，不用存储数据本身，对空间的节省相比于传统方式占据绝对的优势。
时间效率很高，无论是插入还是查询，只需要简单的经过哈希函数转换，时间复杂度均为O（k）。
缺点
存在假阳性的概率，准确率要求高的场景不太适用。
只能插入和查询，不能删除了元素。
应用场景
布隆过滤器的用途很多，但是主要的作用就是去重，这里列举几个使用场景。
爬虫重复URL检测
试想一下，XX是一个爬虫，它会定时搜集各大网站的信息，文章，那么它是如何保证爬取到文章信息不重复，它会将URL存放到布隆过滤器中，每次爬取之前先从布隆过滤器中判断这个URL是否存在，这样就避免了重复爬取。
当然这种存在假阳性的可能，但是只要你的比特数组足够大，假阳性的概率会很低，另一方面，你认为XX会在意这种的误差吗，你的一篇文章可能因为假阳性概率没有收录到，对XX有影响吗？
抖音推荐功能
读者朋友们应该没人没刷过抖音吧，每次刷的时候抖音给你的视频有重复的吗？
他是如何保证推荐的内容不重复的呢？
最容易想到的就是抖音会记录用户的历史观看记录，然后从历史记录中排除。
这是一种解决办法，但是性能呢？
不用多说了，有点常识的都知道这不可能。
解决这种重复的问题，布隆过滤器有着绝对的优势，能够很轻松的解决。
防止缓存穿透
缓存穿透是指查询一条数据库和缓存都没有的一条数据，就会一直查询数据库，对数据库的访问压力会一直增大。
布隆过滤器在解决缓存穿透的问题效果也是很好，这里不再细说，后续文章会写。
如何实现布隆过滤器？
了解布隆过滤器的设计思想之后，想要实现一个布隆过滤器其实很简单，陈某这里就不再搬门弄斧了，介绍一下现成的实现方式吧。
Redis实现
Redis4.0之后推出了插件的功能，下面用docker安装：
∙
∙
dockerpullredislabs/rebloom
dockerrun-p6379:
6379redislabs/rebloom
安装完成后连接redis即可，运行命令：
redis-cli
至于具体的使用这里不再演示了，直接看官方文档和教程，使用起来还是很简单的。
Guava实现
guava对应布隆过滤器的实现做出了支持，使用guava可以很轻松的实现一个布隆过滤器。
1.创建布隆过滤器
创建布隆过滤器，如下：
∙
∙
∙
∙
∙
∙
∙
∙
BloomFilterfilter=BloomFilter.create（
Funnels.integerFunnel（）,
5000,
0.01）;
//插入
IntStream.range（0,100_000）.forEach（filter:
:
put）;
//判断是否存在
booleanb=filter.mightContain
（1）;
arg1：
用于将任意类型T的输入数据转化为Java基本类型的数据，这里转换为byte
arg2：
byte字节数组的基数
arg3：
期望的假阳性概率
2.估计最优m值和k值
guava在底层对byte数组的基数（m）和哈希函数的个数k做了自己的算法，源码如下：
升级会员 