布隆过滤器的原理与使用

一、算法介绍

布隆过滤器是一种多哈希函数映射的快速查找算法,通常用于在大数据量场景下快速判断数据存在性。该算法通过牺牲正确性从而在空间和时间上都有不错的效率。

二、算法原理

当一个元素被加入集合时,通过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代入公式中,逐个计算出每一个哈希值。

上一篇:Vue的计算属性


下一篇:力扣每日一题 2022.1.7