Dernière mise à jour : 2026-07-13

Dimensionnement d'un filtre de Bloom

Un filtre de Bloom est un moyen compact de répondre à une seule question : « ai-je probablement déjà vu cet élément ? ». Il ne stocke aucune clé, seulement un tableau de bits, et échange une petite probabilité réglable de faux positif contre une grande économie de mémoire. Deux nombres décident de sa forme — combien d'éléments vous prévoyez de stocker et à quelle fréquence vous tolérez une fausse correspondance — et il en découle directement la taille optimale du tableau de bits et le nombre de fonctions de hachage.

La formule

Pour $n$ éléments prévus et un taux de faux positifs cible $p$, le tableau de bits qui minimise la mémoire a pour longueur

Le nombre optimal de fonctions de hachage est alors

arrondi à l'entier le plus proche. Ici $m$ est le nombre de bits, $k$ le nombre de fonctions de hachage indépendantes appliquées à chaque élément, et $\ln 2 \approx 0{,}693$. Comme $p$ est une probabilité inférieure à 1, son logarithme naturel est négatif, si bien que les deux formules produisent des valeurs positives.

Exemple résolu. Un filtre pour un million d'éléments ($n = 1{,}000{,}000$) avec une cible de 1 % ($p = 0{,}01$) :

Un million d'éléments à 1 % coûtent donc environ 1,14 Mio de mémoire et sept fonctions de hachage — soit à peu près 9,6 bits par élément, un chiffre valable pour tout nombre d'éléments à cette précision.

Bits par élément et l'échelle de précision

Comme la formule de taille est linéaire en $n$, le coût de stockage par élément, $m / n = -\ln p / (\ln 2)^2$, ne dépend que du taux cible. C'est donc une mesure nette pour comparer des budgets de précision.

Chaque division par dix du taux de faux positifs ajoute environ 4,8 bits par élément et à peu près trois fonctions de hachage. La mémoire ne croît que linéairement alors que le taux d'erreur chute géométriquement, ce qui fait tout l'intérêt des filtres de Bloom.

Pourquoi le nombre de hachages compte

À taille de tableau fixée, trop peu de fonctions de hachage laissent les bits épars et faciles à toucher par hasard, tandis que trop de fonctions remplissent le tableau si densément que presque tous les bits sont à 1. Le point optimal met la moitié des bits à 1 et se situe à $k = (m/n)\ln 2$. Comme $k$ doit être entier, le calculateur l'arrondit, et le taux de faux positifs réel est recalculé à partir de cette valeur arrondie :

Dans l'exemple ci-dessus, le $k = 7$ arrondi donne environ 1,004 %, un rien au-dessus de la cible de 1 % parce que le $k$ idéal valait 6,64 et non un entier.

Ce qu'un filtre de Bloom peut et ne peut pas faire

Un filtre de Bloom ne produit jamais de faux négatif : s'il dit qu'un élément est absent, il l'est vraiment. La seule erreur est un faux positif, dont ce calculateur dimensionne le taux. Les filtres standard acceptent l'insertion et la requête, mais pas la suppression, car les bits sont partagés entre éléments — effacer les bits de l'un pourrait corrompre les autres. Quand la suppression est requise, un filtre de Bloom à compteurs remplace chaque bit par un petit compteur au prix de plusieurs fois la mémoire, et un filtre coucou offre la suppression pour une taille comparable.

Une réserve : un filtre est dimensionné pour un $n$ fixe. Insérez bien plus d'éléments que prévu et le tableau sature, poussant le taux de faux positifs au-dessus de la cible. Si une croissance est probable, dimensionnez d'emblée pour le nombre supérieur ou utilisez une conception extensible qui chaîne plusieurs filtres.

L'arrondi en pratique

Le nombre de bits $m$ issu de la formule est rarement un chiffre rond. Les implémentations réelles allouent des mots machine ou des pages de mémoire entiers, donc elles arrondissent $m$ au supérieur, ce qui pousse le taux de faux positifs obtenu légèrement sous la cible — un petit bonus. La taille affichée ici est le minimum théorique avant cet arrondi.

Calculs associés

Les filtres de Bloom reposent sur le hachage, si bien que la probabilité que deux éléments partagent un même haché obéit à la même mathématique des anniversaires — voyez le Calculateur de probabilité de collision de hachage. Pour les identifiants de longueur fixe, le Calculateur de probabilité de collision d’UUID applique le même raisonnement aux UUID, et le Calculateur d'entropie de Shannon mesure l'information que porte un jeu de données.