Struct xorf::Xor16[][src]

pub struct Xor16 {
    pub seed: u64,
    pub block_length: usize,
    pub fingerprints: Box<[u16]>,
}

Xor filter using 16-bit fingerprints.

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

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

use xorf::{Filter, Xor16};

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

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

// bits per entry
let bpe = (filter.len() as f64) * 16.0 / (SAMPLE_SIZE as f64);
assert!(bpe < 20., "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.02, "False positive rate is {}", fp_rate);

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

Fields

seed: u64

The seed for the filter

block_length: usize

The number of blocks in the filter

fingerprints: Box<[u16]>

The fingerprints for the filter

Trait Implementations

impl Filter<u64> for Xor16[src]

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

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

impl From<&'_ [u64]> for Xor16[src]

impl From<&'_ Vec<u64, Global>> for Xor16[src]

impl From<Vec<u64, Global>> for Xor16[src]

Auto Trait Implementations

impl RefUnwindSafe for Xor16

impl Send for Xor16

impl Sync for Xor16

impl Unpin for Xor16

impl UnwindSafe for Xor16

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized
[src]

impl<T> Borrow<T> for T where
    T: ?Sized
[src]

impl<T> BorrowMut<T> for T where
    T: ?Sized
[src]

impl<T> From<T> for T[src]

impl<T, U> Into<U> for T where
    U: From<T>, 
[src]

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 
[src]

type Error = Infallible

The type returned in the event of a conversion error.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 
[src]

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.

impl<V, T> VZip<V> for T where
    V: MultiLane<T>,