经常会听到大家说起布隆过滤器，但是很多人都只是听过姓名，却并不知道其是怎样完成的。下面将详细介绍一下布隆过滤器，并且运用简略的代码演示。
什么是布隆过滤器
布隆过滤器（Bloom Filter）是一种空间功率非常高的随机数据结构，它利用位数组（BitSet）表明一个调集，并通过必定数量的哈希函数将元素映射为位数组中的方位，用于查看一个元素是否归于这个调集。
完成的中心思维
关于一个元素，通过多个哈希函数生成多个哈希值，将对应的位在位数组中设为 1，若多个哈希值对应的位都为 1，则以为该元素或许在调集中；若至少有一个哈希值对应的位为 0，则该元素必定不在调集中。这种办法能够在较小的空间中完成高效的查找，但或许存在误判率（false positive）。
怎样了解
一个典型的布隆过滤器包含三个参数： 位数组的巨细（即存储元素的个数）； 哈希函数的个数； 填充因子（即误判率），行将元素数量与位数组巨细的比值。
如上图所示： 布隆过滤器的根本操作流程，包含初始化位数组和哈希函数、刺进元素、查看元素是否在调集中等。其中，每个元素都会被多个哈希函数映射到位数组中的多个方位，而在查看元素是否在调集中时，需求保证一切对应的位都被设置为 1，才会以为该元素或许在调集中。
典型应用场景
垃圾邮件过滤： 将一切的黑名单邮件对应的哈希值在布隆过滤器中对应的方位设为 1，关于每一封新邮件，将其哈希值在布隆过滤器中对应的方位查看是否都为 1，若是，则以为该邮件是垃圾邮件，不然或许是正常邮件；
URL 去重： 将现已抓取的 URL 对应的哈希值在布隆过滤器中对应的方位设为 1，关于每一条新的 URL，将其哈希值在布隆过滤器中对应的方位查看是否都为 1，若是，则以为该 URL 现已抓取过，不然需求进行抓取；
缓存击穿： 将缓存中存在的一切数据对应的哈希值在布隆过滤器中对应的方位设为 1，关于每一个查询的键值，将其哈希值在布隆过滤器中对应的方位查看是否都为 1，若是，则以为该键值存在于缓存中，不然需求从数据库中查询并将其增加到缓存中。
需求留意的是，布隆过滤器的误判率会随着位数组巨细的增加而减小，但一起也会增加内存开支和核算时刻。 为了方便了解布隆过滤器，下面用java代码完成一个简略的布隆过滤器：
import java.util.BitSet;
import java.util.Random;
public class BloomFilter {
private BitSet bitSet; // 位集，用于存储哈希值
private int bitSetSize; // 位集巨细
private int numHashFunctions; // 哈希函数数量
private Random random; // 随机数生成器
// 构造函数，依据希望元素数量和错误率核算位集巨细和哈希函数数量
public BloomFilter(int expectedNumItems, double falsePositiveRate) {
this.bitSetSize = optimalBitSetSize(expectedNumItems, falsePositiveRate);
this.numHashFunctions = optimalNumHashFunctions(expectedNumItems, bitSetSize);
this.bitSet = new BitSet(bitSetSize);
this.random = new Random();
}
// 依据希望元素数量和错误率核算最佳位集巨细
private int optimalBitSetSize(int expectedNumItems, double falsePositiveRate) {
int bitSetSize = (int) Math.ceil(expectedNumItems * (-Math.log(falsePositiveRate) / Math.pow(Math.log(2), 2)));
return bitSetSize;
}
// 依据希望元素数量和位集巨细核算最佳哈希函数数量
private int optimalNumHashFunctions(int expectedNumItems, int bitSetSize) {
int numHashFunctions = (int) Math.ceil((bitSetSize / expectedNumItems) * Math.log(2));
return numHashFunctions;
}
// 增加元素到布隆过滤器中
public void add(String item) {
// 核算哈希值
int[] hashes = createHashes(item.getBytes(), numHashFunctions);
// 将哈希值对应的位设置为 true
for (int hash : hashes) {
bitSet.set(Math.abs(hash % bitSetSize), true);
}
}
// 查看元素是否存在于布隆过滤器中
public boolean contains(String item) {
// 核算哈希值
int[] hashes = createHashes(item.getBytes(), numHashFunctions);
// 查看哈希值对应的位是否都为 true
for (int hash : hashes) {
if (!bitSet.get(Math.abs(hash % bitSetSize))) {
return false;
}
}
return true;
}
// 核算给定数据的哈希值
private int[] createHashes(byte[] data, int numHashes) {
int[] hashes = new int[numHashes];
int hash1 = Math.abs(random.nextInt());
int hash2 = Math.abs(random.nextInt());
for (int i = 0; i < numHashes; i++) {
// 运用两个随机哈希函数核算哈希值
hashes[i] = Math.abs((hash1 * i) + (hash2 * i) + i) % data.length;
}
return hashes;
}
}
