You are slightly confused. False positives do indeed happen, but false negatives can never happen (if one of the bits aren't set for the corresponding hash, the

You are slightly confused. False positives do indeed happen, but false negatives can never happen (if one of the bits aren't set for the corresponding hash, then it is guaranteed to have never been added before). Collisions in hash tables are related to false positives in Bloom Filters. Also, regarding your last statement: You don't always need to look at the actual set in some cases, but for a lot you do. Bloom Filters give you a fast, compact way to prevent a lot of unnecessary searching. Spell Checkers, for example, you could reduce the amount of times you had to search through the dictionary, or for finding files or something on disk, you could eliminate a percentage of searches for the files. How much these can be reduced is related to the size of your Bloom filter.