
Memory-Efficient Membership Testing with a Bloom Filter in JavaScript
When a web application needs to test whether an identifier belongs to a catalog of hundreds of thousands of URLs, blocked usernames, or cached cache keys, storing every raw string inside a JavaScript Set quickly consumes tens of megabytes of heap memory. In browser environments, service workers, and edge runtimes with tight memory ceilings, shipping or holding full key lists just to answer simple negative checks ("is this key definitely absent?") wastes both bandwidth and RAM.
A Bloom filter solves this problem by trading exact membership storage for a compact bit array paired with $k$ independent hash positions. Instead of storing values themselves, inserting an item sets $k$ bits in a fixed-size Uint32Array, and membership queries check whether all $k$ bits are 1 in $O(k)$ constant time. While a Bloom filter carries a small, mathematically tunable false-positive probability, it guarantees zero false negatives—meaning a false result proves with 100% certainty that an item has never been seen, allowing applications to skip expensive network lookups or database reads safely.
Example
// Optimal parameter calculation and double-hashing probe indexes
function computeBloomParams(expectedItems, falsePositiveRate) {
const ln2 = Math.LN2;
const bitCount = Math.ceil(
(-expectedItems * Math.log(falsePositiveRate)) / (ln2 * ln2)
);
const hashCount = Math.max(1, Math.round((bitCount / expectedItems) * ln2));
return { bitCount, hashCount };
}
// Kirsch-Mitzenmacher double hashing generates k positions from just 2 base hashes
function probeBitIndex(hashA, hashB, iteration, bitCount) {
return ((hashA + iteration * hashB) >>> 0) % bitCount;
}
Implementation
/**
* BloomFilter
* Space-efficient probabilistic set backed by a Uint32Array bitset
* and Kirsch-Mitzenmacher double hashing.
*/
export class BloomFilter {
/**
* @param {number} expectedItems - Expected maximum number of inserted items.
* @param {number} [falsePositiveRate=0.01] - Target false-positive rate (0 < p < 1).
*/
constructor(expectedItems, falsePositiveRate = 0.01) {
if (!Number.isInteger(expectedItems) || expectedItems <= 0) {
throw new RangeError('expectedItems must be a positive integer.');
}
if (falsePositiveRate <= 0 || falsePositiveRate >= 1) {
throw new RangeError('falsePositiveRate must be strictly between 0 and 1.');
}
const ln2 = Math.LN2;
this.bitCount = Math.ceil(
(-expectedItems * Math.log(falsePositiveRate)) / (ln2 * ln2)
);
this.hashCount = Math.max(
1,
Math.round((this.bitCount / expectedItems) * ln2)
);
this.words = new Uint32Array(Math.ceil(this.bitCount / 32));
this.insertedCount = 0;
}
/**
* Compute two independent 32-bit FNV-1a / Murmur-mixed hashes for a string.
* @param {string} value
* @returns {[number, number]}
*/
static hashPair(value) {
let h1 = 0x811c9dc5;
let h2 = 0x9e3779b1;
for (let i = 0; i < value.length; i++) {
const code = value.charCodeAt(i);
h1 ^= code;
h1 = Math.imul(h1, 0x01000193);
h2 ^= code + i;
h2 = Math.imul(h2, 0x85ebca6b);
}
// Final avalanche mix to ensure uniform bit distribution
h1 ^= h1 >>> 16;
h2 ^= h2 >>> 15;
return [h1 >>> 0, (h2 >>> 0) | 1];
}
/**
* Insert an item into the filter.
* @param {string} value
*/
add(value) {
const key = String(value);
const [h1, h2] = BloomFilter.hashPair(key);
for (let i = 0; i < this.hashCount; i++) {
const bitIndex = ((h1 + Math.imul(i, h2)) >>> 0) % this.bitCount;
this.words[bitIndex >>> 5] |= 1 << (bitIndex & 31);
}
this.insertedCount += 1;
}
/**
* Test whether an item might exist in the filter.
* Returns false when the item is guaranteed absent, or true if possibly present.
* @param {string} value
* @returns {boolean}
*/
mightContain(value) {
const key = String(value);
const [h1, h2] = BloomFilter.hashPair(key);
for (let i = 0; i < this.hashCount; i++) {
const bitIndex = ((h1 + Math.imul(i, h2)) >>> 0) % this.bitCount;
const word = this.words[bitIndex >>> 5];
if ((word & (1 << (bitIndex & 31))) === 0) {
return false;
}
}
return true;
}
/**
* Export the compact binary state for IndexedDB, Cache API, or network transfer.
* @returns { { bitCount: number, hashCount: number, buffer: ArrayBuffer } }
*/
serialize() {
return {
bitCount: this.bitCount,
hashCount: this.hashCount,
buffer: this.words.buffer.slice(0)
};
}
/**
* Restore a BloomFilter from serialized binary state.
* @param { { bitCount: number, hashCount: number, buffer: ArrayBuffer } } snapshot
* @returns {BloomFilter}
*/
static deserialize(snapshot) {
const filter = Object.create(BloomFilter.prototype);
filter.bitCount = snapshot.bitCount;
filter.hashCount = snapshot.hashCount;
filter.words = new Uint32Array(snapshot.buffer.slice(0));
filter.insertedCount = 0;
return filter;
}
}
Main Point: A Bloom filter backed by a Uint32Array and double hashing answers membership queries in constant time with zero false negatives using only a fraction of the memory of a standard Set.
Credits
Photo by Martin Adams on Unsplash