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.