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

``bash
npm install fast-bloom-filter


or

pnpm add fast-bloom-filter

or

bun add fast-bloom-filter
`

🛠️ Usage

`TypeScript
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.

$3

- 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} |