Struct growable_bloom_filter::GrowableBloom [−][src]
pub struct GrowableBloom { /* fields omitted */ }
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));
Implementations
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
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));
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");
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
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);
The current estimated capacity of the filter. A filter starts with a capacity of 0 but 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);
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
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>,
Deserialize this value from the given Serde deserializer. Read more
This method tests for self
and other
values to be equal, and is used
by ==
. Read more
This method tests for !=
.
Auto Trait Implementations
impl RefUnwindSafe for GrowableBloom
impl Send for GrowableBloom
impl Sync for GrowableBloom
impl Unpin for GrowableBloom
impl UnwindSafe for GrowableBloom
Blanket Implementations
Mutably borrows from an owned value. Read more