rsbloom  

一个空间效率高的布隆过滤器简单实现。

布隆过滤器

布隆过滤器是一种空间效率高的概率数据结构，用于测试一个元素是否是集合的成员。它允许查询返回：“可能在集合中”或“肯定不在集合中”。元素可以添加到集合中，但不能删除；添加到集合中的元素越多，误报的概率就越大。已经证明，对于1%的误报概率，每个元素只需要不到10位，独立于集合的大小或元素的数量。

提供的实现允许您创建一个布隆过滤器，指定预期的插入项的大致数量和可选的误报概率。它还允许您估算过滤器中的总项目数量。

增强的双哈希

增强的双哈希用于在位向量中设置位的位置。Adam Kirsch和Michael Mitzenmacher在Less Hashing, Same Performance: Building a Better Bloom Filter中展示了双哈希的选择是有效的，不会损失渐进误报概率，从而减少了计算，并可能在实践中减少对随机性的需求。

增强的双哈希采用以下公式

g_i(x) = (H₁(x) + iH₂(x) + f(i)) mod m, 其中

H₁ 是 Murmur3 128位，H₂ 是 xxHash 64位，f(i) = i³

使用方法

将 rsbloom 依赖项添加到您的 Cargo.toml

[dependencies]
rsbloom = "0.1.0"

示例

use rsbloom::BloomFilter;

fn main() {
  let approx_items = 100;
  let mut bf = BloomFilter::new(approx_items);

  bf.set(&"foo");
  bf.set(&"bar");

  bf.has(&"foo"); // true
  bf.has(&"bar"); // true
  bf.has(&"baz"); // false

  bf.num_items_approx(); // 2
}

测试

make test

基准测试

make bench