Bloom Filter

A Bloom filter is a compact, probabilistic set: it answers membership with either definitely not present or probably present — never a false negative, but with a tunable rate of false positives. It stores only a fixed array of bits plus a handful of hash functions — never the items themselves — so it stays tiny even after billions of inserts. Databases, caches, and CDNs put one in front of an expensive lookup and skip the work entirely whenever the filter reports an item is definitely absent. You will build the factory bloomFilter(size, hashFns), which returns an object with add and mightContain. See Bloom filter for background.

Signature

bloomFilter(size, hashFns)   // -> { add, mightContain }
add(item)                    // set the item's k bits to 1; returns nothing
mightContain(item)           // true = probably present, false = definitely absent

• size — the number of bits in the bit array.
• hashFns — an array of k hash functions. Each maps an item to a non-negative integer; the filter takes that result % size to pick a bit index. They are injected so the filter is fully deterministic.

Examples

const hashFns = [
  (s) => s.length,                    // a bit from the length
  (s) => s.charCodeAt(0),             // a bit from the first character
  (s) => s.charCodeAt(s.length - 1),  // a bit from the last character
];
const bf = bloomFilter(10, hashFns);

bf.add('cat');            // sets bits 3, 9, 6  (3, 99, 116 each mod 10)
bf.mightContain('cat');  // true  — all three bits are 1
bf.mightContain('dog');  // false — reads bit 0, which is still 0

Because the filter only stores bits, an item you never added can still report present once other items have lit all of its bits:

bf.add('ax');            // also sets bits 2, 7, 0
bf.mightContain('fox');  // true — but 'fox' was never added (a false positive)

Notes

• Bit array plus k hashes — the filter is a size-bit array and k hash functions. add turns on the k bits an item hashes to; mightContain checks those same k bits.
• No false negatives — anything you added always reports true. This is the one guarantee the whole structure exists to provide.
• False positives are expected — an item never added can report true when other items happen to have set all of its bits. The rate falls as you give the filter more bits or tune k.
• No removal, no listing — the filter holds only bits, so it cannot delete an item or enumerate its contents; clearing bits would corrupt other items.
• Take each hash mod size — a hash may return any non-negative integer, so reduce it with % size before indexing. Your code must work for any k — one hash function or ten.