Skip to content

BloomFilter ​

BloomFilter implements a probabilistic set-membership structure for string keys. A BloomFilter(k, m) stores keys across m bits using k independent hash functions: contains never reports a false negative, but may report a false positive with a probability that shrinks as the number of bits per key grows. It is non-generic: both constructor arguments are usize.

Construction ​

SyntaxDescription
BloomFilter(k, m)Create a new empty filter with k hash functions over m bits

Methods ​

MethodSignatureReturnsDescription
insert(key: string) => voidvoidAdd key to the filter
contains(key: string) => booleanbooleanWhether key may have been inserted; never a false negative

Complexity ​

OperationTime Complexity
insertO(k)
containsO(k)
BloomFilter(k, m)O(m / 64 + k)

Examples ​

insert ​

tyrus
import { BloomFilter } from "tyrus:algorithm";

const bf = BloomFilter(3, 256);
bf.insert("apple");
bf.insert("banana");
bf.insert("cherry");
bf.insert("date");

contains ​

tyrus
const bf = BloomFilter(3, 256);
bf.insert("apple");
bf.insert("banana");
bf.insert("cherry");
bf.insert("date");

print(bf.contains("apple"));   // true
print(bf.contains("banana"));  // true
print(bf.contains("egg"));     // false
print(bf.contains("fig"));     // false
print(bf.contains("grape"));   // false
print(bf.contains("honey"));   // false

The hashing is deterministic, so the misses above are guaranteed, not probabilistic. contains still allows false positives in general: once the filter is dense, an absent key may share all k bit positions with inserted keys.