当前位置: 首页 > 工具软件 > BLOOM > 使用案例 >

Bloom Filter - Guave

卫建义
2023-12-01

昨天前同事,来请教一个问题,如何对千万级的数据进行 重复数据判断;之前数据量不大的时候,一直使用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);
 类似资料:

相关阅读

相关文章

相关问答