Aller au contenu
Omnikalc

Calculateur de filtre de Bloom

Saisissez le nombre d’éléments et le taux de faux positifs accepté pour obtenir la taille du tableau de bits, le nombre de fonctions de hachage et la mémoire nécessaire.

Mis à jour le
Vos paramètres

Valeur hors limites

%

Valeur hors limites

Résultats

Taille du tableau de bits (millions de bits)

9,59

Mémoire
1,20 Mo
Bits par élément
9,59
Nombre de fonctions de hachage
7
Taux de faux positifs avec le nombre de fonctions arrondi
1,004 %
Mémoire économisée par rapport à des clés de 64 bits
85,0 %

Le calculateur de filtre de Bloom donne la taille du tableau de bits, le nombre de fonctions de hachage et la mémoire nécessaires pour un nombre d’éléments et un taux de faux positifs acceptés.

Comment se fait le calcul

  • Saisissez le nombre d’éléments à stocker.
  • Saisissez le taux de faux positifs accepté, en pourcentage.
  • Le calculateur donne les bits, la mémoire, les bits par élément, les fonctions de hachage, le taux réel de faux positifs et l’économie par rapport au stockage des clés.

Exemple

Pour 1 000 000 d’éléments et un taux de 1 %, m = −10⁶ × ln 0,01 / (ln 2)² = 9,59 millions de bits, soit 1,20 Mo, ou 9,59 bits par élément. Le nombre optimal de fonctions est de 7, et le taux réel de faux positifs avec lui est de 1,004 %.

Pourquoi c’est utile

Le calculateur aide les développeurs, les ingénieurs de bases de données et les étudiants à dimensionner un filtre de Bloom avant de le construire, et à peser la mémoire face au nombre de recherches inutiles.

À savoir

Le taux de faux positifs monte vite si vous insérez plus d’éléments que prévu, donc dimensionnez le filtre pour le nombre maximal d’éléments. Chaque division du taux par dix coûte environ 4,8 bits de plus par élément. Un taux de 0,1 % demande environ 14,4 bits par élément et 10 fonctions. Utilisez des fonctions de hachage indépendantes et rapides, ou deux fonctions combinées pour en donner davantage, une astuce qui garde la qualité. Les filtres de coucou et les filtres de quotient offrent la suppression et une meilleure occupation de l’espace à faible taux. Un filtre placé devant un stockage lent, comme un disque ou un service distant, est rentable quand la plupart des recherches portent sur des clés absentes.

Outils liés

Le calculateur de collisions de hachage couvre l’effet des anniversaires, celui d’étapes de recherche dichotomique compte les comparaisons, celui d’entropie de Shannon mesure l’information et celui de taux de succès du cache décrit les caches.

Questions fréquentes

Qu’est-ce qu’un filtre de Bloom ?

Un filtre de Bloom est une structure compacte qui indique si un élément est peut-être dans un ensemble ou sûrement absent. Il met à 1 k bits d’un tableau de bits pour chaque élément ajouté. Il ne donne jamais de faux négatif, mais il peut donner un faux positif, dont le taux dépend des bits par élément et de k.

Comment choisit-on la taille et le nombre de fonctions ?

Pour un taux visé p, la taille optimale est m = −n ln p / (ln 2)², soit environ 9,6 bits par élément pour 1 %, et le nombre optimal de fonctions est k = (m / n) ln 2. Le calculateur arrondit k à un entier et affiche le taux réel obtenu.

Où utilise-t-on les filtres de Bloom ?

Les bases de données et les magasins clé-valeur s’en servent pour éviter des lectures de disque pour des clés absentes, les navigateurs et les caches pour éviter des recherches inutiles, et les systèmes réseau pour tester l’appartenance à moindre coût. Ils ne permettent pas de supprimer des éléments, sauf avec une variante à compteurs.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.