Struct growable_bloom_filter::GrowableBloom

pub struct GrowableBloom { /* fields omitted */ }

A Growable Bloom Filter

Overview

Implementation of Scalable Bloom Filters which also provides serde serialization and deserialize.

A bloom filter lets you insert items, and then test association with contains. It's space and time efficient, at the cost of false positives. In particular, if contains returns true, it may be in filter. But if contains returns false, it's definitely not in the bloom filter.

You can control the failure rate by setting desired_error_prob and est_insertions appropriately.

Applications

Bloom filters are typically used as a pre-cache to avoid expensive operations. For example, if you need to ask ten thousand servers if they have data XYZ, you could use GrowableBloom to figure out which ones do NOT have XYZ.

Example

use serde_json;
use growable_bloom_filter::GrowableBloom;

let mut gbloom = GrowableBloom::new(0.05, 1000);
gbloom.insert(&0);
assert!(gbloom.contains(&0));

let s = serde_json::to_string(&gbloom).unwrap();
let des_gbloom: GrowableBloom = serde_json::from_str(&s).unwrap();
assert!(des_gbloom.contains(&0));

Methods

impl GrowableBloom

pub fn new(desired_error_prob: f64, est_insertions: usize) -> GrowableBloom

Create a new GrowableBloom filter.

Arguments

• desired_error_prob - The desired error probability (eg. 0.05, 0.01)
• est_insertions - The estimated number of insertions (eg. 100, 1000)

NOTE: You really don't need to be accurate with est_insertions. Power of 10 granularity should be fine.

Example

// 5% failure rate, estimated 100 elements to insert
use growable_bloom_filter::GrowableBloom;
let mut gbloom = GrowableBloom::new(0.05, 100);

Panics

Panics if desired_error_prob is less then 0 or greater than 1

pub fn contains<T: Hash>(&self, item: T) -> bool

Test if item in the Bloom filter.

If true is returned, it's may be in the filter. If false is returned, it's NOT in the filter.

Arguments

• item - The item to test

Example

use growable_bloom_filter::GrowableBloom;
let mut bloom = GrowableBloom::new(0.05, 10);
let item = 0;

bloom.insert(&item);
assert!(bloom.contains(&item));

pub fn insert<T: Hash>(&mut self, item: T)

Insert item into the filter.

This may resize the GrowableBloom.

Arguments

• item - The item to insert

Example

use growable_bloom_filter::GrowableBloom;
let mut bloom = GrowableBloom::new(0.05, 10);
let item = 0;

bloom.insert(&item);
bloom.insert(&-1);
bloom.insert(&vec![1, 2, 3]);
bloom.insert("hello");

Trait Implementations

impl Clone for GrowableBloom

fn clone(&self) -> GrowableBloom

Returns a copy of the value.

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

Performs copy-assignment from source.

impl PartialEq<GrowableBloom> for GrowableBloom

fn eq(&self, other: &GrowableBloom) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &GrowableBloom) -> bool

This method tests for !=.

impl Debug for GrowableBloom

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

Formats the value using the given formatter.

impl Serialize for GrowableBloom

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

Serialize this value into the given Serde serializer.

impl<'de> Deserialize<'de> for GrowableBloom

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.