Mise en œuvre de la fonction de hachage universelle pour les filtres de bloom en C

Question

Im simulant l'approximation de l'intersection des ensembles à l'aide de filtres bloom. J'ai essayé beaucoup de fonctions de hachage simples pour hacher les valeurs du filtre. mais ce n'est pas bon pour éviter les collisions. alors quelqu'un a suggéré une fonction de hachage universelle. mais je ne suis pas sûr de comment cela fonctionne. mon programme est conçu pour passer juste la clé à la fonction de hachage et la fonction de hachage renvoie le hachage. quelqu'un peut-il m'aider avec le code? merci

Answer 1

ne vous inquiétez pas de la collision des fonctions de hachage lorsqu'il est utilisé avec des filtres bloom. vous n'avez pas à gérer la collision dans ce cas. juste obtenir k différent a des fonctions qui définissent k bits dans un tableau de m-bits lorsque vous insérez un élément. au moment de la requête, vous utilisez à nouveau toutes les fonctions de k hash pour vérifier tous les k-bits; si l'un d'entre eux n'est pas défini, la recherche est fausse. si tout est réglé, vous ne pouvez rien conclure (résultats faux positifs). Ceci est clairement expliqué dans wiki:

http://en.wikipedia.org/wiki/Bloom_filter