Bloom Filters

A Bloom Filter is a space-efficient data structure used to test whether an item is in a set. It can quickly indicate if an item is definitely not in the set or possibly in it. To do this, it uses multiple hash functions to map items to positions in a fixed-size bit array. When adding an item, the bits at these positions are set to 1. To check for an item, the same hash functions are applied; if all corresponding bits are 1, the item might be in the set (with some chance of false positives). If any bit is 0, the item is definitely not in the set.