Le filtre de Bloom a échangé quelques réponses erronées contre une empreinte mémoire minuscule

Lorsqu'un ensemble d'éléments est énorme, stocker chaque clé est impossible, mais il faut tout de même savoir si quelque chose s'y trouve. L'exemple de Bloom était un dictionnaire de 500 000 mots où seulement 10 % des mots utilisent des règles de césure coûteuses : la vérification judicieuse consistait à éviter un accès disque, mais le dictionnaire était trop volumineux pour un hachage sans erreur dans la mémoire disponible.

Un filtre de Bloom y parvient avec un tableau de bits et plusieurs fonctions de hachage. L'ajout d'un élément positionne les bits à ces positions, et le test consiste à demander s'ils sont tous positionnés. Si l'un d'eux est à zéro, l'élément est certainement absent, il n'y a donc pas de faux négatifs ; si tous sont positionnés, l'élément peut être dans l'ensemble ou avoir simplement collisionné avec d'autres éléments, produisant un faux positif.

Comme l'erreur est unilatérale et ajustable, la structure reste petite tout en éliminant la plupart des lectures disque inutiles. Une zone de hachage de seulement 18 % de la taille nécessaire à un hachage sans erreur éliminait 87 % des accès disque, et moins de dix bits par élément donnent un taux de faux positifs d'environ 1 %.

Faire dire « peut-être » à un tableau de bits, jamais « non » par erreur

Les faux positifs sont acceptables lorsque le coût se limite à une vérification supplémentaire, mais un faux « non » ferait perdre des données.

Un tableau de bits avec quelques fonctions de hachage stocke l'appartenance en quelques bits par élément.

Il supprime la plupart des recherches coûteuses sur disque ou sur réseau sans stocker l'ensemble réel.

Si une petite chance de dire oui est acceptable mais qu'un faux non ne l'est pas, acceptez délibérément l'erreur unilatérale ; autoriser quelques faux positifs est souvent le seul moyen de faire tenir un ensemble énorme en mémoire.

Les filtres de Bloom se sont répandus dans les bases de données, les caches, les correcteurs orthographiques et le routage réseau pour éviter des recherches coûteuses, et apparaissent dans des systèmes allant de PostgreSQL et Apache Cassandra à Chromium et à la mise en cache à grande échelle ; l'astuce sous-jacente consistant à accepter une erreur unilatérale pour gagner de l'espace est aujourd'hui une primitive standard dans les systèmes informatiques.