Structure de données probabiliste et économe en espace pour les requêtes d'appartenance approximative à un ensemble : elle peut produire des faux positifs mais jamais de faux négatifs ; elle utilise plusieurs fonctions de hachage pour positionner des bits dans un tableau d'octets de taille fixe.

Principe

Utiliser plusieurs fonctions de hachage indépendantes pour mapper chaque élément sur plusieurs positions d'un tableau de bits ; l'appartenance se teste en vérifiant ces bits : une collision peut provoquer un faux positif, l'existence d'au moins un bit nul garantit l'absence.

Démonstration

Un correcteur orthographique insère un grand dictionnaire dans un filtre de Bloom ; pour vérifier un mot on teste tous les bits associés. Si un bit est zéro, le mot est définitivement absent ; si tous sont à un, le mot est probablement présent et un contrôle exact plus lent est utilisé pour confirmer.

Mauvaise application

Utiliser un filtre de Bloom classique là où des suppressions fiables sont nécessaires sans recourir à une variante comptante, ou supposer un taux de faux positifs nul et supprimer la vérification secondaire ; cela conduit à des erreurs d'appartenance.

Conséquence

Tests d'appartenance très économes en mémoire avec un taux de faux positifs réglable et un coût CPU faible par requête, permettant de filtrer à bas coût les candidats dans des flux ou systèmes distribués, au prix de vérifications occasionnelles.

Inversion

Un ensemble de hachage exact (par exemple une table de hachage à chaînage) qui stocke chaque élément explicitement, ne renvoie jamais de faux positifs mais consomme beaucoup plus de mémoire et peut coûter plus cher par opération.

Limite

Ne stocke pas les éléments et ne permet pas l'énumération fiable ; ne fournit pas de comptages exacts (sauf extension en filtre de Bloom comptant) ; le taux de faux positifs augmente avec la saturation et dépend du nombre de hachages, de la taille du tableau et du nombre d'inserts.

Tension sémantique

Appartenance probabiliste approximative (filtre de Bloom) versus structures d'appartenance exactes (ensembles de hachage) : les deux répondent à 'x appartient-il à S ?' mais échangent l'espace et la certitude.

Synthèse

Un filtre probabiliste compact qui échange un taux contrôlé de faux positifs contre de substantielles économies d'espace en représentant l'appartenance par plusieurs positions hachées dans un tableau de bits de taille fixe, adapté quand des vérifications supplémentaires occasionnelles sont acceptables.