Avoid an expensive lookup when the answer is definitely no#
A crawler has billions of known URLs. An exact membership set may be too large to keep in fast memory, so a Bloom filter hashes inserted items into a compact bit array.
Check several hashed bit positions
11111101
| Result | Meaning |
|---|---|
| Definitely not present | At least one checked bit is unset |
| Possibly present | All bits are set; verify because collisions can cause a false positive |
With a correctly implemented filter under its stated insertion assumptions, inserted items are not reported absent. Deletion, resizing, or implementation variants require their own contracts. Never use a Bloom filter alone where exact membership is required.
Related practice problems
Use the manifest-backed prompts below to apply this lesson in a complete design.
- Bloom filterRedis Documentation
Reach this point to mark the lesson as read.