Probabilistic Data Structures in JavaScript: Sub-Millisecond Membership Tests with Bloom Filters

Ask a JavaScript application “have we seen this item before?” and the reflex answer is a Set. For hundreds of entries that is fine. For a million—a spell-check dictionary, every URL ever crawled by a local research tool, a year of processed invoice numbers—the honest accounting turns uncomfortable: each string in a Set carries object headers and character data, so memory climbs into tens of megabytes while cache behavior degrades long before that.

A Bloom filter answers the same question using roughly ten bits per item—about a megabyte for that million—while staying fast enough to feel free. The price is a strange bargain worth understanding deeply before adopting: it can say “definitely not seen” with certainty, but “probably seen” occasionally lies. This article builds one end to end—the intuition, the two formulas that matter, and a complete implementation on plain Uint8Array foundations.

The membership problem: knowing without storing

Most real-world lookups do not actually need the value back—they need a verdict. Has this URL been crawled? Is this word misspelled? Was this document already indexed? The full key matters only when the answer is yes, which is often rare.

Storing keys to answer a yes/no question is where the waste lives. A hash map keeps the entire key plus entry overhead so that it can return the key again. A sorted array keeps everything too. Every exact structure pays storage proportional to what it holds, because exactness demands evidence.

The probabilistic move is asking whether evidence is even necessary for a “no.” If we could test membership against a compact fingerprint of the set—one that never forgets an added member but sometimes hallucinates one—then cheap negative answers would let us consult heavyweight storage only for genuine hits. That is precisely the contract a Bloom filter offers, and in client-side contexts, where RAM budgets are tight and datasets live on the same device, the trade often lands beautifully.

Bits instead of objects

The structure itself is disarmingly simple: an array of m bits, all starting at zero, plus k independent hash functions mapping any input to positions within those m bits.

Inserting an item runs all k hashes and sets each indicated bit to 1. Querying runs the same hashes and inspects: if any indicated bit is still zero, the item was never inserted—a set bit cannot appear by accident, so “no” is certain. If all bits happen to be set, the verdict is “almost certainly yes,” because those bits might have been lit by different items whose paths happened to overlap yours. That overlap is the false positive, and its probability is tunable.

Three properties follow directly:

• False negatives never happen. Adding an item only ever sets bits; nothing unsets them.
• Deletion is impossible. Clearing the bits of one member would erase evidence shared with others, silently corrupting their membership. (Variants exist for this—more below.)
• Error grows as the array fills. More set bits mean more accidental overlap, so sizing is really about choosing where on the saturation curve you operate.

Sizing the filter: two formulas that matter

Bloom filters are unusually generous here—the standard results fit in two lines, both derived from the probability that a given bit remains untouched after n random inserts with k hashes each.

Bits needed per item, given target false-positive rate p:

bits_per_item = −ln(p) / (ln 2)²   ≈  1.44 × log₂(1/p)

Optimal hash count, given that fill ratio:

k = bits_per_item × ln 2

Worked example at honest scale. Target: one million items at 1% error. Then bits_per_item = −ln(0.01)/0.480 ≈ 9.6, so the array needs about 9.6 million bits—roughly 1.2 MB. Hash count rounds to 7. Compare storing the keys verbatim: even ten-character strings cost tens of megabytes inside a JavaScript Set before you account for engine overhead. Two orders of magnitude, for a 1% chance of a false alarm.

Intuition for why more hashes stop helping past the optimum: each additional hash makes a false positive harder (more bits must coincidentally align) but also lights more bits per insert, filling the array faster. The optimum sits exactly where those forces balance—which is why k = (m/n)·ln 2 falls out of setting a derivative to zero rather than from folklore.

Implementation walkthrough

Everything above compresses cleanly onto typed arrays. One subtlety earns respect: computing k independent hashes is wasteful, but two well-mixed hashes suffice to synthesize the rest via the Kirsch–Mitzenmacher technique—simulate hash i as (h₁ + i·h₂) mod m.

// bloom.js — an educational Bloom filter backed by one Uint8Array.
const fnv1a = (str, seed) => {
  let h = seed >>> 0;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);          // FNV-1a: xor byte, multiply prime
    h = Math.imul(h, 16777619);      // stays in 32-bit range
  }
  return h >>> 0;
};

export class BloomFilter {
  #size; #hashes; #bits;

