You have a billion URLs in your collection and want to know if a new URL has been encountered yet. Storing them all in a hash table would take up tens of GB. A Bloom filter does the same job using just a few hundred MB.
How It Works
A bit array, initially filled with zeros, along with k different hash functions.
- Add an element: hash it using all k functions, and set the corresponding k positions to 1
- Check: Hash it and check the k positions. If any position is 0, the element has definitely never been added. If all k positions are 1, it’s possible that
The second case is where an error might occur: those bits may have been set by other elements. This is called a false positive.
The most important characteristic
There are never false negatives. If a Bloom filter says "no," that is a definitive answer. This determines how it is used: to pre-process a costly lookup to eliminate most cases where a lookup is unnecessary.
Typical Applications
- A database that checks whether a key is in a file on disk, before actually reading the disk
- A distributed cache avoids network calls for keys that definitely do not exist
- The web crawler filters URLs it has already encountered
What Must Be Accepted
Unable to delete an element—turning off one bit could break another element that shares that bit. And the number of elements must be estimated in advance: if too many are included, the false positive rate skyrockets, to the point where nearly every answer is "possibly," and the structure becomes useless.
Thảo luận