布隆过滤器
如果要经常判断某个元素是否存在，你会怎么做？很容易想到使用哈希表（HashSet、HashMap），将元素作为key去查找。时间复杂度为O(1)，但是空间利用率不高，需要占用比较多的内存资源。
如果需要编写一个网络爬虫去爬10亿个网站数据，为了避免爬到重复的网站，如何判断某个网站是否爬过？很显然，HashSet、HashMap并不是非常好的选择。
是否存在时间复杂度低、占用内存较少的方案？就是下面要学习的布隆过滤器。
布隆过滤器（Bloom Filter）
布隆过滤器（Bloom Filter）在1970年由布隆提出，它是一个空间效率高的概率型数据结构，可以用来告诉你：一个元素一定不存在或者可能存在。
它实质上是由一个很长的二进制向量和一系列随机映射函数（Hash函数）组成。
优点：空间效率和查询时间都远远超过一般的算法。
缺点：有一定的误判率、删除困难。
应用场景：网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统、解决缓存穿透问题。
开源实现：google的guava中com.google.common.hash.BloomFilter。
布隆过滤器的原理
假设布隆过滤器由20位二进制、3个哈希函数组成，每个元素经过哈希函数处理都能生成一个索引位置。
- 添加元素（put）：将每一个哈希函数生成的索引位置都设为1
- 查询元素是否存在（contains）：如果有一个哈希函数生成的索引位置不为1，就代表不存在（100%准确），如果每一个哈希函数生成的索引位置都为1，就代表可能存在（存在一定的误判率）。
添加、查询的时间复杂度都是：O(k)，空间复杂度是：O(m)（其中k是哈希函数的个数，m是二进制位的个数）。
布隆过滤器的误判率
误判率p受3个因素影响：二进制位的个数m、哈希函数的个数k、数据规模n。
已知误判率p、数据规模n，求二进制位的个数m、哈希函数的个数k，可以使用下面的公式：
布隆过滤器的实现
数据结构
private long[] bits; // 二进制位
private int bitSize; // 二进制位数
private int hashSize; // 哈希函数的个数
/**
* @param n 数据规模
* @param p 误判率
*/
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); // ln2
bitSize = (int) (- (n * Math.log(p)) / ln2 / ln2); // 二进制位的个数
// (bitSize + Long.SIZE - 1) / Long.SIZE = ceil(bitSize / Long.SIZE)
bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE]; // 初始化二进制位
hashSize = (int) (bitSize * ln2 / n); // 哈希函数的个数
}put
/**
* 添加一个value
*
* @param value
* @return
*/
public boolean put(T value) {
nullCheck(value);
int hash1 = value.hashCode();
int hash2 = value.hashCode() >> 16;
boolean result = false;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
int index = combinedHash % bitSize;
if (set(index)) {
result = true;
}
}
return result;
}
public boolean set(int index) {
int bitsIndex = index / Long.SIZE; // 定位到bits数组中long元素的索引
long value = bits[bitsIndex]; // 定位到long元素
int mask = 1 << (index % Long.SIZE);
long bit = value & mask; // 取出第[index % Long.SIZE]位
bits[bitsIndex] = value | mask; // 将第[index % Long.SIZE]位设置为1
return bit == 0;
}
private void nullCheck(T value) {
if (value == null) {
throw new IllegalArgumentException("Value must not be null.");
}
}contains
/**
* 判断value是否存在，如果返回false，表示一定不存在，如果返回true，表示可能存在
*
* @param value
* @return
*/
public boolean contains(T value) {
nullCheck(value);
int hash1 = value.hashCode();
int hash2 = value.hashCode() >> 16;
for (int i = 0; i < hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
int index = combinedHash % bitSize;
if (!get(index)) {
// 只要有一个为0，则返回false
return false;
}
}
return true;
}
private boolean get(int index) {
long value = bits[index / Long.SIZE]; // 定位到long元素
int mask = 1 << (index % Long.SIZE);
long bit = value & mask; // 取出第[index % Long.SIZE]位
return bit != 0;
}更多精彩内容关注本人公众号：架构师升级之路
