Bloom Filter
A probabilistic set: k hash functions set k bits; false positives possible, false negatives impossible.
Decision · step 6 of 10Bloom Filter: Four words in, one stranger looks like a member
Query "cat": hashes 6, 4, 0. All three bits are 1, so the answer is "probably", and here it happens to be right: "cat" was inserted.
What you will see
A key lights up k bits; a query checks the same k bits.
Cost
| insert | O(k) |
|---|---|
| query | O(k) |
| Space | O(m bits) |
False-positive rate depends on mn and k.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.