29-布隆过滤器（Bloom Filter）
布隆过滤器（Bloom Filter）
思考
如果要经常判断一个元素是否存在，是你的话，你会考虑怎么做？
- 很容易想到，可以使用哈希表（HashSet，HashMap）,将元素作为key来进行查找
- 通过这种方法的时间复杂度为O(1)，但是缺点在于空间利用率不高，需要占用比较多的内存资源
但是，如果要编写一个网络爬虫去爬10亿个网站数据，为了避免爬到重复的网站，如何判断某个网站是否爬过呢？
- 很显然，HashSet与HashMap比不是非常好的选择，因为会消耗大量的内存空间
那是否存在时间复杂度低，占用内存空间少的方案？
布隆过滤器（Bloom Filter）就可以办到这一点。
布隆过滤器简介
布隆过滤器是在1970年由布隆提出的，它是一个空间利用率高的概率型数据结构，可以用来告诉你，一个元素一定不存在或者可能存在，基于这个结论，所以布隆过滤器有如下的优缺点
- 优点：空间效率和查询时间都远远超过一般的算法
- 缺点：有一定的误判率，删除困难
虽然布隆过滤器存在一定的误判率，但是误判率依然可以通过代码进行控制，所以结合业务需求来进行调整。一般在如下情况下可以考虑使用布隆过滤器
- 经常要判断某一个元素是否存在
- 元素数量巨大，希望有比较少的内存空间
- 允许有一定的误判率
本质：布隆过滤器的本质是一个很长的二进制向量和一系列随机映射函数（Hash函数）
通过上面的描述可以知道，布隆过滤器由2部分组成，一部分为哈希函数，另外一部分为二进制向量
二进制向量：可以理解为二进制数组
常见应用
- 网页黑名单系统，垃圾邮件过滤系统，爬虫的网址判重系统，解决缓存穿透问题
布隆过滤器的原理
现假设布隆过滤器由20位二进制（初始值为0），3个哈希函数组成，每个元素经过哈希函数处理都能生成一个索引
-
添加元素，将每一个哈希函数生成的索引，都设置为1
例如：现在假设要添加一个元素A，这会分别利用三个哈希函数，生成对应的所用值（假设第一个哈希函数生成的索引为4，第二个哈希函数生成的索引为7，第三个哈希函数生成的索引为18），然后将数组中的对应索引中的值设置为1
如果要继续添加元素B，同样会利用三个哈希函数，生成对应的索引值（假设第一个哈希函数生成的索引值为2，第二个哈希函数生成的索引值为7，第三个哈希函数生成的索引值为15），然后将数组中的对应索引中的值设置为1
- 查询元素是否存在：
利用哈希函数，分别计算出元素在对应函数下的索引，如果对应数组索引中的值全部为1，这说明这个元素可能存在，如果对应索引中的值，至少有一个为0，这说明这个元素一定不存在
所以- 如果有一个哈希函数生成的索引位置不为1，就代表不存在（100%准确）
- 如果每一个哈希函数生成的索引位置都为1，就代表存在，但存在一定的误判率
所以，根据布隆过滤器的原理，可以知道
添加/查询的时间复杂度为O(k)，其中k是哈希函数的个数
空间复杂度为O(m)，m是二进制位的个数
布隆过滤器的误判率
误判率p一般来讲，收到3个因素的影响，分别为
- 二进制位的个数m
- 哈希函数的个数k
- 数据规模n
根据下图中已知的公式，就能计算出当前的误判率p
由于在数据规模非常大时，n的值就非常大，所以可以忽略0,5的常系数，同时二进制位的个数也会非常大，所以常数1也可以忽略，因此简化后的公式如下
所以实际开发中，误判率是结合业务来确定的，因此误判率可以认为是一个已知的值。并且数据规模也是已知的，所以就可以利用误判率p和数据规模n得出二进制位的个数m与哈希表的个数k
科学家总结出的公式如下：
计算二进制位的个数
计算哈希表的个数
布隆过滤器的实现
结合前面介绍布隆过滤器的特性，可以知道，布隆过滤器有会提供2个API，分别是添加元素与查询元素是否存在
两个API的实现如下
/*
* n为数据规模
* p为误判率(0,1)
* */
public BloomFilter(int n,double p) {
if (n <= 0 || p <= 0 || p >= 1){
throw new IllegalArgumentException("wrong n or p");
}
double ln2 = Math.log(2);
//计算二进制向量的长度
bitSize = (int)(- (n * Math.log(p)) / (ln2 * ln2));
//计算哈希函数的个数
hashSize = (int)(bitSize * ln2 / n);
//bits数组的长度
bits = new long[(int)((bitSize + Long.SIZE - 1)) / Long.SIZE];
}
/*
* 添加元素
* */
public void put(T value){
nullCheck(value);
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
//生成一个二进制位的索引
int index = combinedHash % bitSize;
//设置index位置的二进制位为1
set(index);
}
}
以上是两个API的主要实现逻辑。具体实现可以查阅demo。
完！
