A tiny bit array that answers "have I seen this?" with either "definitely not" or "probably": each item switches on k bits chosen by k hash functions, and a test checks whether all of its k bits are on.
- Typical operation
- O(k)
- Space
- O(m)
A tiny bit array that answers "have I seen this?" with either "definitely not" or "probably": each item switches on k bits chosen by k hash functions, and a test checks whether all of its k bits are on.