Class: CuckooFilter

Cuckoo Filter implementation with 16-bit fingerprints.

Provides O(1) membership testing with support for deletion. False positives are possible (~0.003% at 95% load with 16-bit FP). False negatives are impossible (by design).

Note: This implementation tracks original IDs to enable correct resize. This trades memory for correctness. For space-critical applications, use a fixed-size filter created with fromIds().

Constructors

new CuckooFilter()

new CuckooFilter(options?): CuckooFilter

Parameters

Returns

CuckooFilter

Methods

add()

add(id): boolean

Add an item to the filter.

Parameters

Returns

boolean

true if added successfully, false if resize needed

clear()

clear(): void

Clear all items from the filter.

Returns

void

estimateMemoryUsage()

estimateMemoryUsage(): number

Estimate memory usage in bytes.

Returns

number

getCapacity()

getCapacity(): number

Get the capacity (max items before resize).

Returns

number

getCount()

getCount(): number

Get the number of items in the filter.

Returns

number

getLoadFactor()

getLoadFactor(): number

Get the current load factor.

Returns

number

mightContain()

mightContain(id): boolean

Check if an item might be in the filter.

Parameters

Returns

boolean

true if possibly present, false if definitely not present

remove()

remove(id): boolean

Remove an item from the filter.

Parameters

Returns

boolean

true if removed, false if not found

resize()

resize(): void

Resize the filter to accommodate more items. Doubles the number of buckets.

We use tracked IDs to properly rehash all items, ensuring no false negatives after resize. This is the only correct way to resize a Cuckoo filter.

Returns

void

serialize()

serialize(): CuckooFilterData

Serialize the filter for persistence.

Returns

CuckooFilterData

deserialize()

static deserialize(data): CuckooFilter

Deserialize a filter from persisted data.

Parameters

Returns

CuckooFilter

empty()

static empty(options?): CuckooFilter

Create an empty filter.

Parameters

Returns

CuckooFilter

fromIds()

static fromIds(ids, options?): CuckooFilter

Create a filter from a set of IDs (bulk load).

Parameters

Returns

CuckooFilter