Bloom Filter - Guave

昨天前同事，来请教一个问题，如何对千万级的数据进行 重复数据判断；之前数据量不大的时候，一直使用hashset，现在数据量上来了，显然需要重构；我说“啥？还hashset，计算用Redis set也不能用hashset啊…”

大概场景是，每天需要监控司机的位置信息，位置信息可经基站数据转化成Long整数，数据量会达到千万级别，但其中不乏基站发送的重复数据，所以想去重，并且对精度要求也不是很高，偶尔的偏离位置也可以接受；

我一听，这不是标准的布隆过滤器的case么，不能再标准了…

什么是布隆过滤器

布隆过滤器，说简单也很简单，底层就是一个很长的 0/1 bit数组，再加上几个 hash 函数；

• 数据插入：当新添加一个元素的时候，会对元素依次应用hash函数，并计算出在数组中对应的index位置，标记1；所以一个元素，会对应几个index位置为1
• 数据查找：当超找一个元素的时候，也对其应用hash函数，如果对应位置的value有一个为0，那就说明这个元素肯定不存在；但是如果对应的位置都为1，只能说明，这个元素可能存在，毕竟是hash函数取模，还是会遇到hash碰撞问题的… 也就是会造成一定误判

介绍了算法，还需要提供实现思路，不然蹭不到饭的…

万能的Guave中就有布隆过滤器的实现，并且可以通过设置 误判百分比，来控制精准度：

读源码快乐

源码就不一行行过了，但必须来看一下 Google 程序员的快乐！代码中的comments，哈哈！这只有读源码才能体会到的快乐！

1. homie 呦呦check now

public double expectedFpp() {
    // You down with FPP? (Yeah you know me!) Who's down with FPP? (Every last homie!)
    return Math.pow((double) bits.bitCount() / bitSize(), numHashFunctions);
  }
           

1. who cares! 好像这老哥有点暴脾气，不知道现在是不是已经离职了

/*
 * optimalM(1000, 0.0000000000000001) = 76680 which is less than 10kb. Who cares!
 */
long numBits = optimalNumOfBits(expectedInsertions, fpp);
           

简单使用

代码很简单，只需简单的设置下 FPP，即允许误判率即可，下面设置的是 0.01 基本可以了，没必要再低了，不然会影响性能；

Long clientSize = 1000_0000L;
    double fpp = 0.01; // false positive probability

    //thread safe
    BloomFilter<Long> bloomFilter = BloomFilter.create(Funnels.longFunnel(), clientSize, fpp);

    for(long i=0; i<clientSize; i++){
        bloomFilter.put(i);
    }

    int bad = 0;
    for(long i=clientSize; i<clientSize + 1000; i++){
        if(bloomFilter.mightContain(i)) bad++;
    }
    System.out.println(bad);