The Bloom filter, conceived by Burton Howard Bloom in 1970,[1] is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives.
via en.wikipedia.org
I've never understood how this works, only that it exists. I've also never understood how you might construct something that behaves this way that isn't built with a computer.
Note: broken links fixed Oct 5 2010
