bloom_filter_simple

bloom_filter_simple 是一个库，提供了不同类型的数据结构过滤元素的实现。这种数据结构基于 Burton Howard Bloom 提出的想法，因此被称为布隆过滤器

Burton H. Bloom. 1970. 在允许错误的情况下，哈希编码的空间/时间权衡。ACM通讯 13, 7 (1970 年 7 月)，422–426. DOI: https://doi.org/10.1145/362686.362692

基本描述来自 维基百科

布隆过滤器是一种空间高效的概率数据结构，由 Burton Howard Bloom 在 1970 年提出，用于测试一个元素是否是集合的成员。可能存在误报，但不会出现漏报——换句话说，查询结果要么是“可能在集合中”，要么是“肯定不在集合中”。可以添加元素到集合中，但不能从中删除（尽管可以通过计数布隆过滤器变种来解决这个问题）；添加的元素越多，误报的概率就越大。（“布隆过滤器”。定义，第 1 段。在维基百科中检索，2020 年 12 月 2 日，来自 https://en.wikipedia.org/wiki/Bloom_filter）

布隆过滤器实现

该库提供了两种基本的布隆过滤器实现类型：KMBloomFilter 和 SeededBloomFilter。前者使用两个哈希函数，而后者仅使用一个哈希函数，但使用不同的种子生成不同的哈希值。

示例

下面是一些如何初始化和使用不同布隆过滤器类型的简单示例。

默认布隆过滤器

DefaultBloomFilter 的目的是易于入门。它是一个预配置的 KMBloomFilter，使用两个哈希函数，这些函数在我们的测试中已证明是足够的。

use bloom_filter_simple::{BloomFilter,DefaultBloomFilter};

fn main() {
    // We plan on storing at most 10 elements
    let desired_capacity = 10;

    // The chance of a false positive increases with each inserted element. This parameter
    // specifies that it should be less than 0.01% (0.0001) when the desired capacity has
    // been reached.
    // In other words, the chance that the bloom filter returns true when checking whether a
    // novel element has been inserted before is less than 0.01% (0.0001).
    let desired_fp_probability = 0.0001;

    let mut filter = DefaultBloomFilter::new(desired_capacity, desired_fp_probability);

    // You can insert any type implementing the Hash trait. The bloom filter does not store the
    // inserted elements but only their hashes. Hence, there is no transfer of ownership required.
    filter.insert(&5i32);
    filter.insert(&"Some text");
    filter.insert(&10_000usize);

    // You can check whether a value has been inserted into the filter before.
    assert_eq!(false, filter.contains(&3));
    assert_eq!(true, filter.contains(&5));
    assert_eq!(true, filter.contains(&"Some text"));
}

KMBloomFilter

KMBloomFilter 允许您选择要使用的哈希函数。

KMBloomFilter<AHasher, DefaultHasher> = KMBloomFilter::new(desired_capacity, desired_fp_probability);

SeededBloomFilter

SeededBloomFilter 无需配置，因为它使用仅一个特定的哈希函数，该函数会自动播种。

SeededBloomFilter::new(desired_capacity, desired_fp_probability);

更多

有关更多示例和详细信息，请参阅 文档。