What is the difference between a bloom filter and a hash-based set in data structures used in security?

• A. Bloom filter is a probabilistic data structure that tests membership with potential false positives; hash-based set stores exact membership but uses more memory.
• B. Bloom filter stores exact membership with no false positives.
• C. Hash-based set tests membership probabilistically and can have false positives.
• D. Hash-based sets are never used in security applications.

Answer: (A)

The key idea is that a Bloom filter is a probabilistic membership test, while a hash-based set stores exact membership. A Bloom filter uses a compact bit array and several hash functions. When you add an item, you set multiple bits; when you check for membership, you see if all those bits are set. If any are 0, the item is definitely not in the set. If all are 1, the item might be in the set, but there can be false positives due to collisions with other items. It never reveals false negatives, but it can falsely say “yes, it’s in there” when it isn’t. Because of this, Bloom filters are extremely space-efficient for large datasets and fast to query, which is why they’re popular for initial screening in security systems (like quickly checking against huge blacklists).

A hash-based set, by contrast, stores the actual elements and uses a hash table to enable exact membership checks. If you query for an item, you get a definitive yes or no based on whether the exact element is stored. This provides precise results (no false positives or negatives) but requires more memory per item and supports operations like deletions and enumerating items.

In security applications, you’d typically use a Bloom filter when you want a fast, scalable filter that may tolerate occasional false positives, and follow it with a precise check against a hash-based set for final verification. The described choice reflects this distinction: the Bloom filter is probabilistic with possible false positives, while a hash-based set stores exact membership.