Guava
英文原文：
Google Guava BloomFIlter
在 Guava 项目的11.0版中，一个新的类添加了进来—— BloomFilter（布隆过滤器）类。布隆过滤器是一种独特的数据结构，用以表明元素是否被保存在一个集合（Set）中。有趣的是，布隆过滤器能够明确指出元素
绝对不存在于一个集合中，或是
可能存在于一个集合中。由于布隆过滤器从不漏报的特性，使得它成为避免不必要和昂贵操作的约束条件的极好选择。 近来对布隆过滤器的关注开始增多，如要使用它，你可以自己写代码，也可以谷歌之。编写自己的布隆过滤器的问题在于使用正确的哈希函数来确保过滤器生效。鉴于 Guava 是使用 Murmur Hash 来实现的，仅需一个库，你就能获得这个非常有效的布隆过滤器。
布隆过滤器速成
布隆过滤器在本质上是二进制向量。在高层级上，布隆过滤器以下面的方式工作：
- 添加元素到过滤器。
- 对元素进行几次哈希运算，当索引匹配哈希的结果时，将该位设置为 1 的。
如果要检测元素是否属于集合，使用相同的哈希运算步骤，检查相应位的值是1还是0。这就是布隆过滤器明确元素不存在的过程。如果位未被设置，则元素绝不可能存在于集合中。当然，一个肯定的答案意味着，要不就是元素存在于集合中，要不就是遇见了哈希冲突。这里有一份很好的对布隆过滤器细节的描述，还有一份很好的教程。依据维基百科，谷歌在 BigTable 中使用了布隆过滤器，以避免在硬盘中寻找不存在的条目。另一个有趣的用法是使用布隆过滤器优化SQL查询。
其它翻译版本 (1)
加载中
使用 Guava 的布隆过滤器
Guava 的布隆过滤器通过调用 BloomFilter 类中的静态函数创建， 传递一个 Funnel 对象以及一个代表预期插入数量整数。同样来自于 Guava 11 中的 Funnel 对象，用于将数据发送给一个接收器（Sink）。 下面的例子是一个默认的实现，有着3%的误报率。Guava 提供的 Funnels 类拥有两个静态方法提供了将CharSequence 或byte数组插入到过滤器的 Funnel 接口的实现。
//Creating the BloomFilter
BloomFilter bloomFilter = BloomFilter.create(Funnels.byteArrayFunnel(), 1000);
//Putting elements into the filter
//A BigInteger representing a key of some sort
bloomFilter.put(bigInteger.toByteArray());
//Testing for element in set
boolean mayBeContained = bloomFilter.mayContain(bitIntegerII.toByteArray());
更新：根据来自 Louis Wasserman 的回复，下面是如何为 BigIntegers 创建一个带有自定义 Funnel 实现的布隆过滤器：
//Create the custom filter
class BigIntegerFunnel implements Funnel<BigInteger> {
@Override
public void funnel(BigInteger from, Sink into) {
into.putBytes(from.toByteArray());
}
}
//Creating the BloomFilter
BloomFilter bloomFilter = BloomFilter.create(new BigIntegerFunnel(), 1000);
//Putting elements into the filter
//A BigInteger representing a key of some sort
bloomFilter.put(bigInteger);
//Testing for element in set
boolean mayBeContained = bloomFilter.mayContain(bitIntegerII);
其它翻译版本 (1)
加载中
注意事项
正确估计预期插入数量是非常关键的。当插入的数量接近或高于预期值的时候，布隆过滤器将会填满，这样的话，它会产生很多无用的误报点。这里有另一个版本的 BloomFilter.create 方法，它额外接收一个参数，一个代表假命中概率水平的双精度数字（必须大于零且小于1）。假命中概率等级影响哈希表储存或搜索元素的数量。百分比越低，哈希表的性能越好。
总结
对于开发者来说，布隆过滤器是一件很有用的工具。Guava 项目能够让你在需要时更方便的使用布隆过滤器。我希望你喜欢这篇文章。希望听到您的意见或建议。
参考
本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接。
2KB翻译工作遵照
CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。
2KB项目（www.2kb.com，源码交易平台）,提供担保交易、源码交易、虚拟商品、在家创业、在线创业、任务交易、网站设计、软件设计、网络兼职、站长交易、域名交易、链接买卖、网站交易、广告买卖、站长培训、建站美工等服务
