Bloom Filter

Burton Howard Bloom, 1970

Introduced by Burton Bloom in 1970, a Bloom filter uses multiple hash functions to map elements to positions in a bit array. On insertion, the corresponding bits are set. On query, if all mapped bits are set the element is 'probably' in the set; if any bit is unset, the element is definitely absent. This visualization shows insertions lighting up teal bits, then queries checking positions in gold or coral.