Les filtres de bloom sont-ils réellement plus rapides que les hachages, même en tenant compte du cache?

Les filtres Bloom sont vraiment superbes lorsque vous considérez que vous pouvez déterminer si un Int est dans un ensemble avec une certitude de 99% en temps constant. Mais il en va de même pour les hachages, à la seule différence que, dans un hachage, la plupart du temps, vous n'accédez à la mémoire qu'une seule fois. Avec les filtres de floraison, vous devez y accéder ~ 7 fois par demande dans des endroits complètement éloignés , vous aurez donc plusieurs échecs de cache par demande.

Suis-je en train de manquer quelque chose?

Vous ne savez pas comment les deux structures de données gèrent les collisions de hachage. Les filtres de bloom ne stockent pas les valeurs réelles, donc l'espace requis est la taille constante de la matrice désignée. Au lieu de cela, si vous utilisez un hachage traditionnel, il essaie de stocker toutes les valeurs que vous lui donnez, donc il grandit avec le temps.

Prenons une fonction de hachage simplifiée (pour un exemple uniquement!) f(x) = x % 2. Maintenant , vous entrez les nombres entiers suivants: 2, 3, 4, 5, 6, 7.

Hash standard: les valeurs données seront hachées, et nous nous retrouvons avec beaucoup de collisions dues à f(2) = f(4) = f(6) = 0et f(3) = f(5) = f(7) = 1. Néanmoins, le hachage stocke toutes ces valeurs et il pourra vous dire qu'il 8n'y est pas stocké. Comment ça fait ça? Il garde une trace des collisions et stocke toutes les valeurs avec la même valeur de hachage, puis lorsque vous l'interrogez, il compare également votre requête. Examinons donc la carte pour 8:, f(8) = 0donc elle va chercher dans un compartiment où nous avons déjà inséré 2, 4, 6et doit faire 3 comparaisons afin de vous dire que cela 8ne faisait pas partie de l'entrée.

Filtre Bloom: Normalement, chaque valeur d'entrée est hachée contre kdifférentes fonctions de hachage. Encore une fois, pour simplifier, supposons simplement que nous n'utilisons que la fonction de hachage unique f. Nous avons alors besoin d'un tableau de 2 valeurs et lorsque nous rencontrons l'entrée, 2cela signifie qu'en raison de f(2) = 0nous définissons la valeur du tableau en position 0sur la valeur 1. La même chose se produit pour 4et 6. De même, les entrées 3, 5, 7définissent chacune la position du tableau 1sur valeur 1. Maintenant, nous demandons si 8faisait partie de l'entrée: f(8) = 0et le tableau à la position 0est 1, donc le filtre de floraison prétendra faussement que cela 8faisait effectivement partie de l'entrée.

Pour être un peu plus réaliste, considérons que nous ajoutons une deuxième fonction de hachage g(x) = x % 10. Avec cela, la valeur d'entrée 2conduit à deux valeurs de hachage f(2) = 0et g(2) = 2et les deux positions de tableau correspondantes seront définies sur 1. Bien sûr, le tableau doit maintenant être au moins de taille 10. Mais lorsque nous interrogerons, 8nous vérifierons le tableau à la position 8due à g(8) = 8, et cette position sera toujours 0. C'est pourquoi des fonctions de hachage supplémentaires diminuent les faux positifs que vous obtiendrez.

Comparaison: le filtre kBloom utilise des fonctions de hachage, ce qui signifie que kdes positions de tableau aléatoires sont accessibles. Mais ce chiffre est exact. Au lieu de cela, le hachage ne vous garantit qu'un temps d'accès constant amorti, mais peut se générer en fonction de la nature de votre fonction de hachage et des données d'entrée. Il est donc généralement plus rapide, sauf pour les cas dé-générés.

Cependant, une fois que vous avez une collision de hachage, le hachage standard devra vérifier l'égalité des valeurs stockées par rapport à la valeur de la requête. Ce contrôle d'égalité peut être arbitrairement coûteux et ne se produira jamais avec un filtre de bloom.

En termes d'espace, le filtre de bloom est constant, car il n'est jamais nécessaire d'utiliser plus de mémoire que le tableau désigné. D'un autre côté, le hachage se développe dynamiquement et peut devenir beaucoup plus important en raison du fait de devoir suivre les valeurs en collision.

Compromis: Maintenant que vous savez ce qui est bon marché et ce qui ne l'est pas et dans quelles circonstances, vous devriez pouvoir voir le compromis. Les filtres Bloom sont parfaits si vous voulez détecter très rapidement qu'une valeur a été vue précédemment, mais peut vivre avec des faux positifs. D'autre part, vous pouvez choisir la carte de hachage si vous voulez une exactitude garantie au prix de ne pas pouvoir évaluer exactement votre temps d'exécution, mais pouvez accepter des cas dégénérés occasionnellement qui peuvent être beaucoup plus lents que la moyenne.

De même, si vous êtes dans un environnement mémoire limité, vous pouvez préférer les filtres de floraison pour leur garantie d'utilisation de la mémoire.

Les cas d'utilisation des filtres de floraison et des hachages sont distincts et pour la plupart disjoints, la comparaison directe n'a donc pas de sens. En outre, cela dépendra des détails techniques des implémentations car il existe de nombreuses façons de gérer les collisions de hachage avec différents compromis.

Le filtre de floraison peut déterminer si l'élément est dans un ensemble pour des ensembles énormes , avec une probabilité raisonnable, mais pas exactement, en utilisant une quantité modeste de mémoire. D'énormes trillions d'éléments. Mais ils ne sont jamais exacts. Vous ne pouvez réduire la quantité de faux positifs qu'en utilisant plus de mémoire ou plus de fonctions de hachage.

D'un autre côté, les tables de hachage sont exactes, mais elles doivent stocker l'ensemble. Des trillions d'éléments nécessiteraient donc des terrabytes de mémoire (et ce ne sont que des trillions américains). Ils peuvent également stocker des données supplémentaires pour chaque élément, ce que les filtres de floraison ne peuvent pas.

Ainsi, les filtres de floraison sont utilisés lorsque vous avez une méthode lente pour obtenir des données pour un membre (qui implique une requête sur le serveur, des lectures à partir du disque, etc.) d'un grand ensemble (qui ne tient pas en mémoire ou il est impossible de les transférer vers le client ou tel) et que vous souhaitez éviter d'exécuter l'opération lente pour les objets qui ne sont pas dans l'ensemble.