Explanation
- A **Bloom Filter** is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It can produce false positives but never false negatives.
-
-
Steps
- Hash the element using multiple hash functions.
- Set bits at the positions returned by the hash functions.
- Query: Check if all bits corresponding to the hash values are set. If yes, the element is possibly in the set; otherwise, it’s definitely not.
-
Time Complexity
- O(k) for insertions and queries, where
kis the number of hash functions.
- O(k) for insertions and queries, where