CuckooFilter
Defined in: packages/data/src/probabilistic/cuckoo-filter.ts:48
Approximate set membership with deletion, the thing a Bloom filter cannot do.
Stores a short fingerprint of each item in one of two candidate buckets. The second bucket is derived from the first by XOR with the fingerprint’s hash, which is what makes the relation symmetric: from either bucket the other can be computed without the item, so a fingerprint can be relocated during insertion and found again during lookup.
Deleting removes one copy of a fingerprint. Only delete items actually inserted: removing a fingerprint that a different item happens to share would introduce a false negative, which this structure otherwise never has.
add can fail. When both candidate buckets are full, it evicts and relocates
up to maxKicks times; past that the filter is too loaded and add returns
false. A failed insert is rolled back, so the filter still holds
exactly what it held before — no previously inserted item is ever displaced
into nothing.
Time complexity: O(1) for has and delete — exactly two bucket probes.
add is O(1) amortised, degrading as the load factor approaches capacity.
Type Parameters
Section titled “Type Parameters”T
The item type.
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new CuckooFilter<
T>(iterable,options):CuckooFilter<T>
Defined in: packages/data/src/probabilistic/cuckoo-filter.ts:61
Parameters
Section titled “Parameters”iterable
Section titled “iterable”Iterable<T, any, any> | undefined
options
Section titled “options”Returns
Section titled “Returns”CuckooFilter<T>
Properties
Section titled “Properties”bucketSize
Section titled “bucketSize”
readonlybucketSize:number
Defined in: packages/data/src/probabilistic/cuckoo-filter.ts:55
Fingerprints per bucket.
Methods
Section titled “Methods”add(
item):boolean
Defined in: packages/data/src/probabilistic/cuckoo-filter.ts:117
O(1) amortised.
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”boolean
false if the filter was too full to place the item, after
maxKicks relocations. The filter is rolled back to exactly its prior
contents, so nothing inserted earlier is lost.
addAll()
Section titled “addAll()”addAll(
items):number
Defined in: packages/data/src/probabilistic/cuckoo-filter.ts:169
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”number
How many items were added. A shortfall means the filter filled up
— see add.
clear()
Section titled “clear()”clear():
void
Defined in: packages/data/src/probabilistic/cuckoo-filter.ts:105
Returns
Section titled “Returns”void
count()
Section titled “count()”count():
number
Defined in: packages/data/src/probabilistic/cuckoo-filter.ts:96
How many fingerprints are stored.
Returns
Section titled “Returns”number
delete()
Section titled “delete()”delete(
item):boolean
Defined in: packages/data/src/probabilistic/cuckoo-filter.ts:204
Removes one copy of the item’s fingerprint. O(1).
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”boolean
true if a matching fingerprint was removed. Deleting an item
never inserted can remove a colliding item’s fingerprint instead, which
is the one way this filter can produce a false negative.
has(
item):boolean
Defined in: packages/data/src/probabilistic/cuckoo-filter.ts:187
O(1), two bucket probes.
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”boolean
false means the item is definitely absent, provided only
inserted items were ever deleted. true means probably present.
loadFactor()
Section titled “loadFactor()”loadFactor():
number
Defined in: packages/data/src/probabilistic/cuckoo-filter.ts:101
The fraction of slots in use.
Returns
Section titled “Returns”number