Struct CuckooFilter 

pub struct CuckooFilter<T: ?Sized, S = DefaultHashBuilder> { /* private fields */ }

Available on crate feature alloc only.

A probabilistic set that supports deletion.

Like a BloomFilter, a Cuckoo filter answers approximate membership queries in a fraction of the memory an exact set would need, and never reports a false negative for an item that is present. Unlike a Bloom filter it supports remove: items can be deleted without rebuilding the structure.

The filter stores a short fingerprint of each item (16 bits here) in one of two candidate buckets, relocating existing fingerprints as needed to make room — the “cuckoo” behaviour. The false-positive rate is fixed by the fingerprint width at roughly 0.012%; for a tunable rate without deletion, use a BloomFilter.

The filter is generic over the item type T and a BuildHasher S, defaulting to the deterministic DefaultHashBuilder.

Examples

use bloom_lib::CuckooFilter;

let mut filter = CuckooFilter::new(1_000).unwrap();

filter.insert("alice").unwrap();
assert!(filter.contains("alice"));

assert!(filter.remove("alice"));
assert!(!filter.contains("alice"));

Implementations

impl<T: ?Sized> CuckooFilter<T, DefaultHashBuilder>

pub fn new(capacity: usize) -> Result<Self, Error>

Creates a filter able to hold roughly capacity items, using the default hasher.

The number of buckets is rounded up to a power of two with headroom, so the reported capacity is at least capacity and usually larger. Inserting close to the reported capacity may begin to fail with Error::CapacityExceeded; size with margin for write-heavy workloads.

Parameters

• capacity: the expected number of distinct items. Must be non-zero.

Errors

Returns Error::InvalidParameter if capacity is zero.

Examples

use bloom_lib::CuckooFilter;

let filter = CuckooFilter::<&str>::new(10_000).unwrap();
assert!(filter.capacity() >= 10_000);
assert!(filter.is_empty());

impl<T: ?Sized, S: BuildHasher> CuckooFilter<T, S>

pub fn with_hasher(capacity: usize, hasher: S) -> Result<Self, Error>

Creates a filter for roughly capacity items with a caller-supplied hasher.

Errors

Returns Error::InvalidParameter if capacity is zero.

Examples

use std::collections::hash_map::RandomState;
use bloom_lib::CuckooFilter;

let filter: CuckooFilter<&str, RandomState> =
    CuckooFilter::with_hasher(1_000, RandomState::new()).unwrap();

pub fn insert(&mut self, item: &T) -> Result<(), Error>

where T: Hash,

Inserts item into the filter.

Duplicates are permitted: inserting the same item twice stores two fingerprints and requires two remove calls to fully evict. This matches the semantics of the original Cuckoo filter and keeps remove exact with respect to insertions.

Errors

Returns Error::CapacityExceeded when the filter is too full to place the item within its relocation budget. The filter is unchanged in that case and remains usable for lookups and deletions.

Examples

use bloom_lib::CuckooFilter;

let mut filter = CuckooFilter::new(100).unwrap();
filter.insert(&42u32).unwrap();
assert!(filter.contains(&42u32));

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

where T: Hash,

Tests whether item is in the filter.

Returns false only if the item was definitely never inserted (or has since been removed). A return of true means the item is probably present, with a false-positive probability of roughly 0.012%.

Examples

use bloom_lib::CuckooFilter;

let mut filter = CuckooFilter::new(100).unwrap();
filter.insert("present").unwrap();
assert!(filter.contains("present"));
assert!(!filter.contains("absent"));

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

where T: Hash,

Removes one occurrence of item, returning true if it was present.

Only a single stored fingerprint is removed per call, mirroring insert. Because fingerprints collide, removing an item that was never inserted but collides with a present one can delete the wrong fingerprint; this is the same false-positive trade-off that governs contains. Only delete items you previously inserted.

Examples

use bloom_lib::CuckooFilter;

let mut filter = CuckooFilter::new(100).unwrap();
filter.insert("temp").unwrap();
assert!(filter.remove("temp"));
assert!(!filter.remove("temp")); // already gone

pub fn clear(&mut self)

Removes every item, retaining the allocation.

Examples

use bloom_lib::CuckooFilter;

let mut filter = CuckooFilter::new(100).unwrap();
filter.insert("x").unwrap();
filter.clear();
assert!(filter.is_empty());

pub fn len(&self) -> usize

The number of fingerprints currently stored.

Examples

use bloom_lib::CuckooFilter;

let mut filter = CuckooFilter::new(100).unwrap();
filter.insert("a").unwrap();
filter.insert("b").unwrap();
assert_eq!(filter.len(), 2);

pub fn is_empty(&self) -> bool

Returns true if the filter holds no items.

pub fn capacity(&self) -> usize

The maximum number of fingerprints the table can hold.

This is num_buckets * 4. Practical fill tops out a little below this value before insertions start to fail.

pub fn load_factor(&self) -> f64

The current load factor in [0.0, 1.0].

Examples

use bloom_lib::CuckooFilter;

let filter = CuckooFilter::<u32>::new(100).unwrap();
assert_eq!(filter.load_factor(), 0.0);

Trait Implementations

impl<T: Clone + ?Sized, S: Clone> Clone for CuckooFilter<T, S>

fn clone(&self) -> CuckooFilter<T, S>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug + ?Sized, S: Debug> Debug for CuckooFilter<T, S>

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

Formats the value using the given formatter.

impl<'de, T: ?Sized, S> Deserialize<'de> for CuckooFilter<T, S>

where S: Default,

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<T: ?Sized, S> Serialize for CuckooFilter<T, S>

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

where __S: Serializer,

Serialize this value into the given Serde serializer.