CuckooFilter
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:86
A cuckoo filter: a set with a tunable false-positive rate, zero false negatives, and delete. Keys are stored as short fingerprints in one of two candidate buckets (Fan et al., “Cuckoo Filter: Practically Better Than Bloom”, 2014).
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new CuckooFilter(
__namedParameters):CuckooFilter
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:257
Constructs a filter from CuckooParams.
Parameters
Section titled “Parameters”__namedParameters
Section titled “__namedParameters”Returns
Section titled “Returns”CuckooFilter
Throws
Section titled “Throws”ParamError if a setting is invalid.
Accessors
Section titled “Accessors”bitsPerKey
Section titled “bitsPerKey”Get Signature
Section titled “Get Signature”get bitsPerKey():
number
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:521
Slot bits per expected key, m / n.
Returns
Section titled “Returns”number
buckets
Section titled “buckets”Get Signature
Section titled “Get Signature”get buckets():
number
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:506
Number of 4-slot buckets.
Returns
Section titled “Returns”number
capacity
Section titled “capacity”Get Signature
Section titled “Get Signature”get capacity():
number
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:501
Slots in the table, 4 * buckets.
Returns
Section titled “Returns”number
Get Signature
Section titled “Get Signature”get count():
number
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:496
Fingerprints stored, one per add not undone by a delete.
Returns
Section titled “Returns”number
epsilon
Section titled “epsilon”Get Signature
Section titled “Get Signature”get epsilon():
number
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:531
Target false-positive rate at n keys.
Returns
Section titled “Returns”number
fingerprintBits
Section titled “fingerprintBits”Get Signature
Section titled “Get Signature”get fingerprintBits():
number
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:511
Width of each stored fingerprint, in bits.
Returns
Section titled “Returns”number
Get Signature
Section titled “Get Signature”get m():
number
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:516
Total slot bits, fingerprintBits * capacity.
Returns
Section titled “Returns”number
Get Signature
Section titled “Get Signature”get seed():
number
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:526
Hash seed.
Returns
Section titled “Returns”number
Methods
Section titled “Methods”add(
key):void
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:281
Adds key. Every call stores a fingerprint, including for a key already
present, so each add needs its own delete.
Parameters
Section titled “Parameters”BytesLike
Returns
Section titled “Returns”void
Throws
Section titled “Throws”CuckooFullError if the filter has no room for it.
delete()
Section titled “delete()”delete(
key):boolean
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:341
Removes one copy of key: the first slot holding its fingerprint in
either candidate bucket.
Only delete keys you added. A key never added can share a fingerprint and bucket with one that was, and deleting it removes that key’s fingerprint instead, a false negative the filter cannot detect: it stores fingerprints, not keys, so it cannot tell the two apart.
Parameters
Section titled “Parameters”BytesLike
Returns
Section titled “Returns”boolean
true if a matching fingerprint was removed; false, with the
filter unchanged, if there was none.
equals()
Section titled “equals()”equals(
other):boolean
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:409
Whether other holds the same settings and slots, so the two serialize to
identical bytes. Which slot a key lands in depends on insertion order, so
filters holding the same keys can still differ.
Parameters
Section titled “Parameters”CuckooFilter
The filter to compare against.
Returns
Section titled “Returns”boolean
true if the two are indistinguishable.
has(
key):boolean
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:356
Tests whether key may be in the filter.
Parameters
Section titled “Parameters”BytesLike
Returns
Section titled “Returns”boolean
false if key is definitely absent; true if it was added
(and not deleted) or on a false positive.
rate()
Section titled “rate()”rate():
number
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:370
Estimates the current false-positive rate from the load: a query compares
its fingerprint against about 8 * count / capacity occupied slots across
its two buckets, each matching with probability 1 / (2^f - 1).
Returns
Section titled “Returns”number
The estimated false-positive rate, 0 for an empty filter.
toBytes()
Section titled “toBytes()”toBytes():
Uint8Array
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:381
Serializes the filter to a DSTL type 7 frame, readable by CuckooFilter.fromBytes and by any reader of the documented format.
Returns
Section titled “Returns”Uint8Array
The frame bytes.
toJSON()
Section titled “toJSON()”toJSON():
FilterJSON
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:428
Serializes the filter as a JSON envelope around its CuckooFilter.toBytes frame.
Returns
Section titled “Returns”The JSON-safe envelope.
create()
Section titled “create()”
staticcreate(n,epsilon,options?):CuckooFilter
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:108
Creates a filter sized for n expected keys at a target false-positive rate.
Parameters
Section titled “Parameters”number
Expected number of keys.
epsilon
Section titled “epsilon”number
Target false-positive rate, e.g. 0.01 for 1%.
options?
Section titled “options?”CuckooOptions = {}
Optional seed.
Returns
Section titled “Returns”CuckooFilter
A new, empty filter.
from()
Section titled “from()”
staticfrom(keys,epsilon,options?):CuckooFilter
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:126
Builds a filter from the given keys; duplicates are ignored. It is sized for the distinct keys at the target false-positive rate, and holds each once, so a key listed twice needs one delete.
Parameters
Section titled “Parameters”Iterable<BytesLike>
The keys to insert.
epsilon
Section titled “epsilon”number
Target false-positive rate, e.g. 0.01 for 1%.
options?
Section titled “options?”CuckooOptions = {}
Optional seed.
Returns
Section titled “Returns”CuckooFilter
A new filter containing every key.
fromBytes()
Section titled “fromBytes()”
staticfromBytes(bytes):CuckooFilter
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:161
Restores a filter from its CuckooFilter.toBytes serialization.
Parameters
Section titled “Parameters”Uint8Array
The serialized filter.
Returns
Section titled “Returns”CuckooFilter
The reconstructed filter.
fromJSON()
Section titled “fromJSON()”
staticfromJSON(value):CuckooFilter
Defined in: packages/distillate/src/cuckoo/cuckoo.ts:248
Restores a filter from its CuckooFilter.toJSON envelope.
Parameters
Section titled “Parameters”unknown
The parsed JSON envelope.
Returns
Section titled “Returns”CuckooFilter
The reconstructed filter.