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

Requires Node.js 22 or newer.

🛠️ 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. Buffer scenarios in the full report include only adapters with native Buffer support.

strings N=1e5, M=2^21 (~256KiB), 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 | 15.04 Mops 100.0% of best | 14.91 Mops 100.0% of best | 14.32 Mops 100.0% of best | 0.00500% 80.0% of best | | bloomfilter | 8.410 Mops 55.9% of best | 11.15 Mops 74.8% of best | 6.935 Mops 48.4% of best | 0.00600% 66.7% of best | | @ably/bloomit | 1.459 Mops 9.7% of best | 1.453 Mops 9.7% of best | 2.157 Mops 15.1% of best | 0.00700% 57.1% of best | | bloom-filter | 220.0 Kops 1.5% of best | 216.3 Kops 1.5% of best | 1.220 Mops 8.5% of best | 0.00600% 66.7% of best | | bloom-filters | 171.1 Kops 1.1% of best | 174.4 Kops 1.2% of best | 167.3 Kops 1.2% of best | 0.00400% 100.0% of best |

🧪 Development

The checked-in WASM artifact lets a fresh clone run the TypeScript tests and build the distributable package without requiring Emscripten locally.

pnpm install
pnpm test
pnpm build

If you change the C sources under src/wasm/, rebuild the artifact with Emscripten before publishing:

pnpm build:wasm
pnpm build:full