Guava BloomFilter 实现

Guava BloomFilter 实现

Guava BloomFilter 改进点

  1. 重写了 bitset,可以参见 LockFreeBitArray类的实现 ,突破了int.maxsize 大约21亿的限制
  2. 采用MurmurHash3 非加密型哈希函数,对大块的数据,具有较高的平衡性与低碰撞率。en.wikipedia.org100w字符串hash,1s+
  3. 论文Less Hashing, Same Performance!Building a Better Bloom Filter,提到只需要两个;论文用google翻译了一部分,见
  4. 32位散列函数这个技巧并不会显着降低Bloom过滤器的性能;guava 具体做法见 BloomFilterStrategies 类的MURMUR128_MITZ_32MURMUR128_MITZ_64两种策略的实现
  5. 添加元素过程中,并非执行了 optimalNumOfHashFunctions 次hash 操作,改为一次MurmurHash3,和optimalNumOfHashFunctions次基础运算,大大减少了计算次数,提高了性能
  6. BloomFilter 一直被标记为@Beta,但已经在google很多产品中得到运用

Bloom Filter 概念和原理

  Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

  Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。

适用场景

  • 黑名单
  • 爬虫重复URL检测
  • 字典纠缠
  • 磁盘文件检测
  • CDN(squid)代理缓存技术

以爬虫重复URL举例:

  假设要你写一个网络蜘蛛(web crawler)。由于网络间的链接错综复杂,蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道蜘蛛已经访问过那些URL。给一个URL,怎样知道蜘蛛是否已经访问过呢?稍微想想,就会有如下几种方案:

  1. 将访问过的URL保存到数据库。

  2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。

  3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。

  4. Bit-Map方法。建立一个BitSet,将每个URL经过一个哈希函数映射到某一位。

  方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。
  
以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。


Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×