FAST-BLOOM-FILTER

The fastest Bloom Filter on npm.
Powered by WASM, written in TypeScript & C.

💡 What is a Bloom Filter?

A Bloom filter is a probabilistic set that guarantees no false negatives but tolerates unlikely false positives.

With n items, m bits and k hash functions the false-positive probability is P_fp ≈ (1 - e^{-kn/m})^k; using the near-optimal k ≈ (m/n) ln 2 yields m ≈ -(n ln p)/(ln 2)^2 bits to hit a target rate p (≈9.6 bits per element for p = 0.01).

🚀 Install

npm install fast-bloom-filter
# or
pnpm add fast-bloom-filter
# or
bun add fast-bloom-filter

🛠️ Usage

import FastBloomFilter from "fast-bloom-filter";

// Create a bloom filter for 100 elements with an expected false positive rate of 0.01
const bloomFilter = await FastBloomFilter.createOptimal(100, 0.01);
// Create a bloom filter of 100 bits with 4 hash rounds
//const bloomFilter = await FastBloomFilter.create(100, 4);

bloomFilter.addString("hello");
bloomFilter.add(Buffer.from([0x01, 0x02, 0x03]));

bloomFilter.hasString("hello"); // true
bloomFilter.has(Buffer.from([0x01, 0x02, 0x03])); // true
bloomFilter.hasString("foo"); // likely false
bloomFilter.has(Buffer.from([0x01, 0x02, 0x03, 0x04])); // likely false

const snapshot = bloomFilter.export();
bloomFilter.dispose();

const restored = await FastBloomFilter.import(snapshot);
restored.hasString("hello"); // true
restored.has(Buffer.from([0x01, 0x02, 0x03])); // true
restored.hasString("foo"); // likely false
restored.has(Buffer.from([0x01, 0x02, 0x03, 0x04])); // likely false
restored.dispose();

📐 Theory

📄 Burton H. Bloom (1970) Space/time trade-offs in hash coding with allowable errors

📄 Kirsch and Mitzenmacher (2006) Less Hashing, Same Performance: Building a Better Bloom Filter

📊 Benchmarks

Complete benchmark results

Timings are medians of 3 runs with GC before/after each run. For adapters without Buffer support, buffer datasets are base64-encoded strings.

strings N=1e5, M=2^21 (~2MB), K=10

• N: 100,000 • Bits: 2,097,152 • K: 10 • Data: strings

| Adapter | Add Throughput | Has-hit Throughput | Has-miss Throughput | FP Rate | |:--|--:|--:|--:|--:| | FastBloomFilter | 24.28 Mops 100.0% of best | 24.33 Mops 100.0% of best | 22.25 Mops 100.0% of best | 0.00500% 80.0% of best | | bloomfilter | 11.00 Mops 45.3% of best | 10.25 Mops 42.1% of best | 10.88 Mops 48.9% of best | 0.00600% 66.7% of best | | @ably/bloomit | 1.348 Mops 5.6% of best | 1.399 Mops 5.7% of best | 1.834 Mops 8.2% of best | 0.00700% 57.1% of best | | blumea | 567.1 Kops 2.3% of best | 492.8 Kops 2.0% of best | 1.444 Mops 6.5% of best | 0.964% 0.4% of best | | bloom-filters | 339.4 Kops 1.4% of best | 345.4 Kops 1.4% of best | 360.1 Kops 1.6% of best | 0.00400% 100.0% of best | | bloom-filter | 215.5 Kops 0.9% of best | 219.2 Kops 0.9% of best | 1.272 Mops 5.7% of best | 0.00600% 66.7% of best |