Calculatrice de Filtre de Bloom (Taille, Fonctions de Hachage, Taux de Faux Positifs)
Combien de bits, quelle mémoire et combien de fonctions de hachage il faut à un filtre de Bloom pour stocker un nombre d'éléments avec un taux de faux positifs acceptable.
Résultats
La ligne en pointillé marque la valeur que vous avez saisie.
Ce que fait cet outil
Un filtre de Bloom répond à « cet élément est-il dans l'ensemble ? » par « certainement pas » ou « probablement oui », avec un petit tableau de bits et plusieurs fonctions de hachage. Pour n éléments et un taux de faux positifs p, la taille optimale est m = −n ln p ÷ (ln 2)² bits, et le meilleur nombre de fonctions est k = (m ÷ n) ln 2, soit environ 1,44 × log₂(1 ÷ p) bits par élément. Un taux de 1 % coûte environ 9,6 bits par élément et 0,1 % environ 14,4, quels que soient les éléments. Le taux de faux positifs grimpe vite si l'on insère plus d'éléments que prévu, et un filtre de Bloom classique ne permet pas de supprimer.
Formule
m = −n ln p ÷ (ln 2)² · k = (m ÷ n) ln 2 · p = (1 − e^(−k n ÷ m))^k
Variables
| Symbole | Signification | Unité |
|---|---|---|
nn | Nombre d'éléments à stocker | — |
pp | Taux de faux positifs accepté | — |
M | Taille du tableau de bits | bit |
MB | Mémoire | MiB |
K | Nombre de fonctions de hachage | — |
BP | Bits par élément | — |
PR | Taux de faux positifs avec ce nombre entier de fonctions | — |
Exemple résolu
- Nombre d'éléments à stocker1 000 000
- Taux de faux positifs accepté0,01
- Taille du tableau de bits9 585 059 bit
- Mémoire1,14 MiB
- Nombre de fonctions de hachage7
- Bits par élément9,59
- Taux de faux positifs avec ce nombre entier de fonctions0,01004
Limites
- Le résultat est une estimation fondée uniquement sur les valeurs saisies. Les situations réelles comportent souvent des facteurs que cette calculatrice ignore.
- La formule suppose des conditions idéales : pas de frottement, pas de résistance de l'air et pas de pertes de rendement sauf si vous les saisissez.