Set Membership Testing: From Arrays to Bloom Filters

"Is this value in the set?" is one of the most common questions software asks. Has this user already voted? Have we seen this request ID before? Is this username taken? Is this URL on a list of known malicious sites?

That last one is a real example. When Chrome's Safe Browsing feature warns you before you visit a dangerous site, it's answering a membership question against a list of hundreds of millions of known-bad URLs. It does this on every page load, without a network round trip for most of them, and without shipping hundreds of millions of URLs down to your browser.

How is that possible? By trading a small, controlled amount of accuracy for enormous savings in memory and speed. This post walks through set membership testing from the obvious approach up to the probabilistic data structure behind that trick — the one Chrome itself used to run on directly: the Bloom filter.

The naive approach: search an array

The most basic way to check membership is to loop through a list and compare each item.

const maliciousUrls = [  "evil-site.com",  "phishing-example.net",  "totally-not-malware.org",];
function isMalicious(url) {  for (let i = 0; i < maliciousUrls.length; i++) {    if (maliciousUrls[i] === url) {      return true;    }  }  return false;}
console.log(isMalicious("evil-site.com")); // trueconsole.log(isMalicious("safe-site.com")); // false

Benefits: dead simple, no setup cost, works for any comparable value.

Trade-offs: this is O(n). Every lookup scans, on average, half the list. For three URLs that's irrelevant. For the hundreds of millions of URLs Safe Browsing tracks, checking every page load against a linear scan would be unusable.

Here's that scan happening, one comparison at a time. Press play and watch the cursor move down the array.

A better approach: hash sets

JavaScript's built-in Set (backed by a hash table) gets you to average O(1) lookups by hashing the value to a bucket instead of comparing against every entry.

const maliciousUrls = new Set([  "evil-site.com",  "phishing-example.net",  "totally-not-malware.org",]);
function isMalicious(url) {  return maliciousUrls.has(url);}
console.log(isMalicious("evil-site.com")); // trueconsole.log(isMalicious("safe-site.com")); // false

Benefits: constant-time average lookup, exact answers (no false positives or false negatives), simple API.

Trade-offs: memory. A hash set has to store every actual value (or at least a reference and its hash), plus bucket overhead. For a set of a few hundred million URL strings, that's gigabytes of memory — per client. Shipping that down to every copy of Chrome on every device isn't realistic, and even server-side, holding the full data set in memory on every edge node gets expensive fast.

Same lookup, same URLs — but watch how much shorter the path is. One hash, one jump, done.

This is the core tension: exact structures need space proportional to the number of items stored. To scale membership testing to huge sets under tight memory budgets, something has to give.

Trading certainty for space: probabilistic membership

A probabilistic membership structure never stores the actual items. Instead, it stores a compact summary that can answer "definitely not in the set" or "probably in the set." It sacrifices perfect accuracy in one direction to shrink memory by orders of magnitude.

