Struct bloom2::CompressedBitmap

pub struct CompressedBitmap { /* fields omitted */ }

CompressedBitmap implements a sparse, 2 level bloom filter - a space efficient, probabilistic set.

Users of a CompressedBitmap call insert_hash with deterministic, unique hashes (a fingerprint) of their entries and check the existence of the entry by calling contains_hash.

use bloom2::{CompressedBitmap, FilterSize};

let mut filter = CompressedBitmap::new(FilterSize::KeyBytes2);

let data_hashes = vec![
    "bananas",
    "batman",
    "bintang",
];

for v in data_hashes.iter() {
    filter.insert_hash(v);
}

assert_eq!(filter.contains_hash("bananas"), true);
assert_eq!(filter.contains_hash("apples"), false);

The CompressedBitmap maintains the same false-positive properties and similar performance properties as a normal bloom filter while lazily initialising the backing memory as it is needed, resulting in smaller memory footprints for all except completely loaded filters.

Insertions are amortised O(1) and lookups are always O(1). The backing memory is lazily initialised by growing a std::vec::Vec, therefore it uses the same (undefined) allocation strategy to amortise the expansion of the backing memory - call shrink_to_fit to reduce the underlying memory allocation to the minimum required.

Methods

impl CompressedBitmap

pub fn new(key_byte_size: FilterSize) -> Self

Initialises a new, empty bloom filter configured to consume hashes in chunks of key_byte_size number of bytes to use as keys.

pub fn shrink_to_fit(&mut self)

Reduces the allocated memory usage of the filter to the minimum required for the current filter contents.

This is useful to minimise the memory footprint of a populated, read-only CompressedBitmap.

See Vec::shrink_to_fit.

pub fn clear(&mut self)

Resets the state of the filter.

An efficient way to remove all elements in the filter to allow it to be reused. Does not shrink the allocated backing memory, instead retaining the capacity to avoid reallocations.

pub fn insert_hash<T: AsRef<[u8]>>(&mut self, hash: T)

Inserts hash into the filter, chunking it into the configured key size.

Calling insert_hash with a hash length greater than the configured key size effectively increases the "hash" count, or k property of the filter.

pub fn contains_hash<T: AsRef<[u8]>>(&self, hash: T) -> bool

Checks if hash exists in the filter.

If contains_hash returns true, hash has probably been inserted previously. If contains_hash returns false, hash has definitely not been inserted into the filter.

Trait Implementations

impl Clone for CompressedBitmap

fn clone(&self) -> CompressedBitmap

Returns a copy of the value.

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

Performs copy-assignment from source.