Struct xorf::Xor16 [−][src]
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%.
fn len(&self) -> usize
[src]
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]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
pub fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,