Struct xorf::Xor8

pub struct Xor8 { /* fields omitted */ }

Xor filter using 8-bit fingerprints.

An Xor8 filter uses <10 bits per entry of the set is it constructed from, and has a false positive rate of <0.4%. As with other probabilistic filters, a higher number of entries decreases the bits per entry but increases the false positive rate.

An Xor8 is constructed from a set of 64-bit unsigned integers and is immutable.

use xorf::{Filter, Xor8};

const SAMPLE_SIZE: usize = 1_000_000;
let keys: Vec<u64> = (0..SAMPLE_SIZE).map(|_| rng.gen()).collect();
let filter = Xor8::from(&keys);

// no false negatives
for key in keys {
    assert!(filter.contains(&key));
}

// bits per entry
let bpe = (filter.len() as f64) * 8.0 / (SAMPLE_SIZE as f64);
assert!(bpe < 10., "Bits per entry is {}", bpe);

// false positive rate
let false_positives: usize = (0..SAMPLE_SIZE)
    .map(|_| rng.gen())
    .filter(|n| filter.contains(n))
    .count();
let fp_rate: f64 = (false_positives * 100) as f64 / SAMPLE_SIZE as f64;
assert!(fp_rate < 0.405, "False positive rate is {}", fp_rate);

Serializing and deserializing Xor8 filters can be enabled with the serde feature.

Trait Implementations

impl Filter<u64> for Xor8

fn contains(&self, key: &u64) -> bool

Returns true if the filter contains the specified key. Has a false positive rate of <0.4%.

fn len(&self) -> usize

Returns the number of fingerprints in the filter.

impl<'_> From<&'_ [u64]> for Xor8

fn from(keys: &[u64]) -> Self

Performs the conversion.

impl<'_> From<&'_ Vec<u64>> for Xor8

fn from(v: &Vec<u64>) -> Self

Performs the conversion.

impl From<Vec<u64>> for Xor8

fn from(v: Vec<u64>) -> Self

Performs the conversion.