关于 Bloom Filter 的原理不做介绍，网上各种资料满天飞，其中参考资料 1 已经讲解的很详细。
我重点关注如何用 Rust 实现一个简单的 Bloom Filter，并学习一些语法，源码在参考资料 2 。
BloomFilter 结构体
pub struct BloomFilter<T> {
hasher: T,
k: u32,
bit_vec: BitVec,
insert_count: u64,
}
- 尖括号中的 T 代表泛型，这样我们就可以使用不同的 hash 函数实现 （hasher）
- k 表示使用几个 hash 函数，根据 BF 的原理，使用多个 hash 能减少 False Positive
- bit vec 表示使用一个多大的 bit 数组，这个关系到 BF 的命中率和 FP 率
BitVec 的作用等于是实现了 bloom filter 的 bit array，直接用这个库省略了作者重复实现一个。
定义 BloomHasher
定义这个 trait 的目的是让所有的 hash 函数库都有 hash() 这个函数，方便在上面的 hasher 中调用。
因为通常，不同的函数库有不同的调用方法名字，定义这个 trait 之后，为每个函数库实现 BloomHasher，这样对于所有的库函数都有了 hash()。
pub trait BloomHasher {
/// Returns the hashed value of the bytes given some seed.
#[inline]
fn hash(&self, seed: u32, bytes: &[u8]) -> u32;
}
/// A unit struct for the murmur3 hash function.
pub struct Murmur3;
impl BloomHasher for Murmur3 {
fn hash(&self, seed: u32, bytes: &[u8]) -> u32 {
let mut cursor = Cursor::new(bytes);
murmur3_32(cursor.by_ref(), seed)
}
}
在这个例子中用的 hash 函数是 Murmur3::murmur3_32, 从他的名字可以看出，返回结果是一个 u32 类型，也就是说，任意的输入可以获得一个 u32 的输出，并且同样的输入，加上不同的seed，也会得到不同的结果。
比如下面这个例子
extern crate murmur3;
use std::io::Cursor;
use murmur3::murmur3_32;
fn main() {
println!("seed = 0, result = {}", murmur3_32(&mut Cursor::new("hello world"), 0));
println!("seed = 1, result = {}", murmur3_32(&mut Cursor::new("hello world"), 1));
}
实现 Bloom Filter
接下来就是正题了，为 BloomFilter 结构体实现方法。
impl<T: BloomHasher> BloomFilter<T> {
pub fn insert(&mut self, bytes: &[u8]) {
for seed in 0..self.k {
let hash = self.hasher.hash(seed, bytes) as usize % self.bit_vec.len();
self.bit_vec.set(hash, true);
}
self.insert_count += 1;
}
}
pub fn contains<B: AsRef<[u8]>>(&self, bytes: B) -> bool {
for seed in 0..self.k {
let hash = self.hasher.hash(seed, bytes.as_ref()) as usize % self.bit_vec.len();
if !self.bit_vec[hash] {
return false;
}
}
true
}
}
理解了 bitvec 和 murmur3 库函数的用法后，再看上面的实现就非常简单了。
其中一个语法知识点是 impl 后面声明 T，这样 Rust 就知道 BloomFilter<T> 的尖括号中的类型是泛型而不是具体类型
, 从而在 BloomFilter<T> 上实现的方法中就可以使用它了。