Struct growable_bloom_filter::GrowableBloom
source · pub struct GrowableBloom { /* private fields */ }
Expand description
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 growable_bloom_filter::GrowableBloom;
// Create and insert into the bloom filter
let mut gbloom = GrowableBloom::new(0.05, 1000);
gbloom.insert(&0);
assert!(gbloom.contains(&0));
// Serialize and Deserialize the bloom filter
use serde_json;
let s = serde_json::to_string(&gbloom).unwrap();
let des_gbloom: GrowableBloom = serde_json::from_str(&s).unwrap();
assert!(des_gbloom.contains(&0));
// Builder API
use growable_bloom_filter::GrowableBloomBuilder;
let mut gbloom = GrowableBloomBuilder::new()
.estimated_insertions(100)
.desired_error_ratio(0.05)
.build();
gbloom.insert(&0);
assert!(gbloom.contains(&0));
Implementations§
source§impl GrowableBloom
impl GrowableBloom
sourcepub fn new(desired_error_prob: f64, est_insertions: usize) -> 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 (~1000 is decent).
§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.
- Panics if capacity is zero. If you’re unsure, set it to 1000.
§Builder API
An alternative way to construct a GrowableBloom.
See GrowableBloomBuilder
for documentation. It allows you to specify
other constants to control bloom filter behaviour.
use growable_bloom_filter::GrowableBloomBuilder;
let mut gbloom = GrowableBloomBuilder::new()
.estimated_insertions(100)
.desired_error_ratio(0.05)
.build();
sourcepub fn contains<T: Hash>(&self, item: T) -> bool
pub fn contains<T: Hash>(&self, item: T) -> bool
Test if item
in the Bloom filter.
If true
is returned, it 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));
sourcepub fn insert<T: Hash>(&mut self, item: T) -> bool
pub fn insert<T: Hash>(&mut self, item: T) -> bool
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");
sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Clear the bloom filter.
This does not resize the filter.
§Example
use growable_bloom_filter::GrowableBloom;
let mut bloom = GrowableBloom::new(0.05, 10);
let item = 0;
bloom.insert(&item);
assert!(bloom.contains(&item));
bloom.clear();
assert!(!bloom.contains(&item)); // No longer contains item
sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
The current estimated number of elements added to the filter. This is an estimation, so it may or may not increase after an insertion in the filter.
§Example
use growable_bloom_filter::GrowableBloom;
let mut bloom = GrowableBloom::new(0.05, 10);
bloom.insert(0);
assert_eq!(bloom.len(), 1);
sourcepub fn capacity(&self) -> usize
pub fn capacity(&self) -> usize
The current estimated capacity of the filter. A filter starts with a small capacity and will expand to accommodate more items. The actual ratio of increase depends on the values used to construct the bloom filter.
Note: An empty filter has capacity zero as we haven’t calculated the necessary bloom filter size. Subsequent inserts will result in the capacity updating.
§Example
use growable_bloom_filter::GrowableBloom;
let mut bloom = GrowableBloom::new(0.05, 10);
assert_eq!(bloom.capacity(), 0);
bloom.insert(0);
// After an insert, our capacity is no longer zero.
assert_ne!(bloom.capacity(), 0);
sourcepub fn check_and_set<T: Hash>(&mut self, item: T) -> bool
pub fn check_and_set<T: Hash>(&mut self, item: T) -> bool
Record if item
already exists in the filter, and insert it if it doesn’t already exist.
Returns true
if the item already existed in the filter.
Note: This isn’t faster than just inserting.
§Example
use growable_bloom_filter::GrowableBloom;
let mut bloom = GrowableBloom::new(0.05, 10);
let item = 0;
let existed_before = bloom.check_and_set(&item);
assert!(existed_before == false);
let existed_before = bloom.check_and_set(&item);
assert!(existed_before == true);
Trait Implementations§
source§impl Clone for GrowableBloom
impl Clone for GrowableBloom
source§fn clone(&self) -> GrowableBloom
fn clone(&self) -> GrowableBloom
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl Debug for GrowableBloom
impl Debug for GrowableBloom
source§impl<'de> Deserialize<'de> for GrowableBloom
impl<'de> Deserialize<'de> for GrowableBloom
source§fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
source§impl PartialEq for GrowableBloom
impl PartialEq for GrowableBloom
source§fn eq(&self, other: &GrowableBloom) -> bool
fn eq(&self, other: &GrowableBloom) -> bool
self
and other
values to be equal, and is used
by ==
.source§impl Serialize for GrowableBloom
impl Serialize for GrowableBloom
impl StructuralPartialEq for GrowableBloom
Auto Trait Implementations§
impl Freeze for GrowableBloom
impl RefUnwindSafe for GrowableBloom
impl Send for GrowableBloom
impl Sync for GrowableBloom
impl Unpin for GrowableBloom
impl UnwindSafe for GrowableBloom
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)