BloomFilter.js

BloomFilter.js is published as @rawify/bloomfilter. It implements a mutable Bloom filter for memory-efficient, probabilistic membership checks on strings and binary values.

Use it as a pre-check before a database, cache, file, or network lookup: false means the key was not added, while true means the key may have been added. Use a Set or database index instead when exact membership, deletion, stored values, or iteration is required. For a static set, other probabilistic filter families may offer different space and construction tradeoffs.

Features

• Space-efficient set membership testing with guaranteed no false negatives
• Practical use case: lookup pre-check to avoid unnecessary requests
• Optimal parameter calculation from target capacity and false-positive rate
• Bit-level operations inspired by BitSet.js
• Support for binary and string keys (UTF-8 encoded once)
• High-quality double hashing (Kirsch–Mitzenmacher) with Murmur3-style hashes
• Enhanced double hashing (ENH) + xor mixing for accuracy
• Optional power-of-two optimization for constant-time masking
• Union and intersection of Bloom filters
• Live estimates: fill ratio, cardinality, false-positive rate
• Compact base64 serialization and restoration

Implementation Notes & Accuracy

Bloom filters are simple in concept but easy to implement poorly. Some implementations (see RocksDB issue #4120) suffer from:

1. Poor probe distribution: If the “step” size between indices is zero or not coprime with the filter size, the same few positions get probed repeatedly. This silently increases the false-positive rate.

2. Weak hashing: Deriving all indices from the same 32-bit hash with only rotations/XOR can create subtle correlations between indices, especially in medium-sized filters.

BloomFilter.js avoids these pitfalls:

• Uses two independent Murmur3 32-bit hashes instead of reusing one, ensuring high-quality entropy.
• Always forces the step to be odd, and when the bit count is a power of two (default), this guarantees full-cycle probing with no repeats.
• For non-power-of-two filters, it applies Enhanced Double Hashing (ENH) so indices remain well distributed even when gcd(step, m) ≠ 1.
• Adds a cheap xor mixing step to decorrelate the two hash streams further.

As a result, the accuracy of this implementation closely tracks the theoretical false-positive rates, even for small or non-standard filter sizes.

Note: Binary Fuse and XOR filters can outperform Bloom filters on static sets (lower bits/item, faster lookups), but they are not a drop-in replacement. Bloom filters remain the better choice when you need online updates, unions/intersections, or compatibility with streaming workloads.

Installation

You can install BloomFilter.js via npm:

npm install @rawify/bloomfilter

Or with yarn:

yarn add @rawify/bloomfilter

Alternatively, download or clone the repository:

git clone https://github.com/rawify/BloomFilter.js

Usage and runtime

CommonJS

const BloomFilter = require('@rawify/bloomfilter');
const filter = new BloomFilter({ capacity: 1000, errorRate: 0.01 });

The direct class export also remains available as .default and .BloomFilter.

ES modules

import BloomFilter, { BloomFilter as NamedBloomFilter } from '@rawify/bloomfilter';
const filter = new BloomFilter({ capacity: 1000, errorRate: 0.01 });

Standalone browser script

<script src="https://cdn.jsdelivr.net/npm/@rawify/[email protected]/dist/bloomfilter.min.js"></script>
<script>
  const filter = new BloomFilter({ capacity: 1000, errorRate: 0.01 });
</script>

Native browser module

<script type="module">
  import BloomFilter from 'https://cdn.jsdelivr.net/npm/@rawify/[email protected]/dist/bloomfilter.mjs';
  const filter = new BloomFilter({ capacity: 1000, errorRate: 0.01 });
</script>

The package has no runtime dependencies and supports Node.js 20 or newer. It requires Uint8Array, Uint32Array, TextEncoder, btoa, and atob, which are available in supported Node.js versions and modern browsers.

Recipes

Skip a lookup for a definitely absent key

The filter can reject keys before an expensive lookup. A positive result must still be confirmed by the authoritative data source.

import { BloomFilter } from '@rawify/bloomfilter';

const users = new BloomFilter({ capacity: 100, errorRate: 0.01 });
users.addAll(['user:alice', 'user:bob']);

console.log(users.mightContain('user:alice'));   // true
console.log(users.mightContain('user:mallory')); // false for this filter state

The second result is deterministic for this example, but arbitrary absent keys can return true because false positives are part of the data structure. Added keys are not expected to return false.

Persist and restore a filter

toJSON() stores the dimensions and a portable little-endian base64 representation of the bitset. fromJSON() recreates a compatible filter and rejects malformed dimensions or payload lengths.

import { BloomFilter } from '@rawify/bloomfilter';

const original = new BloomFilter({ capacity: 100, errorRate: 0.01 });
original.add('release:2026-09');

const serialized = JSON.stringify(original.toJSON());
const restored = BloomFilter.fromJSON(JSON.parse(serialized));

console.log(restored.mightContain('release:2026-09')); // true

Treat serialized data as untrusted input: malformed data throws, and a filter does not preserve the original keys or an exact insertion count.

Combine compatible shard filters

Union returns a new filter that recognizes entries from either source. Intersection performs a bitwise intersection and is only a probabilistic approximation of set intersection.

import { BloomFilter } from '@rawify/bloomfilter';

const east = new BloomFilter({ bitCount: 128, hashCount: 3 });
const west = new BloomFilter({ bitCount: 128, hashCount: 3 });
east.add('asset:east');
west.add('asset:west');

const combined = BloomFilter.union(east, west);
console.log(combined.mightContain('asset:east')); // true
console.log(combined.mightContain('asset:west')); // true

Both operands must have identical bitCount and hashCount; otherwise union() and intersection() throw. add() and addAll() mutate and return the receiver, clear() mutates and returns undefined, and set operations return a new filter.

Creating a Bloom Filter

You can create a Bloom filter either by specifying the desired capacity and false-positive rate:

const bf = new BloomFilter({ capacity: 100000, errorRate: 0.01 });

or by explicitly providing the number of bits and hash functions:

const bf = new BloomFilter({ bitCount: 1 << 20, hashCount: 7 });

Lookup Pre-Check Example

// Suppose we want to avoid unnecessary DB/API requests
bf.add("user:alice"); // mark known entries
bf.add("user:bob");

if (!bf.mightContain("user:mallory")) {
  // definitely not present → skip expensive lookup
} else {
  // possibly present → perform the real DB/API request
}

Adding and Testing Elements

bf.add("alice");
bf.addAll(["bob", "carol"]);

bf.mightContain("alice");   // true (possibly)
bf.mightContain("mallory"); // false (definitely not)

Estimations

bf.estimatedCardinality();        // Approximate number of inserted elements
bf.estimatedFalsePositiveRate();  // Current FP rate given fill ratio
bf.fillRatio();                   // Fraction of bits set

Set Operations

const bf1 = new BloomFilter({ capacity: 1000, errorRate: 0.01 });
const bf2 = new BloomFilter({ capacity: 1000, errorRate: 0.01 });

bf1.add("foo");
bf2.add("bar");

const both = BloomFilter.union(bf1, bf2);          // union of sets
const common = BloomFilter.intersection(bf1, bf2); // intersection of sets

Serialization

const dump = bf.toJSON();
// Save to disk, send over network, etc.
const bf2 = BloomFilter.fromJSON(dump);

Methods

Instance Methods

• add(key) - insert a single element.
• addAll(iterable) - insert multiple elements.
• mightContain(key) - test membership (false = definitely not present).
• clear() - reset the filter.
• bitCount - number of bits in the filter.
• hashCount - number of hash functions.
• bitset - underlying Uint32Array.
• addCalls - number of add operations performed.
• countSetBits() - number of bits currently set.
• fillRatio() - fraction of bits set.
• estimatedCardinality() - approximate number of distinct inserted elements.
• estimatedFalsePositiveRate() - current false-positive probability.
• toJSON() - export configuration and bitset as JSON.

Static Methods

• BloomFilter.fromJSON(obj) - restore from serialized JSON.
• BloomFilter.optimalParameters(capacity, errorRate) - compute ideal {bitCount, hashCount}.
• BloomFilter.union(a, b) - compute union of two compatible filters.
• BloomFilter.intersection(a, b) - compute intersection of two compatible filters.

Building the library

The implementation is written in strict TypeScript. The build emits CommonJS, ES modules, a standalone browser bundle, source maps, and format-specific declarations.

After cloning the Git repository, run:

npm install
npm run build

Run the runtime and type-level tests with:

npm test

Copyright and Licensing

Copyright (c) 2026, Robert Eisele Licensed under the MIT license.