Quelles sont les fonctions de hachage entier acceptant une clé de hachage entière?

Question

Quelles sont les fonctions de hachage entier acceptant une clé de hachage entière?

Answer 1

J'ai trouvé l'algorithme suivant fournit une très bonne distribution statistique. Chaque entrée peu affecte chaque bit de sortie avec environ 50% de probabilité. Il n'y a pas de collisions (chaque entrée différent de sortie). L'algorithme est rapide, sauf si le CPU n'a pas intégré entier multiplication de l'unité. Le code en C, en supposant int 32 bits (pour Java, remplacez - >> avec >>> et retirez unsigned):

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x);
    return x;
}

Le nombre magique a été calculé en utilisant un spécial multi-thread programme de test qui a duré plusieurs heures, qui calcule l'effet d'avalanche (le nombre de bits de sortie que le changement si une seule entrée bit est modifié; ils devraient être près de 16 en moyenne), l'indépendance de la sortie changements bits (bits de sortie ne doit pas dépendre les uns des autres), et la probabilité d'un changement dans chaque bit de sortie si aucune entrée bit est modifié. Les valeurs calculées sont mieux que les 32 bits de l'outil de finalisation utilisé par MurmurHash, et presque aussi bien (pas tout à fait) comme lors de l'utilisation de l'AES.

Answer 2

Knuth est multiplicative méthode:

hash(i)=i*2654435761 mod 2^32

En général, vous devez choisir un multiplicateur qui est dans l'ordre de votre hachage de taille (2^32 dans l'exemple) et n'a pas de facteurs communs avec elle. De cette façon, la fonction de hachage couvre l'ensemble de votre espace de hachage uniforme.

Edit: Le plus grand inconvénient de cette fonction de hachage est qu'il préserve la divisibilité, donc si votre entiers sont tous divisibles par 2 ou par 4 (qui n'est pas rare), leurs empreintes sera trop. C'est un problème dans les tables de hachage - vous pouvez vous retrouver avec seulement 1/2 ou 1/4 de les seaux utilisés.

Answer 3

Cela dépend de la manière dont vos données sont distribuées. Pour un compteur simple, la fonction la plus simple

 f(i) = i
 

ça va être bien (je pense que c'est optimal, mais je ne peux pas le prouver).

Answer 4

Cette page répertorie quelques fonctions de hachage simples qui ont tendance à être décentes en général, mais tout hachage simple a des cas pathologiques où il ne fonctionne pas bien.

Answer 5

• Méthode multiplicative 32 bits (très rapide) voir @rafal

   #define hash32(x) ((x)*2654435761)
  #define H_BITS 24 // Hashtable size
  #define H_SHIFT (32-H_BITS)
  unsigned hashtab[1<<H_BITS]  
  .... 
  unsigned slot = hash32(x) >> H_SHIFT
   

• 32 bits et 64 bits (bonne répartition) sur: MurmurHash

• Fonction de hachage entier