Struct xorfilter::Xor8

pub struct Xor8<H = BuildHasherDefault> where
    H: BuildHasher,  {
    pub hash_builder: H,
    pub seed: u64,
    pub block_length: u32,
    pub finger_prints: Vec<u8>,
    // some fields omitted
}

Type Xor8 is probabilistic data-structure to test membership of an element in a set.

This implementation has a false positive rate of about 0.3% and a memory usage of less than 9 bits per entry for sizeable sets.

Xor8 is parametrized over type H which is expected to implement BuildHasher trait, like types RandomState and BuildHasherDefault. When not supplied, BuildHasherDefault is used as the default hash-builder.

If RandomState is used as BuildHasher, std has got this to say

A particular instance RandomState will create the same instances of Hasher, but the hashers created by two different RandomState instances are unlikely to produce the same result for the same values._

If DefaultHasher is used as BuildHasher, std has got this to say,

The internal algorithm is not specified, and so its hashes should not be relied upon over releases.

The default type for parameter H might change when a reliable and commonly used BuildHasher type is available.

Fields

hash_builder: H

seed: u64

block_length: u32

finger_prints: Vec<u8>

Implementations

impl<H> Xor8<H> where
    H: BuildHasher, 

pub fn new() -> Self where
    H: Default, 

New Xor8 instance initialized with DefaultHasher.

pub fn with_hasher(hash_builder: H) -> Self

New Xor8 instance initialized with supplied hasher.

impl<H> Xor8<H> where
    H: BuildHasher, 

pub fn insert<K: ?Sized + Hash>(&mut self, key: &K)

Insert 64-bit digest of a single key. Digest for the key shall be generated using the default-hasher or via hasher supplied via Xor8::with_hasher method.

pub fn populate<K: Hash>(&mut self, keys: &[K])

Populate with 64-bit digests for a collection of keys of type K. Digest for key shall be generated using the default-hasher or via hasher supplied via Xor8::with_hasher method.

pub fn populate_keys(&mut self, digests: &[u64])

Populate with pre-compute collection of 64-bit digests.

pub fn build(&mut self) -> Result<()>

Build bitmap for keys that where previously inserted using Xor8::insert, Xor8::populate and Xor8::populate_keys method.

pub fn build_keys(&mut self, digests: &[u64]) -> Result<()>

Build a bitmap for pre-computed 64-bit digests for keys. If keys where previously inserted using Xor8::insert or Xor8::populate or Xor8::populate_keys methods, they shall be ignored.

It is upto the caller to ensure that digests are unique, that there no duplicates.

impl<H> Xor8<H> where
    H: BuildHasher, 

pub fn contains<K: ?Sized + Hash>(&self, key: &K) -> bool

Contains tell you whether the key is likely part of the set, with false positive rate.

pub fn contains_key(&self, digest: u64) -> bool

Contains tell you whether the key, as pre-computed digest form, is likely part of the set, with false positive rate.

impl<H> Xor8<H> where
    H: Into<Vec<u8>> + From<Vec<u8>> + BuildHasher, 

Implements serialization and de-serialization logic for Xor8. This is still work in progress, refer to issue: https://github.com/bnclabs/xorfilter/issues/1 in github.

TODO: https://github.com/bnclabs/xorfilter/issues/1

pub fn write_file(&self, path: &OsStr) -> Result<usize> where
    H: Clone, 

Write to file in binary format TODO Add chechsum of finger_prints into file headers

pub fn read_file(path: &OsStr) -> Result<Self> where
    H: Default, 

Read from file in binary format

pub fn to_bytes(&self) -> Vec<u8> where
    H: Clone, 

pub fn from_bytes(buf: Vec<u8>) -> Result<Self> where
    H: Default, 

Trait Implementations

impl<H> Default for Xor8<H> where
    H: BuildHasher + Default, 

fn default() -> Self

Returns the “default value” for a type.

impl<H> PartialEq<Xor8<H>> for Xor8<H> where
    H: BuildHasher, 

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.