Struct xorfilter::Fuse8

pub struct Fuse8<H = BuildHasherDefault> where
    H: BuildHasher,  {
    pub hash_builder: H,
    pub seed: u64,
    pub segment_length: u32,
    pub segment_length_mask: u32,
    pub segment_count: u32,
    pub segment_count_length: u32,
    pub finger_prints: Vec<u8>,
    // some fields omitted
}

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

Fuse8 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 available.

IMPORTANT: Fuse8 filter can only tolerate few duplicates in a given data-set. So make sure to supply a hasher that is capable of generating unique digests, (with allowed tolerance of duplicates) and while supplying the digests directly via populate_keys() and build_keys() make sure they don’t have more than few duplicates.

Fields

hash_builder: H

seed: u64

segment_length: u32

segment_length_mask: u32

segment_count: u32

segment_count_length: u32

finger_prints: Vec<u8>

Implementations

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

pub fn new(size: u32) -> Fuse8<H> where
    H: Default, 

New Fuse8 instance that can index size number of keys. Internal data-structures are pre-allocated for size. size should be at least 2.

pub fn with_hasher(size: u32, hash_builder: H) -> Fuse8<H>

New Fuse8 instance initialized with supplied hasher.

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

pub fn size_of(&self) -> usize

Return the size of index.

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 Fuse8::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 Fuse8::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 Fuse8::insert, Fuse8::populate and Fuse8::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 Fuse8::insert or Fuse8::populate or Fuse8::populate_keys methods, they shall be ignored.

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

impl<H> Fuse8<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.