雨翔河
首页
列表
关于
深入探讨布隆过滤器
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` 之后它依然是个负数,数据量大的时候这种事情是一定会发生的(墨菲定律),而如果你的代码健壮性不够的话到后面就容易数组越界了。 基本上布隆过滤器的思想和精华就在这里了,实践和理论的确是存在些许实现上的差异,但是思想是吻合的。
类型:工作
标签:布隆过滤器,算法
Copyright © 雨翔河
我与我周旋久
独孤影
开源实验室