【通用】布隆过滤器的原理和使用
场景
如果有场景需要判断一个集合中某个值是否存在时，你第一时间想到的是怎么实现？
比较直接能想到的是使用hash表，即在判断之前对每个值进行哈希处理，将值存放到列表中对应的索引位置，查找时就能通过对目标值的哈希处理就能快速定位是否存在。
但是这个方法有个弊端，内存消耗随数据量和每条数据大小呈现线性增长
假设共有1亿条长度为10的字符串数据，每条数据20字节，考虑哈希冲突，哈希表存储效率通常小于50%，因此消耗的内存：20 * 2 * 1亿 字节 = 4G 内存
这个时候就需要布隆过滤器
由1970年巴顿.布隆提出的数据结构。用于检索一个元素是否在一个集合中，判是存在一定误差。但它的空间效率比哈希表要高出很多。
原理
简单来说，它包含一个很长的二进制向量和一系列随机映射函数。（本篇只介绍简单版本的布隆过滤器）
一个空的布隆过滤器有长度为M比特的bit数组构成，且所有位都初始化0。同时有K个不同的hash函数，每一个都可以将元素映射到bit数组的某一位上，形成一个总体的随机分布。K必须远小于M，且K和M的大小由错误率（false positive rate）决定。
每添加一个元素，由这K个hash函数映射到K个位置，设置这些位为1。
查找一个元素是否在集合中，也是由这K个hash函数映射到K个位置，只要有一个位不为1，则元素一定不存在；但是，全部位都为1，不能代表元素一定存在，可能是其他元素的插入导致，布隆过滤器的误差就来源于此。
那移除元素呢？很显然，既然我们都无法确定一个元素一定存在，也就无法移除元素。
下图示是一个m=18，k=3的布隆过滤器。
为什么说它空间利用率高？
不保存元素值。一个误差率1%且K是最佳数量的布隆过滤器，每多一个元素大约只需要多9.6 bit，且无视元素大小。1亿条数据也只需要1G不到的内存，对比hash表方式，节省不少空间。
如何确定hash函数的数量和二进制数组的长度？
数学推导结果误差率ε：
n 是已经添加元素的数量；
k 哈希的次数；
m 布隆过滤器的长度（如比特数组的大小）
为了得到尽量小的误差率
那么，布隆过滤器的长度 m 可以根据给定的误判率ε 和期望添加的元素个数 n 的通过如下公式计算：
即k和ε的关系（忽略整数要求）
实际使用中，给定一个期望的误判率ε，可以算出相应的最佳hash函数数量K；而布隆过滤器的长度则还与期望插入的元素数量正正比。
使用场景
现在如果有需求是只需要判断一个值在一个大集合里存不存在，且不需要100%的精确度时（比如有兜底确认），我们就可以考虑使用布隆过滤器来实现。
比如以下场景：
缓解缓存穿透
网页 URL 去重
垃圾邮件识别
大集合中重复元素的判断
项目实际运用
基于内存
布隆过滤器有很多实现和优化，由 Google 开发著名的 Guava 库就提供了布隆过滤器（Bloom Filter）的实现。
引入
Code: Select all
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>{guava.version}</version>
</dependency>com.google.common.hash.BloomFilter
初始化参数
1、将目标对象转化为数组的函数对象
com.google.common.hash.Funnels 内有常用的实现
2、期望插入数量
和误判率一起用来计算最佳的二进制数组长度
Code: Select all
(long) (-n * Math.log(p) / (Math.log(2) * Math.log(2))) 3、期望误判率，默认是3%
用于计算最佳hash函数数量
Code: Select all
Math.max(1, (int) Math.round((double) m / n * Math.log(2)))插入元素方法：put(T Object)
判断元素是否存在方法：mightContain(T Object)
缺点：每次应用重启后都需要重新构建
基于Redis
最终需要存储的无非是一个bit数组，那就可以用redis的bitmap来存储，模仿guava来实现。
参考资料：
维基百科
https://en.wikipedia.org/wiki/Bloom_fil ... %20details