The key asymmetry: false positives are allowed (it says "probably yes" for something that isn't actually in the set), but false negatives are not (if something is in the set, it will never say "no"). That one-sided error is exactly what makes it safe to use as a fast pre-check — you can always follow up on a "probably yes" with a slower, authoritative check, but you never need to double check a "no."

This is close to how Chrome's Safe Browsing has always worked, and it's still the cleanest way to explain the idea. Early versions kept a literal Bloom filter of malicious URL hashes locally in the browser: most page loads hashed to "definitely not malicious" and finished instantly with zero network calls, and on the rare "probably malicious" hit, Chrome made a real request to Google's servers to confirm before showing a warning. The filter's job was never to be the final word — it was to filter out the vast majority of harmless lookups so the expensive, authoritative check only ran when it might matter. (Chrome has since moved on to more specialized structures — a sorted prefix set, and later a hash-prefix list synced from Google's servers — but they solve the exact same problem with the exact same one-sided-error trick: false positives allowed, false negatives never.)

Bloom filters

A Bloom filter is a fixed-size bit array plus a handful of independent hash functions. To add an item, you hash it k times, and set the bit at each resulting position to 1. To check membership, you hash the item the same way and check whether all of those bit positions are 1.

That check only has two possible outcomes, and they're not symmetric:

• Any bit is 0 → the item was definitely never added. This is the fast path, and the common one: most lookups against a real filter are for things that aren't in the set, and the moment one hash position comes back 0, the answer is settled. No more hashing, no more checking.
• Every bit is 1 → the item was probably added. "Probably," because those bits could have been set by some combination of other items whose hashes happened to land on the same positions. The filter only remembers bits, not the values that set them, so it has no way to tell "the real item" apart from "an unlucky collision."

That second case is the entire trade-off in one sentence: a Bloom filter buys its speed and space by being willing to say "probably yes" when the truth is "no."

class BloomFilter {  constructor(size = 256, hashCount = 3) {    this.size = size;    this.hashCount = hashCount;    this.bits = new Uint8Array(size);  }
  // Kirsch-Mitzenmacher double hashing: derive `hashCount` positions  // from just two real hash computations (h1 + i*h2) instead of running  // k separate hash functions. The positions aren't fully independent,  // but in practice the false-positive rate is close enough to the  // "true" k-independent-hashes case that almost no production Bloom  // filter bothers computing k real hashes.  _positions(value) {    const h1 = this._hash(value, 5381);    const h2 = this._hash(value, 52711);    const positions = [];
    for (let i = 0; i < this.hashCount; i++) {      positions.push((h1 + i * h2) % this.size);    }
    return positions;  }
  _hash(value, seed) {    let hash = seed;    for (let i = 0; i < value.length; i++) {      hash = (hash * 33) ^ value.charCodeAt(i);    }    return Math.abs(hash);  }
  add(value) {    for (const position of this._positions(value)) {      this.bits[position] = 1;    }  }
  // Returns false for "definitely not in the set", true for  // "probably in the set".  mightContain(value) {    return this._positions(value).every((position) => this.bits[position] === 1);  }}
const filter = new BloomFilter();filter.add("evil-site.com");filter.add("phishing-example.net");
console.log(filter.mightContain("evil-site.com"));   // true — a real match: this one was addedconsole.log(filter.mightContain("safe-site.com"));   // false — a true non-match: definitely not in the set
// "store.info" was never added. But hash it and check: it lands on// positions [230, 110, 246] — the exact same three bits "evil-site.com"// set when it was added. The filter has no way to tell the two apart,// because it never stored the strings, only those three bits.console.log(filter.mightContain("store.info"));      // true — false positive

The bit array here is fixed size regardless of how many URLs go in — 256 bits either way. Compare that to a Set, where memory grows with every item added. That's the whole trade: a Bloom filter for millions of URLs can fit in a few megabytes, where a hash set holding the same URLs would need gigabytes.

Benefits:

• Extremely space-efficient — size doesn't depend on the length of the stored values, only on how many bits you allocate up front.
• Lookups and inserts are O(k), where k is the (small, fixed) number of hash functions — effectively constant time.
• No false negatives: if it says "not in the set," that's guaranteed.

Trade-offs:

• False positives are possible, as "store.info" demonstrates above, and the rate rises as more items are added relative to the bit array's size — more items set more bits, so a random hash is more likely to land on ones that are already 1. This is a real, tunable number, not a vague risk: at n items in an m-bit filter with k hash functions, the expected false-positive rate is approximately (1 - e^(-kn/m))^k. You size the filter based on how many items you expect and how much false-positive risk you can tolerate — that's exactly the calculation behind the "≈1.44 × log₂(1/p) bits per item" figure in the memory chart further down.
• You can't remove items. Clearing a bit to "unadd" one value might belong to another value's hash pattern too, corrupting the filter. (A variant called a Counting Bloom Filter uses small counters instead of single bits to support removal, at the cost of more memory.)
• You can't retrieve the original items or iterate the set's contents — the filter only answers "is this in here," not "what's in here."

This is where the .every() in mightContain earns its keep — it stops at the first bit that isn't set, instead of checking all k regardless. That short-circuit is also why Bloom filters are so good in practice: for something like Safe Browsing, the overwhelming majority of lookups are non-matches (most URLs aren't malicious), so the common case resolves in a single failed bit check, not k of them. The animation below walks through all three outcomes on the same filter — a real match, a true non-match, and a false positive — so you can see exactly where each one ends:

Seeing the trade-offs at scale

The benefits and trade-offs above are easy to state but easy to underestimate — "grows with the list" doesn't feel dramatic until you put a real list size against it. Here's the same three approaches checking a URL against a list of 1,000,000 known-bad sites.

The array scan line only gets worse as the list grows, since it's doing real work proportional to n. The hash set and Bloom filter barely move — that flat line is what O(1) and O(k) actually look like next to O(n).

Lookup speed is only half the story, though. Memory is where the Bloom filter earns its place in a browser.

Choosing between them

Use an array when the set is small and simplicity matters more than speed. Use a hash set when you need exact answers and can afford to store every item. Reach for a probabilistic structure like a Bloom filter when the set is huge, memory is constrained, and an occasional false positive is acceptable because something downstream — like Chrome's server-side confirmation check — can catch it.

That's the pattern behind Safe Browsing, spell checkers flagging "probably misspelled" words before a real dictionary lookup, and databases like Cassandra using Bloom filters to skip disk reads for keys that definitely don't exist on a given file. The same trick — a small, fixed-size summary that trades certainty for scale — shows up anywhere a system needs to ask "have I seen this before?" billions of times a day.