Lib.rs

rust-bloomfilter

布隆过滤器由 4 个相互依赖的值定义

• n - 过滤器中的项目数量
• p - 假正例的概率，介于 0 和 1 之间，或者表示 1/p 的数字
• m - 过滤器中的位数
• k - 哈希函数的数量

参数选择指南

这些值是相互依赖的，如下所示的计算

m = ceil((n * log(p)) / log(1.0 / (pow(2.0, log(2.0)))));

k = round(log(2.0) * m / n);

设计

我使用 murmur3 哈希生成 128 位哈希整数，然后将其分成两个 64 位的整数。以下是为布隆过滤器设计编写的伪代码。

let hash_128 = murmur3_hash(data);
let first_64 = (hash_128 & (2_u128.pow(64) - 1));
let second_64 = hash >> 64;
for i 0..num_of_hashfuncs{
    first_64 += i* second_64;
    index =  fist_64 % number_of_bits
    self.bitvec.set(index, true);
}

用法

extern crate rust_bloomfilter;

use rust_bloomfilter::BloomFilter;

let mut b = BloomFilter(20000, 0.01, true);
b.add("Helloworld");
assert!(b.contains("Helloworld"));