Diviser la totalité de la plage de hachage en n plages égales

Question

Je cherche à prendre une plage de hachage (md5 ou sha1) et la diviser en n plages égales. Par exemple, si m (num nodes) = 5, la plage de hachage entière serait divisée par 5 de sorte qu'il y aurait une distribution uniforme des plages de clés. Je voudrais que n = 1 (nœud 1) soit du début de la gamme de hachage à 1/5, 2 de 1/5 à 2/5, etc tout le chemin jusqu'à la fin.

Fondamentalement, j'ai besoin d'avoir des plages de clés mappées à chaque n de telle sorte que lorsque je hachage une valeur, il sait quel n va prendre en compte cette plage.

Je ne connais pas encore le hachage et je ne sais pas très bien où je pourrais commencer à résoudre ce problème pour un projet. Toute aide que vous pourriez donner serait géniale.

Answer 1

Si vous pouvez supporter un peu très dur pour supprimer le biais (toute puissance de deux est impossible de diviser uniformément en 5, donc il doit y avoir un certain biais), puis modulo (% en C et beaucoup d'autres langues avec C- comme syntaxe) est le moyen de diviser la gamme complète en 5 partitions de taille presque identique.

Tout message m avec md5(m)%5==0 est dans la première partition, etc.

Answer 2

Si vous cherchez à placer une valeur de hachage dans un certain nombre de « seaux » de façon uniforme, puis quelques calculs simples fera l'affaire. Attention aux cas arrondis ... Vous feriez mieux d'utiliser une puissance de 2 pour la valeur BUCKETS.

ce code est en python, en passant, qui prend en charge les grands entiers ...

BUCKETS = 5 
BITS  = 160 

BUCKETSIZE = 2**BITS/BUCKETS 

int('ad01c5b3de58a02a42367e33f5bdb182d5e7e164', 16)/BUCKETSIZE == 3 
int('553ae7da92f5505a92bbb8c9d47be76ab9f65bc2', 16)/BUCKETSIZE == 1 
int('001c7c8c5ff152f1cc8ed30421e02a898cfcfb23', 16)/BUCKETSIZE == 0