Struct qht::QQuotientHashTableD

pub struct QQuotientHashTableD { /* fields omitted */ }

QQuotient Hash Table Duplicates ("compact")

This implements qqhtdc, using a dense bitset as the underlying data structure

Methods

impl QQuotientHashTableD

pub fn new(
    memory_size: usize,
    n_buckets: usize,
    fingerprint_size: usize
) -> Self

Returns a a newly created QQuotientHashTableD or panics

This function takes as arguments:

• memory_size: allocated memory for the filter, in bits
• n_buckets: number of buckets
• fingerprint_size: size of each fingerprint, in bits. Cannot exceed FINGERPRINT_SIZE_LIMIT.

Parameters should be chosen in a consistent way, namely so that memory_size >= n_buckets * fingerprint_size

Example

use qht::{QQuotientHashTableD,BasicQHT};
let f = QQuotientHashTableD::new(1024, 1, 3);

Trait Implementations

impl Filter for QQuotientHashTableD

fn lookup(&self, e: impl Hash) -> bool

Performs a lookup for the provided element

Example

use qht::{Element, Filter, QQuotientHashTableD, BasicQHT};
let f = QQuotientHashTableD::new(1024, 1, 3);
let e = Element { value: 1234 };
assert!( !f.lookup(e) ); // The filter is empty

fn insert(&mut self, e: impl Hash) -> bool

Performs a lookup for an element and inserts it

Note: In this implementation, if the element is already present, it is re-inserted.

Note: The new element is inserted in the last bucket (not a random bucket)

Example

use qht::{Element,Filter, QQuotientHashTableD, BasicQHT};
let mut f = QQuotientHashTableD::new(1024, 1, 3);
let e = Element { value: 1234 };
let was_present = f.insert(e);
assert!( f.lookup(e) ); // The filter now contains e
assert!( !was_present ); // The filter did not previously contain e

impl BasicQHT for QQuotientHashTableD

fn get_fingerprint_from_bucket(
    &self,
    address: usize,
    bucket_number: usize
) -> u64

Retrieves a fingerprint from a given bucket (provided as an address and bucket_number)

fn insert_fingerprint_in_bucket(
    &mut self,
    address: usize,
    bucket_number: usize,
    fingerprint: u64
)

Inserts a fingerprint in a given buffer (provided as an address and bucket_number)

fn in_cell(&self, address: usize, fingerprint: u64) -> bool

Checks whether a fingerprint belongs to a given cell

fn get_fingerprint(&self, e: impl Hash) -> u64

Obtains an element's fingerprint