Bloom Filter Algorithm

A Bloom filter is a probabilistic algorithm for testing whether an element belongs to a set, built to use far less memory than storing the set outright at the cost of occasionally returning a wrong answer in one specific direction: a Bloom filter can report that an element is possibly in the set when it is not, a false positive, but it will never wrongly report that an element already in the set is not, since it is designed to have no false negatives. It works with a bit array and several independent hash functions: adding an element hashes it through each function to get several positions in the array and sets the bit at each of those positions to one, and testing an element hashes it the same way and checks whether every one of those positions is already set, concluding the element is definitely absent if even one bit is unset and otherwise treating it as present, accepting the small chance of a false positive. Burton Howard Bloom conceived the technique in 1970, originally proposing it for situations, such as a hyphenation dictionary, where an error-free lookup structure would need impractical amounts of memory but a much smaller probabilistic structure could still filter out the great majority of unnecessary lookups.