Bloom Filters -- A Tutorial, Analysis, and Survey

Bloom filters use superimposed hash transforms to provide a probabilistic membership test. The only types of errors are false positives (non-members being reported as members). Non-members are typically detected quickly (requiring only two probes in the optimal case).

This article surveys modern applications of this technique (e.g., in spell checking and Web caching software) and provides a detailed analysis of their performance, in theory and practice. The article concludes with practical advice about implementing this useful and intriguing technique.