Struct xorfilter::Fuse16

pub struct Fuse16<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<u16>,
    // some fields omitted
}

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

Fuse16 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.

Fields

hash_builder: H

seed: u64

segment_length: u32

segment_length_mask: u32

segment_count: u32

segment_count_length: u32

finger_prints: Vec<u16>

Implementations

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

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

New Fuse16 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) -> Fuse16<H>

New Fuse16 instance initialized with supplied hasher.

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

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

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