前言最近有朋友问我这么一个面试题目:
需求其实很清晰,只是要判断一个数据是否存在即可。 但这里有一个比较重要的前提:非常庞大的数据。 常规实现先不考虑这个条件,我们脑海中出现的第一种方案是什么? 我想大多数想到的都是用 写入和判断元素是否存在都有对应的 为此我写了一个单测,利用 -Xms64m -Xmx64m -XX: PrintHeapAtGC -XX: HeapDumpOnOutOfMemoryError 复制代码 为了方便调试加入了 @Test public void hashMapTest(){ long star = System.currentTimeMillis(); Set<Integer> hashset = new HashSet<>(100) ; for (int i = 0; i < 100; i ) { hashset.add(i) ; } Assert.assertTrue(hashset.contains(1)); Assert.assertTrue(hashset.contains(2)); Assert.assertTrue(hashset.contains(3)); long end = System.currentTimeMillis(); System.out.println("执行时间:" (end - star)); } 复制代码 当我只写入 100 条数据时自然是没有问题的。 还是在这个基础上,写入 1000W 数据试试: 执行后马上就内存溢出。 可见在内存有限的情况下我们不能使用这种方式。 实际情况也是如此;既然要判断一个数据是否存在于集合中,考虑的算法的效率以及准确性肯定是要把数据全部 Bloom Filter基于上面分析的条件,要实现这个需求最需要解决的是 而我们是否可以换种思路,因为只是需要判断数据是否存在,也不是需要把数据查询出来,所以完全没有必要将真正的数据存放进去。 伟大的科学家们已经帮我们想到了这样的需求。
它主要就是用于解决判断一个元素是否在一个集合中,但它的优势是只需要占用很小的内存空间以及有着高效的查询效率。 所以在这个场景下在合适不过了。 Bloom Filter 原理下面来分析下它的实现原理。
听起来比较绕,但是通过一个图就比较容易理解了。 如图所示:
整个的写入、查询的流程就是这样,汇总起来就是:
所以布隆过滤有以下几个特点:
第一点应该都能理解,重点解释下 2、3 点。 为什么返回存在的数据却是可能存在呢,这其实也和 在有限的数组长度中存放大量的数据,即便是再完美的 Hash 算法也会有冲突,所以有可能两个完全不同的 这时拿 B 进行查询时那自然就是误报了。 删除数据也是同理,当我把 B 的数据删除时,其实也相当于是把 A 的数据删掉了,这样也会造成后续的误报。 基于以上的 自己实现一个布隆过滤算法其实很简单不难理解,于是利用 public class BloomFilters { /** * 数组长度 */ private int arraySize; /** * 数组 */ private int[] array; public BloomFilters(int arraySize) { this.arraySize = arraySize; array = new int[arraySize]; } /** * 写入数据 * @param key */ public void add(String key) { int first = hashcode_1(key); int second = hashcode_2(key); int third = hashcode_3(key); array[first % arraySize] = 1; array[second % arraySize] = 1; array[third % arraySize] = 1; } /** * 判断数据是否存在 * @param key * @return */ public boolean check(String key) { int first = hashcode_1(key); int second = hashcode_2(key); int third = hashcode_3(key); int firstIndex = array[first % arraySize]; if (firstIndex == 0) { return false; } int secondIndex = array[second % arraySize]; if (secondIndex == 0) { return false; } int thirdIndex = array[third % arraySize]; if (thirdIndex == 0) { return false; } return true; } /** * hash 算法1 * @param key * @return */ private int hashcode_1(String key) { int hash = 0; int i; for (i = 0; i < key.length(); i) { hash = 33 * hash key.charAt(i); } return Math.abs(hash); } /** * hash 算法2 * @param data * @return */ private int hashcode_2(String data) { final int p = 16777619; int hash = (int) 2166136261L; for (int i = 0; i < data.length(); i ) { hash = (hash ^ data.charAt(i)) * p; } hash = hash << 13; hash ^= hash >> 7; hash = hash << 3; hash ^= hash >> 17; hash = hash << 5; return Math.abs(hash); } /** * hash 算法3 * @param key * @return */ private int hashcode_3(String key) { int hash, i; for (hash = 0, i = 0; i < key.length(); i) { hash = key.charAt(i); hash = (hash << 10); hash ^= (hash >> 6); } hash = (hash << 3); hash ^= (hash >> 11); hash = (hash << 15); return Math.abs(hash); } } 复制代码
实现逻辑其实就和上文描述的一样。 下面来测试一下,同样的参数: -Xms64m -Xmx64m -XX: PrintHeapAtGC 复制代码 @Test public void bloomFilterTest(){ long star = System.currentTimeMillis(); BloomFilters bloomFilters = new BloomFilters(10000000) ; for (int i = 0; i < 10000000; i ) { bloomFilters.add(i "") ; } Assert.assertTrue(bloomFilters.check(1 "")); Assert.assertTrue(bloomFilters.check(2 "")); Assert.assertTrue(bloomFilters.check(3 "")); Assert.assertTrue(bloomFilters.check(999999 "")); Assert.assertFalse(bloomFilters.check(400230340 "")); long end = System.currentTimeMillis(); System.out.println("执行时间:" (end - star)); } 复制代码 执行结果如下: 只花了 3 秒钟就写入了 1000W 的数据同时做出来准确的判断。 当让我把数组长度缩小到了 100W 时就出现了一个误报, 这也体现了 我们提高数组长度以及 Guava 实现刚才的方式虽然实现了功能,也满足了大量数据。但其实观察 总的来说就是内存利用率做的不好。 其实 Google Guava 库中也实现了该算法,下面来看看业界权威的实现。 -Xms64m -Xmx64m -XX: PrintHeapAtGC 复制代码 @Test public void guavaTest() { long star = System.currentTimeMillis(); BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 10000000, 0.01); for (int i = 0; i < 10000000; i ) { filter.put(i); } Assert.assertTrue(filter.mightContain(1)); Assert.assertTrue(filter.mightContain(2)); Assert.assertTrue(filter.mightContain(3)); Assert.assertFalse(filter.mightContain(10000000)); long end = System.currentTimeMillis(); System.out.println("执行时间:" (end - star)); } 复制代码 也是同样写入了 1000W 的数据,执行没有问题。 观察 GC 日志会发现没有一次 源码分析那就来看看 构造方法中有两个比较重要的参数,一个是预计存放多少数据,一个是可以接受的误报率。 我这里的测试 demo 分别是 1000W 以及 0.01。
这个算法计算规则可以参考维基百科。 put 写入函数真正存放数据的
bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize); 复制代码 其实也是 重点是 其实 set 方法是 利用了一个 所以
mightContain 是否存在函数前面几步的逻辑都是类似的,只是调用了刚才的 总结布隆过滤的应用还是蛮多的,比如数据库、爬虫、防缓存击穿等。 特别是需要精确知道某个数据不存在时做点什么事情就非常适合布隆过滤。 这段时间的研究发现算法也挺有意思的,后续应该会继续分享一些类似的内容。 如果对你有帮助那就分享一下吧。 |
|