  constructor(expectedItems, fpRate = 0.01) {
    // Standard sizing: m = -n·ln(p)/ln²2,  k = (m/n)·ln 2.
    this.#size   = Math.ceil((-expectedItems * Math.log(fpRate)) / (Math.LN2 ** 2));
    this.#hashes = Math.max(1, Math.round((this.#size / expectedItems) * Math.LN2));
    this.#bits   = new Uint8Array(Math.ceil(this.#size / 8));
  }

  // Two base hashes generate k positions via double hashing.
  #positions(key) {
    const a = fnv1a(key, 0x811c9dc5);
    const b = fnv1a(key, 0x9747b28c) | 1;         // odd stride avoids cycles
    const out = new Int32Array(this.#hashes);
    for (let i = 0; i < this.#hashes; i++) {
      out[i] = ((a + i * b) >>> 0) % this.#size;
    }
    return out;
  }

  add(key) {
    for (const p of this.#positions(key)) {
      this.#bits[p >> 3] |= 1 << (p & 7);         // byte p>>3, bit p&7
    }
  }

  mightContain(key) {
    return this.#positions(key).every(
      (p) => (this.#bits[p >> 3] & (1 << (p & 7))) !== 0);
  }

  serialize() {                                   // snapshot for persistence
    const { size, hashes } = this;
    return { size, hashes, bytes: this.#bits.slice() };
  }
}

Usage reads like the concept:

const crawled = new BloomFilter(1_000_000);      // ~1.2 MB, 1% error budget

crawled.add('example.com/reports/2026-q2');
crawled.mightContain('example.com/reports/2026-q2');  // always true
crawled.mightContain('example.com/reports/1999-q4');  // false unless 1% unlucky

Details worth noticing. Math.imul performs true 32-bit multiplication—plain * would break precision beyond 2³¹ and wreck hash quality. Bit indexing uses shift-and-mask (p >> 3, p & 7) instead of division, which is exactly the kind of arithmetic typed arrays make pleasant. And serialize() exists because these structures are meant to be built once and shipped—serialized to IndexedDB or OPFS and reloaded instantly, no rebuild cost on launch.

Where this wins in web development

Client-side scenarios reward the trade repeatedly:

• Offline spell-check dictionaries. Hundreds of thousands of words fingerprinted into a couple of megabytes; unknown words get flagged instantly, candidates confirmed against the real dictionary only when a hit suggests it.
• Deduplication histories in local tools. A crawler, backup differ, or document indexer consulting “seen before?” before expensive processing—our off-main-thread architecture piece shows where such checks belong in a worker pipeline.
• Allowlists and blocklists in extensions. Phishing-filter-style designs check URLs against a compact filter first and fetch authoritative lists only on positive results, saving bandwidth and latency simultaneously.
• Sync pre-checks in local-first apps. Before shipping a change to peers, test whether the receiving side likely has the chunk already—cheap coordination without central servers, a pattern that fits naturally with the storage choices described in IndexedDB or OPFS?

When not to use one: anywhere answers must be exact (billing, security allowlists where a false positive harms someone), anything requiring deletion or counting, and small sets—below a few thousand items, a plain Set is smaller than the code to avoid it. Counting Bloom filters (small counters instead of bits) and cuckoo filters (deletable, slightly denser) are the standard exits when those limits bind.

Questions people often ask

Do I need cryptographic hash functions?

No—collision resistance is unnecessary because inputs are not adversarial in typical uses, and FNV-1a-class hashes run far faster. Reach for stronger mixing only when attackers control the keys and could craft collisions to inflate your error rate deliberately.

Can a Bloom filter grow after construction?

Not gracefully—capacity is baked into sizing. Standard practice allocates for expected growth upfront, or layers scalable filters: a sequence of sibling filters, each sized for its era, queried in order and retired together during rebuilds.

How should serialized filters be stored?

The snapshot is just parameters plus raw bytes—ideal for structured storage. Persist via IndexedDB for queryability alongside metadata, or OPFS for large dictionaries; reload costs one Uint8Array construction versus recomputing every insert from source data.

How do I pick the false-positive rate?

Work backward from consequence: ask what one wrong “yes” costs downstream. Pre-filters guarding a cheap local lookup tolerate 1–5% happily; anything feeding security decisions belongs near 0.1% or should not be probabilistic at all. Memory scales logarithmically with precision, so tightening from 1% to 0.1% adds only about four bits per item.

The takeaway

Bloom filters earn their place wherever “have we seen this?” gets asked millions of times about data too large to hold. The mathematics is two formulas, the implementation fits in one screen, and the failure mode—a chosen, bounded rate of false positives—is something you negotiate rather than fear. Few data structures offer this ratio of insight to effort; build one once and probabilistic thinking starts showing up everywhere else in your designs.