判断一个元素是否存在亿级数据中

2019-04-12

现在有一个非常庞大的数据，假设全是 int 类型。现在我给你一个数，你需要告诉我它是否存在其中(尽量高效)。

需求分析：只是要判断一个数据是否存在即可。但这里有一个比较重要的前提是非常庞大的数据。

常规实现

我想大多数想到的都是用 HashMap 来存放数据，因为它的写入查询的效率都比较高。

写入和判断元素是否存在都有对应的 API，所以实现起来也比较简单。

为此我写了一个单测，利用 HashSet 来存数据（底层也是 HashMap ）；同时为了后面的对比将堆内存写死：

1	-Xms64m -Xmx64m -XX:+PrintHeapAtGC -XX:+HeapDumpOnOutOfMemoryError

为了方便调试加入了 GC 日志的打印，以及内存溢出后 Dump 内存。

@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 数据试试：

执行后马上就内存溢出。

可见在内存有限的情况下我们不能使用这种方式。

实际情况也是如此；既然要判断一个数据是否存在于集合中，考虑的算法的效率以及准确性肯定是要把数据全部 load 到内存中的。

Bloom Filter 原理

官方：它是一个保存了很长的二级制向量，同时结合 Hash 函数实现的。

如图所示：

首先需要初始化一个二进制的数组，长度设为 L（图中为 8），同时初始值全为 0 。
当写入一个 A1=1000 的数据时，需要进行 H 次 hash 函数的运算（这里为 2 次）；与 HashMap 有点类似，通过算出的 HashCode与 L 取模后定位到 0、2 处，将该处的值设为 1。
A2=2000 也是同理计算后将 4、7 位置设为 1。
当有一个 B1=1000 需要判断是否存在时，也是做两次 Hash 运算，定位到 0、2 处，此时他们的值都为 1 ，所以认为 B1=1000 存在于集合中。
当有一个 B2=3000 时，也是同理。第一次 Hash 定位到 index=4 时，数组中的值为 1，所以再进行第二次 Hash 运算，结果定位到 index=5 的值为 0，所以认为 B2=3000 不存在于集合中。

布隆过滤有以下几个特点：

只要返回数据不存在，则肯定不存在。
返回数据存在，但只能是大概率存在。
同时不能清除其中的数据。

基于以上的 Hash 冲突的前提，所以 Bloom Filter 有一定的误报率，这个误报率和 Hash算法的次数 H，以及数组长度 L 都是有关的。

自己实现一个布隆过滤

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);
    }
}

首先初始化了一个 int 数组。
写入数据的时候进行三次 hash 运算，同时把对应的位置置为 1。
查询时同样的三次 hash 运算，取到对应的值，一旦值为 0 ，则认为数据不存在。

下面来测试一下，同样的参数：

1	-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 的数据同时做出来准确的判断。

总结

布隆过滤常应用在数据库、爬虫、Redis防缓存击穿等。