Struct probabilistic_collections::quotient::QuotientFilter

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

A space-efficient probabilistic data structure to test for membership in a set.

A quotient filter is essentially a compact hash table. Each item is hashed to a 64-bit fingerprint. The top q bits is the quotient of the item and the bottom r bits is the remainder of the item. The quotient which defines the index of the table to store the remainder. This index is called the “canoncial slot” of the item. When multiple items map to the same location, they are stored in contiguous slots called a run, and the quotient filter maintains that items in the same run are sorted by their remainder. Additionally, all runs are sorted by their canonical slot. If run r1 has a canonical slot at index i1 and run r2 has a canonical slot at index i2 where i1 < i2, then r1 occurs to the left of r2. Note that a run’s first fingerprint may not occupy its canonical slot if the run has been forced right by some run to its left. These invariants are established by maintaining three bits of metadata about a slot: is_shifted, is_continuation, and is_occupied.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let mut filter = QuotientFilter::<String>::new(8, 4);

assert!(!filter.contains("foo"));
filter.insert("foo");
assert!(filter.contains("foo"));

filter.clear();
assert!(!filter.contains("foo"));

assert_eq!(filter.quotient_bits(), 8);
assert_eq!(filter.remainder_bits(), 4);

Implementations

impl<T> QuotientFilter<T>

pub fn new(quotient_bits: u8, remainder_bits: u8) -> Self

Constructs a new, empty QuotientFilter with the specified number of quotient and remainder bits. quotient_bits and remainder_bits must be positive integers whose sum cannot exceed 64.

Panics

Panics if quotient_bits is 0, remainder_bits is 0, or if quotient_bits + remainder_bits is greater than 64.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let filter = QuotientFilter::<String>::new(8, 4);

pub fn from_fpp(capacity: usize, fpp: f64) -> Self

Constructs a new, empty QuotientFilter that can store capacity items with an estimated false positive probability of less than fpp. The ideal fullness of quotient filter is 50%, so the contructed quotient filter will have a maximum capacity of 2 * capacity.

Panics

Panics if capacity is 0, or if fpp is not in the range (0, 1).

Examples

use probabilistic_collections::quotient::QuotientFilter;

let filter = QuotientFilter::<String>::from_fpp(100, 0.05);

pub fn insert<U>(&mut self, item: &U)where
    T: Borrow<U>,
    U: Hash + ?Sized,

Inserts an element into the quotient filter.

Panics

Panics if the quotient filter is completely full.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let mut filter = QuotientFilter::<String>::new(8, 4);

filter.insert("foo");

pub fn contains<U>(&self, item: &U) -> boolwhere
    T: Borrow<U>,
    U: Hash + ?Sized,

Checks if an element is possibly in the quotient filter.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let mut filter = QuotientFilter::<String>::new(8, 4);

assert!(!filter.contains("foo"));
filter.insert("foo");
assert!(filter.contains("foo"));

pub fn remove<U>(&mut self, item: &U)where
    T: Borrow<U>,
    U: Hash + ?Sized,

Removes an element from the quotient filter.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let mut filter = QuotientFilter::<String>::new(8, 4);

filter.insert("foo");
assert!(filter.contains("foo"));
filter.remove("foo");
assert!(!filter.contains("foo"));

pub fn clear(&mut self)

Clears the quotient filter, removing all elements.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let mut filter = QuotientFilter::<String>::new(8, 4);

filter.insert("foo");
filter.clear();

assert!(!filter.contains("foo"));

pub fn len(&self) -> usize

Returns the number of items in the quotient filter.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let mut filter = QuotientFilter::<String>::new(8, 4);

filter.insert("foo");
assert_eq!(filter.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the quotient filter is empty.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let filter = QuotientFilter::<String>::new(8, 4);

assert!(filter.is_empty());

pub fn capacity(&self) -> usize

Returns the capacity of the quotient filter.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let filter = QuotientFilter::<String>::new(8, 4);

assert_eq!(filter.capacity(), 256);

pub fn quotient_bits(&self) -> u8

Returns the number of quotient bits in a fingerprint for a item.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let filter = QuotientFilter::<String>::new(8, 4);

assert_eq!(filter.quotient_bits(), 8);

pub fn remainder_bits(&self) -> u8

Returns the number of remainder bits in a fingerprint for a item.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let filter = QuotientFilter::<String>::new(8, 4);

assert_eq!(filter.remainder_bits(), 4);

pub fn estimated_fpp(&self) -> f64

Returns the estimated false positive probability of the quotient filter. This value will increase as more items are added.

Examples

use probabilistic_collections::quotient::QuotientFilter;

let mut filter = QuotientFilter::<String>::from_fpp(100, 0.05);
assert!(filter.estimated_fpp() < 1e-15);

filter.insert("foo");
assert!(filter.estimated_fpp() > 1e-15);
assert!(filter.estimated_fpp() < 0.05);

Trait Implementations

impl<T> Debug for QuotientFilter<T>

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

Formats the value using the given formatter.