布隆过滤器的原理与使用
一、算法介绍
布隆过滤器是一种多哈希函数映射的快速查找算法，通常用于在大数据量场景下快速判断数据存在性。该算法通过牺牲正确性从而在空间和时间上都有不错的效率。
二、算法原理
当一个元素被加入集合时，通过N个散列函数将这个元素映射成一个位图中的N个点，将它们置为1。判断某个元素是否存在时，通过这些点是不是都是1即可：如果这些点有任何一个0，则目标元素一定不在；如果都是1，则目标元素很可能在。例如，一个集合中只存在一个apple元素，其经过三个哈希函数计算映射在位图中三个位，此时判断orange是否存在于集合中，同样经过三个哈希函数计算，我们发现有一位为0，所以orange一定不存在于集合中。
三、算法实现
构造一个布隆过滤器需要一个给定长度的位图和N个哈希函数，那么问题来了，这个位图到底要多大？到底要多少个哈希函数呢？这里引入两个公式：
根据预估数据量n以及误判率fpp，位图大小m的计算方式：
根据预估数据量n以及位图长度m，哈希函数个数k的计算方式：
根据公式我们可以明显看出，当数据量越大、误判率越低，则位图长度越大。
关于m和k的计算，我们可以看一下Guava中的实现：
/** * 计算hash函数个数 * n，预期数据量 * m，位图长度 */ @VisibleForTesting static int optimalNumOfHashFunctions(long n, long m) { return Math.max(1, (int)Math.round((double)m / (double)n * Math.log(2.0D))); } /** * 计算位图长度 * n，预估的数据量 * p， 误判率 */ @VisibleForTesting static long optimalNumOfBits(long n, double p) { if (p == 0.0D) { p = 4.9E-324D; } return (long)((double)(-n) * Math.log(p) / (Math.log(2.0D) * Math.log(2.0D))); }
解决了位图长度和哈希函数个数的计算问题，接下来我们看看哈希函数选取问题，一般情况下我们都需要三个甚至更多的哈希函数，我们如果真要去准备这些函数那就太麻烦了，这里我们可以参考如下论文：
https://www.ccs.neu.edu/home/pete/pub/bloom-filters-verification.pdf
这篇论文提出了一种算法，把原本需要N个哈希函数的计算转化成了两个哈希值的运算，完美地解决了这个问题。如下所示：
上述公式中f(i)为第i个哈希函数。其中0 < i < k。也就是说使用a()和b()对一次输入求出两个不同的哈希值，然后将这两个哈希值代入此公式，便可求出N个哈希值。 在Guava中同样采用此算法，Guava的布隆过滤器中实现了MURMUR128_MITZ_32和MURMUR128_MITZ_64两种策略，我们以MURMUR128_MITZ_32为例看看：
public <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.LockFreeBitArray bits) { long bitSize = bits.bitSize(); long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong(); int hash1 = (int)hash64; int hash2 = (int)(hash64 >>> 32); boolean bitsChanged = false; for(int i = 1; i <= numHashFunctions; ++i) { int combinedHash = hash1 + i * hash2; if (combinedHash < 0) { combinedHash = ~combinedHash; } bitsChanged |= bits.set((long)combinedHash % bitSize); } return bitsChanged; }
计算逻辑如下：
1）根据Murmur3算法计算出输入对象的64位哈希值，并将其分为两段，后32位为hash1，前32位为hash2，hash1对应公式中的函数a的返回值，hash2对应公式中的函数b的返回值；
2）将hash1、hash2和需要的哈希个数numHashFunctions代入公式中，逐个计算出每一个哈希值。
分类: 数据结构与算法
