BloomFilter
Defined in: packages/data/src/probabilistic/bloom-filter.ts:50
Approximate set membership in a fraction of the space an exact set needs.
has has no false negatives and does have false positives: “no” is
certain, “yes” means “probably”. That asymmetry is the whole point — it makes
a Bloom filter a safe front door for an expensive exact lookup, never a
replacement for one.
There is no delete: clearing a bit would clear it for every other item that
happens to hash onto it, turning “no false negatives” into a lie. Use
CuckooFilter when deletion is needed.
Sizing follows the standard derivation from expectedItems (n) and
falsePositiveRate (p): m = ceil(-n·ln p / (ln 2)²) bits and k = round((m/n)·ln 2) hashes, which is the k that minimises p for that m.
Exceeding expectedItems does not break the filter, it just raises the real
false-positive rate above the one asked for — estimatedFalsePositiveRate()
reports where it actually stands.
The k hashes come from two calls to the caller’s hash combined as h1 + i·h2 (Kirsch–Mitzenmacher), which is proven to cost nothing in accuracy
versus k independent hashes.
Time complexity: O(k) for add and has, independent of how many items are
held. Space: m bits regardless of item size.
Type Parameters
Section titled “Type Parameters”T
The item type.
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new BloomFilter<
T>(iterable,options):BloomFilter<T>
Defined in: packages/data/src/probabilistic/bloom-filter.ts:60
Parameters
Section titled “Parameters”iterable
Section titled “iterable”Iterable<T, any, any> | undefined
options
Section titled “options”Returns
Section titled “Returns”BloomFilter<T>
Properties
Section titled “Properties”bitCount
Section titled “bitCount”
readonlybitCount:number
Defined in: packages/data/src/probabilistic/bloom-filter.ts:56
Bits in the filter.
hashCount
Section titled “hashCount”
readonlyhashCount:number
Defined in: packages/data/src/probabilistic/bloom-filter.ts:58
Hashes per operation.
Methods
Section titled “Methods”add(
item):void
Defined in: packages/data/src/probabilistic/bloom-filter.ts:114
O(k), with exactly two hash calls regardless of k.
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”void
addAll()
Section titled “addAll()”addAll(
items):void
Defined in: packages/data/src/probabilistic/bloom-filter.ts:136
O(m·k) in the number of items.
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”void
clear()
Section titled “clear()”clear():
void
Defined in: packages/data/src/probabilistic/bloom-filter.ts:108
Returns
Section titled “Returns”void
count()
Section titled “count()”count():
number
Defined in: packages/data/src/probabilistic/bloom-filter.ts:104
How many times add was called with an item not already certainly present.
An estimate of the set’s size, not an exact count.
Returns
Section titled “Returns”number
estimatedFalsePositiveRate()
Section titled “estimatedFalsePositiveRate()”estimatedFalsePositiveRate():
number
Defined in: packages/data/src/probabilistic/bloom-filter.ts:170
The false-positive probability at the filter’s current fill, from the
fraction of bits actually set: (setBits / bitCount) ^ hashCount.
Measured rather than assumed, so it stays honest after more items were added than the filter was sized for. O(bitCount / 32).
Returns
Section titled “Returns”number
has(
item):boolean
Defined in: packages/data/src/probabilistic/bloom-filter.ts:148
O(k), with exactly two hash calls regardless of k.
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”boolean
false means the item is definitely absent. true means it
is probably present — see estimatedFalsePositiveRate.
merge()
Section titled “merge()”merge(
other):void
Defined in: packages/data/src/probabilistic/bloom-filter.ts:189
Folds other into this filter, so it holds the union of both item sets.
Merging is exact — the union of two Bloom filters is the Bloom filter of the union — which is what makes these usable across partitions.
Parameters
Section titled “Parameters”BloomFilter<T>
Returns
Section titled “Returns”void
Throws
Section titled “Throws”If the two filters were not sized identically. Bitwise union is only meaningful between filters with the same geometry.