Gauze

具有简单界面的概率集合成员资格过滤器集合。这些过滤器可以声称给定的条目

• 肯定不在条目集合中表示，或者
• 可能在该集合中表示。

此包正在开发中，目前仅实现 Bloom 过滤器。

如果需要，扩展特质 DynFilter 使 insert 和 contains 的动态分发变体成为对象安全。

实际应用中的 Gauze

一个简单的 Bloom 过滤器实现如下

use gauze::{BloomFilter, Filter};

fn main() {
    // The number of items we want the `BloomFilter` to store
    // while not returning too many false positives
    let capacity = 100_000;
    // The rate of false positives the `BloomFilter` is allowed
    // to return if it stores no more than `capacity` items
    let target_err_rate = 0.001;
    // These parameters allow us to construct a `BloomFilter` with
    // *approximately* optimal properties
    let mut bloom =
        BloomFilter::new(capacity, target_err_rate)
        .expect("couldn't construct Bloom filter.");

    // `BloomFilter`s can add any type that is `impl Hash`
    bloom.insert(1);
    bloom.insert("a");
    bloom.insert(Vec::<bool>::new());
    bloom.insert([0; 2]);

    // Querying whether a `BloomFilter` contains an element
    // never yields a false negative
    let inserts = capacity - 4;
    for i in 0..inserts {
        bloom.insert(i);
    }

    let mut false_negatives = 0;
    for i in 0..inserts{
        if !bloom.contains(i) {
            false_negatives += 1;
        }
    }
    println!("False negatives: {false_negatives}");

    // But it can yield some false positives
    let mut false_positives = 0;
    for i in 0..inserts{
        if bloom.contains(inserts + i) {
            false_positives += 1;
        }
    }
    println!("False positives: {false_positives}");
    
    // It is possible to get an *approximation* of the number of
    // `item`s stored in the `BloomFilter`
    let stored_items_approx = bloom.count_approx();
    println!("Approximately count of items stored: {stored_items_approx}");
    
    // Items can't be removed. But the `BloomFilter` can be reset.
    bloom.reset();

    // We can also get some properties of the `BloomFilter` itself
    println!("Number of bits for the actual filter: {}", bloom.bit_count());
    println!("Number of hash functions used: {}", bloom.hash_fn_count());
    println!("The filter's actual error rate: {}", bloom.error_rate());
}

许可证

本项目许可协议为 MIT。