Un filtre Bloom est une structure de données qui permet aux ordinateurs de voir si un élément donné se trouve dans un ensemble. Les filtres Bloom utilisent pour cela des fonctions de hachage. Pour chaque élément qui est ajouté, une valeur de hachage est calculée. Lorsqu'un nouvel élément est ajouté, sa valeur de hachage est comparée à celle des autres éléments de l'ensemble. Un filtre Bloom est une structure de données probabiliste. Il est possible d'obtenir un faux positif, mais pas un faux négatif. En d'autres termes, une requête renvoie soit "peut-être dans l'ensemble", soit "certainement pas dans l'ensemble". Des éléments peuvent être ajoutés à l'ensemble, mais pas supprimés. Pour chaque élément ajouté, la probabilité d'obtenir un faux positif augmente.
Edward Bloom a proposé le filtre Bloom en 1970. Dans l'article, Bloom suppose qu'il existe un algorithme pour mettre un trait d'union entre les mots en fin de ligne. Selon l'exemple, la plupart des mots ont un schéma de césure simple. Mais environ 10 % des mots nécessitent de longues recherches pour trouver la bonne règle. Son cas est celui de la césure d'environ 500 000 mots. Il a vu que l'utilisation des techniques de hachage "normales" sans erreur, le stockage des modèles de césure, nécessiterait beaucoup de mémoire. Il a découvert qu'en utilisant sa technique, il pouvait éliminer la plupart des recherches. Par exemple, une zone de hachage de seulement 15 % de la taille requise par un hachage idéal sans erreur élimine encore 85 % des accès au disque.
Plus généralement, moins de 10 bits par élément sont nécessaires pour une probabilité de faux positif de 1 %, indépendamment de la taille ou du nombre d'éléments dans l'ensemble.