A Garden Variety of Bloom Filters
matthias.vallentin.net
matthias.vallentin.net
He has a nice interactive demo with an explanation on how it works.
I like Jason's demo and graphic better, but I go into a bit more detail. The blog post under discussion goes into much more detail than me, and assumes a bit more knowledge of the reader.
If you add letters a - z as keys, then do a search for some numbers, such as the number 6, you get "Probably there". I was under the impression that a Bloom Filter could determine if something was definitely NOT in the data set, in which case this the example isn't working.
Please correct me if I'm wrong :)
EDIT: After playing around with it some more I'm questioning if I do fully understand how it is supposed to work. It seems there are many cases of "Probably there" when the key definitely is not. So I'm guessing in those cases you'd want to search the set to make sure?
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.