昨天前同事,来请教一个问题,如何对千万级的数据进行 重复数据判断;之前数据量不大的时候,一直使用hashset,现在数据量上来了,显然需要重构;我说“啥?还hashset,计算用Redis set也不能用hashset啊…”
大概场景是,每天需要监控司机的位置信息,位置信息可经基站数据转化成Long整数,数据量会达到千万级别,但其中不乏基站发送的重复数据,所以想去重,并且对精度要求也不是很高,偶尔的偏离位置也可以接受;
我一听,这不是标准的布隆过滤器的case么,不能再标准了…
布隆过滤器,说简单也很简单,底层就是一个很长的 0/1 bit数组,再加上几个 hash 函数;
介绍了算法,还需要提供实现思路,不然蹭不到饭的…
万能的Guave中就有布隆过滤器的实现,并且可以通过设置 误判百分比,来控制精准度:
源码就不一行行过了,但必须来看一下 Google 程序员的快乐!代码中的comments,哈哈!这只有读源码才能体会到的快乐!
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);
}
/*
* 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);