Bloom filter

A Bloom filter stores m bits, initially zero. Inserting a string sets its k hash positions to one. A query checks the same positions: any zero bit means definitely absent; all ones mean only possibly present. With fixed parameters and no deletion, inserted strings cannot become false negatives. The separate teaching reference stores exact strings solely to identify true membership and false positives; its extra storage is not included in the m filter bits.

Choose integer m from 8 to 1024 and k from 1 to 12, then create the filter. Editing either parameter discards the active filter until it is created again. Reset clears the filter and retains the input fields. Strings have 1–256 UTF-16 code units; at most 1024 different strings are retained. Comparison is exact and case-sensitive: there is no trimming or Unicode normalization. Spaces matter, many emoji occupy two code units, and composed and decomposed accents are different strings. The last string is shown using JSON quotes and escapes to make spaces and control characters identifiable. Duplicate insertion leaves the bit array, distinct-entry count and query counters unchanged.

The implementation retains its FNV-1a-like 32-bit hash variant over JavaScript UTF-16 code units, rather than the octets of standard FNV-1a. Each unit is XORed into the hash and multiplied by 16777619 modulo 2³². The two initial values are 2166136261 and 0xdeadbeef; the second result is made odd. The actual positions are (h₁ + i h₂) mod m for i = 0…k−1. Arithmetic is reduced modulo m without an intermediate 32-bit wrap. Repeated positions are permitted: an odd step does not guarantee a full cycle for arbitrary m. The operation table shows every position in sequence, including repeats. An insertion into a bit already set simply leaves it set. The two base hashes are available in Details. This is a deterministic, non-cryptographic teaching implementation, not a claim that the hashes are independent and uniform.

The observed false-positive rate is false positives divided by queries for strings actually absent from the reference set. Queries of inserted strings do not enter either counter. A new distinct insertion resets the counters because the reference set and possibly the bits have changed. Without any negative queries the rate is undefined. Repeated queries count as repeated requests; manually chosen queries are not an independent random sample and the displayed rate is not a guarantee for future strings.

Details show the classical approximation f ≈ (1 − exp(−kn/m))ᵏ for n distinct entries and ideal independent uniform hashes. It is not the exact rate of this finite deterministic filter. The a…h example inserts those eight ASCII strings into the current filter. With m = 8 and k = 1 they fill every bit, so any new string is a false positive. For a smaller example insert only a, then query i, a and b: i is false positive, a truly present and b absent; the observed rate is 1/2, because only two queries are negative.

Valid parameters, entries, counters and the last operation are retained during navigation. The existing cookie state has a 1500-character limit; larger states remain in this session and show a reload warning. No deletion, counting-filter variant, cryptographic protection or benchmark is provided.

Sources: Bloom (1970), Method 2 and Eq. 1, original-paper mirror; Kirsch and Mitzenmacher (2008), §§2 and 5.2; RFC 9923, FNV basics.