深入探讨布隆过滤器

雨翔河

首页列表关于

深入探讨布隆过滤器

2020-01-08 02:53

看了很多网上的文章好像对布隆过滤器有什么误解，不是抄袭就是拷贝来的文章，没有说到根本和真正的生产实践，还有的就是只说原理，但是你会发现合适的实现和原理有时候并不完全一样。

就以谷歌的guava实现布隆过滤器为参考吧。

原理什么的就不详细介绍了，直接进入正题。

如果要让布隆过滤器趋于完美，首先要有一个预估的数据量，和误差率，需要通过这两个值来算到你需要的合适的hash函数的个数和合适的bit位长度。

这个计算公式早已有了数学家提供了数学理论基础，谷歌也是这么实现的。（按照现有的一些网络上各种拷贝的文章，这种值是随便取，没有根据）

在维基百科中我们可以看到这样的一些公式：
求M和K， https://en.wikipedia.org/wiki/Bloom_filter

![](https://cdn.yuxianghe.net/image/blog/70-1.png)

参考这个公式我们可以用代码实现这个公式函数，直接调用即可。

1. 首先要先求出M，bit位的长度，M是在已知的预期数据总数和预期的误差率的基础上得到的。
```
     /**
     * 求M，bit位长度。
     *
     * @param n 预期的数据总数
     * @param p 预期的误差率
     * @return int
     */
    public static int optimalM(long n, double p) {
        double fz = -1 * n * Math.log(p);
        double fm = Math.log(2) * Math.log(2);
        double v = fz / fm;
        return BigDecimal.valueOf(Math.ceil(v)).intValue();
    }
```

2. 在计算出了M之后，就可以接着求需要的K个hash函数。
```
     /**
     * 求函数个数k
     *
     * @param m bit位长度
     * @param n 预期的数据总数
     * @return int
     */
    public static int optimalK(long m, double n) {
        double kk = (m / n) * Math.log(2);
        int k = BigDecimal.valueOf(Math.ceil(kk)).intValue();
        return k;
    }
```

有了M和k之后，接下来就是写布隆过滤器的核心的部分，入参是需要hash的数据，出参是hash之后得到的K个bit位索引。

很多人会觉得k个hash函数的话，只需要使用 `MurmurHash3` 的hash算法做种就可以得到k个函数，这种方法不是不可以，只是性能太差了，如果做k次hash的话，耗时是很大的，所以这里可以取巧使用h1+h2的方式来做，这种做法是否符合布隆过滤器原理的要求呢，有数学家已经做了论证，谷歌也是这么实现的，可以参考：
Adam Kirsch 和 Michael Mitzenmacher 有一篇论文《Less Hashing, Same Performance: Building a Better Bloom Filter》，翻译过来就是更少的hash，相同的性能，构建更好的布隆过滤器。
论文pdf地址：
https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf

所以代码实现如下：

```
     /**
     * 返回hash之后索引值列表
     * 默认是int的hash版本
     * 可以看出来这里的hash使用的是64位拆分为两个32位的int，所以数据量不能太大，数据量太大很容易造成碰撞，建议不超过十亿级别
     * 想要支持十亿级别以上的支持，可以重载下这个方法。使用128位的hash方法去计算出两个long来进行操作。
     *
     * @param value value
     * @return List<Long>
     */
    List<Integer> indexList(String value) {
        byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
        long hashResult = MurmurHash3.hash64(bytes, 0, bytes.length, hashSeed);
        byte[] hashResultBytes = Longs.toByteArray(hashResult);
        int hash1 = Ints.fromBytes(hashResultBytes[7], hashResultBytes[6], hashResultBytes[5], hashResultBytes[4]);
        long hash2 = Ints.fromBytes(hashResultBytes[3], hashResultBytes[2], hashResultBytes[1], hashResultBytes[0]);
        int combinedHash = hash1;
        List<Integer> list = new ArrayList<>();
        for (int j = 0; j < this.k; j++) {
            int index = combinedHash & Integer.MAX_VALUE;
            index = index % this.m;
            list.add(index);
            combinedHash += hash2;
        }
        return list;
    }
```

如上代码所示，这里使用的是只进行一次hash来得到K次hash的结果，先得到一个64位的long类型数据，然后拆分为两个32位的int，这样得到两个数之后。
`combinedHash += hash2;` 依次进行加法操作，得到k个结果，这样形成的hash值会是均衡分布的。比起多次执行hash函数，效率要高好多，碰撞率也不会有偏差。

如果想要更大的数据量，就需要使用 `MurmurHash3` 生产出128位的数，拆分为两个64位的long类型。

另外需要注意的是： 当得到的hash值是负数的时候，需要对负数做转正数的操作，因为对值并没有很强烈的确定性（比如-5转换后对应+5，只要转换结果每次是一致的，且是正数，得到的正数是什么值无关紧要），所以可以直接使用。

`int index = combinedHash & Integer.MAX_VALUE;` 这种位操作可以直接进行负数转正数。

还有一种骚操作是： `index = ~combinedHash;`

以上两种负正转换的方式，一种是从正数最大值往下减，一种是从0开始往上增，但是效率都很高，毕竟是位操作。因为计算机里面表示负数都是以符号位为1，其余位对原码取反，所以脑补下吧，大学知识，虽然忘的七七八八了。

再说到为什么不用 `Math.abs(hash)` ,其实一开始我想当然的用了这个做负数转正数，绝对值嘛，没毛病，但是可以看下它的源码。

```
     /**
     * Returns the absolute value of an {@code int} value.
     * If the argument is not negative, the argument is returned.
     * If the argument is negative, the negation of the argument is returned.
     *
     * <p>Note that if the argument is equal to the value of
     * {@link Integer#MIN_VALUE}, the most negative representable
     * {@code int} value, the result is that same value, which is
     * negative.
     *
     * @param   a   the argument whose absolute value is to be determined
     * @return  the absolute value of the argument.
     */
    public static int abs(int a) {
        return (a < 0) ? -a : a;
    }

```

如果hash之后的结果恰巧就是 `Integer.MIN_VALUE` ，你就会发现你使用 `Math.abs` 之后它依然是个负数，数据量大的时候这种事情是一定会发生的（墨菲定律），而如果你的代码健壮性不够的话到后面就容易数组越界了。

基本上布隆过滤器的思想和精华就在这里了，实践和理论的确是存在些许实现上的差异，但是思想是吻合的。

类型：工作标签：布隆过滤器,算法