Bloom Filter: Comment trouver des fonctions de hachage k?

Question

Un filtre Bloom nécessite k fonctions de hachage, qui renvoient une valeur comprise entre 0 et m (m est la longueur du tableau de bits). Je dois implémenter un tel filtre bloom et j'ai déjà lu quelques articles théoriques sur ces filtres (comment ils fonctionnent, combien de fonctions de hachage vous avez besoin, comment se comporte l'erreur etc.)

Maintenant j'ai deux questions sur les fonctions de hachage :

• Comment trouver les fonctions de hachage k - quelles fonctions de hachage dois-je utiliser?
• Comment trouver les fonctions de hachage qui retournent une valeur entre 0 et m? Alternativement, comment puis-je mapper la sortie d'une fonction de hachage à la plage 0-m?

Answer 1

Vous pouvez utiliser cette - http://en.wikipedia.org/wiki/Universal_hashing

Answer 2

Vous pouvez obtenir un tas de valeurs de hachage à un moment donné avec une fonction de hachage cryptographique comme MD5 ou SHA. Diviser la valeur de hachage cryptographique en N bits de m bits, et les traiter comme vous le feriez en sortie de N fonctions de hachage normales.

Answer 3

• Les caractéristiques des fonctions de hachage k qui doivent être utilisées sont
  donné sur la page wikipedia: Bloom Filter et aller dans le
  Description de l'algorithme où il est dit - L'exigence de la conception k différent hachage indépendant fonctions ...

• Pour de bons tutoriels sur le hachage universel: Nice MIT lecture

Answer 4

U pourrait utiliser toutes les fonctions de hachage .... il existe de nombreuses fonctions de hachage simple hash disponibles dans le réseau. Référez http://en.wikipedia.org/wiki/List_of_hash_functions

Utilisez une fonction de hachage pour obtenir une valeur de hachage et, pour l'obtenir dans la plage de 0 m, utilisez l'opérateur de module (%). i.e bitlocation = hachage% m;

il pourrait ne pas être efficace, mais il fonctionne ...