Bloom Filter

A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It is 'probabilistic' because it can produce false positive matches but not false negatives. In other words, a query might return 'possibly in set' or 'definitely not in set'. A Bloom filter consists of a bit array of `m` bits, initially all set to 0, and `k` different hash functions. To add an element to the filter, we feed it to each of the `k` hash functions to get `k` array positions. We then set the bits at all these positions to 1. To query for an element, we again feed it to the `k` hash functions to get `k` positions. We then check the bits at all these positions. If any of the bits is 0, the element is 'definitely not in the set' (because if it were, all its corresponding bits would have been set to 1). If all bits are 1, the element is 'possibly in the set'. It's possible because these bits might have been set to 1 by other elements. Bloom filters are extremely useful when memory is a concern and a small false positive rate is acceptable. They are used in applications like network routers, web browser caches to check for malicious URLs, and databases (like Google Bigtable) to reduce disk lookups for non-existent keys.