Struct AlephFilter 

pub struct AlephFilter { /* private fields */ }

The main Aleph Filter data structure.

Stores fingerprints in a compact quotient-filter format with dynamic expansion. Each element occupies one logical “slot” with data stored in slots and metadata in metadata.

Implementations

impl AlephFilter

pub fn new(expected_items: usize, fpr: f64) -> Self

Creates a new Aleph Filter sized for expected_items with target fpr.

Automatically computes internal parameters (slots, fingerprint width) to meet the FPR.

Arguments

• expected_items - Expected number of items to insert (must be > 0)
• fpr - Target false positive rate, e.g., 0.01 for 1% (must be in (0, 1))

Returns

A new empty AlephFilter instance

Panics

If expected_items <= 0 or fpr not in (0, 1).

pub fn with_params(num_slots: usize, remainder_bits: u32) -> Self

Creates a new Aleph Filter with manual parameters.

Use this constructor when you already know the desired slot count and fingerprint width.

Arguments

• num_slots - Desired number of logical slots (rounded up to next power of 2)
• remainder_bits - Fingerprint width in bits

Returns

A new empty AlephFilter instance

pub fn insert(&mut self, key: &[u8])

Inserts a key into the filter.

May trigger an automatic expansion if load factor exceeds threshold. Supports duplicate insertions (see contains for lookup semantics).

Arguments

• key - Byte slice to insert

Complexity

O(1) amortized expected time

pub fn contains(&self, key: &[u8]) -> bool

Checks if a key might be in the filter.

Returns true if the key is definitely in the filter. May return true for keys not inserted (false positive at rate fpr). Never returns true for keys definitely not inserted (no false negatives).

Arguments

• key - Byte slice to query

Returns

true if key is in filter (or hash collision), false if definitely not in filter

Complexity

O(1) expected time

pub fn delete(&mut self, key: &[u8]) -> bool

Removes a key from the filter, if present.

Deleting void entries (exhausted fingerprints) marks them with a tombstone. Deleting regular entries compacts the run by shifting elements left.

Arguments

• key - Byte slice to delete

Returns

true if a matching entry was found and deleted, false if not found

Complexity

O(1) expected time

pub fn len(&self) -> usize

Returns the number of items inserted, accounting for duplicates.

Returns

Count of insertion operations

pub fn is_empty(&self) -> bool

Returns true if the filter contains no items.

Returns

true if empty, false otherwise

pub fn load_factor(&self) -> f64

Returns the current load factor (items / slots).

Returns

Ratio in [0, 1+) (can exceed 1 due to extension slots)

pub fn capacity(&self) -> usize

Returns the current logical slot count.

Returns

Number of quotient-addressable slots

pub fn num_expansions(&self) -> usize

Returns the number of times the filter has expanded.

Each expansion doubles slots and sacrifices 1 fingerprint bit per entry.

Returns

Expansion count

pub fn quotient_bits(&self) -> u32

Returns the current number of quotient bits (log2 of logical slots).

Returns

Quotient bits

impl AlephFilter

pub fn fp_bits(&self) -> u32

Returns the current fingerprint width in bits.

Decreases by 1 with each expansion to make room for additional quotient bits. Uses saturating subtraction to prevent underflow.

Returns

Fingerprint bits available (>= 0)

Trait Implementations

impl Clone for AlephFilter

fn clone(&self) -> AlephFilter

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for AlephFilter

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.