Struct BloomFilter

pub struct BloomFilter { /* private fields */ }

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not.

Reference: Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422-426. Full text article

Implementations

impl BloomFilter

pub fn new(config: FilterBuilder) -> Self

Build a Bloom filter form FilterBuilder.

Examples:

use fastbloom_rs::{BloomFilter, FilterBuilder};

let builder = FilterBuilder::new(100_000_000, 0.01);
let bloom = BloomFilter::new(builder);

pub fn add_if_not_contains(&mut self, element: &[u8]) -> bool

Tests whether an element is present in the filter (subject to the specified false positive rate). And if it is not in this filter, add it to the filter.

pub fn from_file_with_hashes(path: &str) -> Self

Build a Bloom filter from file with first four bytes is hashes which is encode by big-endian. The remaining is underlying byte vector of the Bloom filter.

pub fn from_file(path: &str, hashes: u32) -> Self

Build a Bloom filter from file. The content is underlying byte vector of the Bloom filter.

pub fn from_u8_array(array: &[u8], hashes: u32) -> Self

Build a Bloom filter form &[u8].

Examples

use fastbloom_rs::BloomFilter;
let mut array = vec![0u8; 4096];
let bloom = BloomFilter::from_u8_array(array.as_bytes(), 4);

pub fn from_u16_array(array: &[u16], hashes: u32) -> Self

Build a Bloom filter form &[u16].

Examples

use fastbloom_rs::BloomFilter;
let mut array = vec![0u16; 2048];
let bloom = BloomFilter::from_u16_array(array.as_bytes(), 4);

pub fn from_u32_array(array: &[u32], hashes: u32) -> Self

Build a Bloom filter form &[u32].

Examples

use fastbloom_rs::BloomFilter;
let mut array = vec![0u32; 1024];
let bloom = BloomFilter::from_u32_array(array.as_bytes(), 4);

pub fn from_u64_array(array: &[u64], hashes: u32) -> Self

Build a Bloom filter form &[u64].

Examples

use fastbloom_rs::BloomFilter;
let mut array = vec![0u64; 512];
let bloom = BloomFilter::from_u32_array(array.as_bytes(), 4);

pub fn config(&self) -> FilterBuilder

Returns the configuration/builder of the Bloom filter.

Examples

use fastbloom_rs::{BloomFilter, FilterBuilder};

let bloom = FilterBuilder::new(100_000_000, 0.01).build_bloom_filter();
let builder = bloom.config();

pub fn save_to_file_with_hashes(&mut self, path: &str)

Save the bloom filter to file, and the first four bytes is hashes with big-endian, and the remaining bytes is underlying byte vector of the Bloom filter.

pub fn save_to_file(&mut self, path: &str)

Save the bloom filter to file, and the content of the file is underlying byte vector of the Bloom filter.

pub fn get_u8_array(&self) -> &[u8]

Return the underlying byte vector of the Bloom filter.

pub fn get_u16_array(&self) -> &[u16]

Return the underlying u16 vector of the Bloom filter.

pub fn get_u32_array(&self) -> &[u32]

Return the underlying u32 vector of the Bloom filter.

pub fn get_u64_array(&self) -> &[u64]

Return the underlying u64 vector of the Bloom filter.

pub fn union(&mut self, other: &BloomFilter) -> bool

Performs the union operation on two compatible bloom filters. This is achieved through a bitwise OR operation on their bit vectors. This operations is lossless, i.e. no elements are lost and the bloom filter is the same that would have resulted if all elements wer directly inserted in just one bloom filter.

pub fn intersect(&mut self, other: &BloomFilter) -> bool

Performs the intersection operation on two compatible bloom filters. This is achieved through a bitwise AND operation on their bit vectors. The operations doesn’t introduce any false negatives but it does raise the false positive probability. The the false positive probability in the resulting Bloom filter is at most the false-positive probability in one of the constituent bloom filters

pub fn is_empty(&self) -> bool

Returns true if the Bloom filter does not contain any elements

pub fn estimate_set_cardinality(&self) -> f64

Returns estimated cardinality of the set see Scalable and Efficient Privacy Preserving Global Itemset Support Approximation Using Bloom Filters as reference

Trait Implementations

impl Clone for BloomFilter

fn clone(&self) -> BloomFilter

Returns a duplicate of the value.

const fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BloomFilter

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Hashes for BloomFilter

fn hashes(&self) -> u32

Returns the hash function number of the Bloom filter.

impl Membership for BloomFilter

fn add(&mut self, element: &[u8])

Adds the passed value to the filter.

fn contains(&self, element: &[u8]) -> bool

Tests whether an element is present in the filter (subject to the specified false positive rate).

fn get_hash_indices(&self, element: &[u8]) -> Vec<u64>

Get the hashes indices of the element in the filter.

fn contains_hash_indices(&self, indices: &Vec<u64>) -> bool

Tests whether a hashes indices is present in the filter

fn clear(&mut self)

Removes all elements from the filter (i.e. resets all bits to zero).