Struct ofilter::Bloom

pub struct Bloom<T> { /* private fields */ }

Bloom filter.

This is a basic Bloom filter, using SipHasher13 hash funcs. It can be fine-tuned by passing custom parameters when being initialized. The default constructor uses a false positive rate of 1% and 2 hash functions.

Heavily inspired from bloomfilter crate.

Examples

use ofilter::Bloom;
use std::hash::Hash;

#[derive(Hash)]
struct Obj {
    some: usize,
    thing: usize,
}

let mut filter: Bloom<Obj> = Bloom::new(100);
let obj = Obj{ some: 1, thing: 2};

assert!(!filter.check(&obj)); // object is not in filter
filter.set(&obj);             // put object in filter
assert!(filter.check(&obj));  // object is in filter

Implementations

impl<T> Bloom<T>

pub fn new(capacity: usize) -> Self

Create a new Bloom filter, with given capacity.

All other parameters are set to defaults, or aligned to match capacity.

This type of filter is useful to maintain a set of max capacity items. It can have false positives but no false negatives. This means you can be sure that an item does NOT belong to the set, but only have a clue whether the item is in the set or not.

Examples

use ofilter::Bloom;

let filter: Bloom<usize> = Bloom::new(100);
assert_eq!(100, filter.capacity());

pub fn new_with_params(params: Params) -> Self

Create a new Bloom filter, with specific parameters.

Examples

use ofilter::{Bloom, Params};

let filter: Bloom<usize> = Bloom::new_with_params(Params::with_nb_items_and_fp_rate(100, 0.1));
assert_eq!(100, filter.capacity());

pub fn params(&self) -> Params

Get filter params.

This can be useful because when creating the filter, the .adjust() func is called, and may decide to fine-tune some parameters. With this, one can know exactly what is used by the filter.

Examples

use ofilter::Bloom;

let filter: Bloom<usize> = Bloom::new(100);
println!("{}", filter.params());

pub fn capacity(&self) -> usize

Get filter capacity.

Returns the value of params.nb_items, that is the number of items the filter is designed for.

use ofilter::{Bloom, Params};

let filter: Bloom<usize> = Bloom::new_with_params(Params::with_bit_len(1_000_000));
assert_eq!(52681, filter.capacity());

pub fn clear(&mut self)

Clear the filter.

Clears the bit vector, but keeps parameters.

use ofilter::Bloom;

let mut filter: Bloom<usize> = Bloom::new(1_000);
filter.set(&10);
assert!(filter.check(&10));
filter.clear();
assert!(!filter.check(&10));

pub fn is_empty(&self) -> bool

Returns true if filter is empty.

use ofilter::Bloom;

let mut filter: Bloom<usize> = Bloom::new(1_000);
assert!(filter.is_empty());
filter.set(&10);
assert!(!filter.is_empty());

pub fn fp_rate(&self) -> f64

Returns the current false positive rate.

In theory the false positive rate fp_rate is known at filter creation. But that, is the theoretical fp_rate that the filter reaches when it is “wasted” because it has too many entries. Until then, it performs better than that, statistically.

This function returns the actual false positive rate. When this value is greater than the fp_rate from the parameters, one should not continue to add items to the filter.

use ofilter::Bloom;

let mut filter: Bloom<usize> = Bloom::new(1_000);
assert_eq!(0.0, filter.fp_rate());
filter.set(&10);
assert!(filter.fp_rate() > 0.0); // will be params.fp_rate when filter is full

pub fn level(&self) -> f64

Returns the ratio between real fp_rate, and theoretical fp_rate.

This is a helper to quickly compare the real fp_rate, given how filled the filter is, and the theoretical fp_rate.

When this value is greater than 1.0, one should not continue to add items to the filter.

use ofilter::Bloom;

let mut filter: Bloom<usize> = Bloom::new(1_000);
assert_eq!(0.0, filter.level());
filter.set(&10);
assert!(filter.level() > 0.0); // will be 1.0 when filter is full

pub fn is_ok(&self) -> bool

Returns true if there is still room in the filter.

This is a helper which returns true if the actual fp_rate is lower than the theoretical fp_rate.

When this is false, one should not continue to add items to the filter.

use ofilter::Bloom;

let mut filter: Bloom<usize> = Bloom::new(1_000);
assert_eq!(0.0, filter.level());
filter.set(&10);
assert!(filter.level() > 0.0); // will be 1.0 when filter is full

pub fn count_ones(&self) -> usize

Returns the number of ones in the bit vector.

By comparing this number with the size of the bit vector, one can estimate how “filled” the filter is.

use ofilter::Bloom;

let mut filter: Bloom<usize> = Bloom::new(1_000_000);
assert_eq!(0, filter.count_ones());
filter.set(&10);
assert_eq!(2, filter.count_ones());

pub fn export(&self) -> &BitVec

Export the underlying bit vector.

use ofilter::Bloom;

let mut filter: Bloom<usize> = Bloom::new(1_000_000);
let bit_vec = filter.export();
println!("{:?}", bit_vec);

pub fn import(&mut self, src: &BitVec)

Import the underlying bit vector.

use ofilter::Bloom;
use bitvec::prelude::BitVec;

let mut filter: Bloom<usize> = Bloom::new(1_000_000);
let mut bit_vec = BitVec::new();
bit_vec.resize(100, false);
bit_vec.set(42, true);
filter.import(&bit_vec); // safe to call even is sizes mismatch

impl<T> Bloom<T>

where T: Hash,

pub fn set(&mut self, item: &T)

Record an item in the set.

Once this has been called, any call to check() will return true, as there are no false negatives. However some other items may test positive as a consequence of recording this one.

use ofilter::Bloom;

let mut filter: Bloom<usize> = Bloom::new(1_000);
filter.set(&42);

pub fn check(&self, item: &T) -> bool

Guess whether an item is likely to be in the set.

If set() has been called before with value, then this returns true, as there are no false negatives. However it may respond true even if the item has never been recorded in the set.

use ofilter::Bloom;

let mut filter: Bloom<usize> = Bloom::new(1_000);
filter.set(&42);
assert!(filter.check(&42));

pub fn check_and_set(&mut self, item: &T) -> bool

Record an item in the set and returns its previous value.

Equivalent to calling get() then set() but performs hash lookup only once so it’s a bit more efficient.

use ofilter::Bloom;

let mut filter: Bloom<usize> = Bloom::new(1_000);
assert!(!filter.check_and_set(&42));
assert!(filter.check(&42));

Trait Implementations

impl<T: Clone> Clone for Bloom<T>

fn clone(&self) -> Bloom<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for Bloom<T>

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

Formats the value using the given formatter.

impl<'de, T> Deserialize<'de> for Bloom<T>

where T: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<T> Display for Bloom<T>

Pretty-print the filter.

Examples

use ofilter::Bloom;

let filter: Bloom<usize> = Bloom::new(100);

assert_eq!("{ fp_rate: 0.000000, params: { nb_hash: 2, bit_len: 1899, nb_items: 100, fp_rate: 0.009992, predict: false } }" , format!("{}", filter));

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

Formats the value using the given formatter.

impl<T> Serialize for Bloom<T>

where T: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.