Quelle fonction de hachage d’entier est-elle bonne si elle accepte une clé de hachage d’entier?

Quelle fonction de hachage d’entier est-elle bonne si elle accepte une clé de hachage d’entier?

La méthode multiplicative de Knuth:

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

En général, vous devriez choisir un multiplicateur qui est dans l’ordre de votre taille de hachage ( 2^32 dans l’exemple) et qui n’a aucun facteur commun. De cette façon, la fonction de hachage couvre tous vos espaces de hachage uniformément.

Edit: Le plus gros inconvénient de cette fonction de hachage est qu’elle préserve la divisibilité, donc si vos entiers sont tous divisibles par 2 ou par 4 (ce qui n’est pas rare), leurs hachages le seront aussi. Ceci est un problème dans les tables de hachage – vous pouvez vous retrouver avec seulement 1/2 ou 1/4 des compartiments utilisés.

J’ai trouvé que l’algorithme suivant fournit une très bonne dissortingbution statistique. Chaque bit d’entrée affecte chaque bit de sortie avec une probabilité d’environ 50%. Il n’y a pas de collision (chaque entrée produit une sortie différente). L’algorithme est rapide sauf si le processeur ne possède pas d’unité de multiplication entière intégrée. Le code C, en supposant que int est de 32 bits (pour Java, remplacez >> par >>> et supprimez 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 programme de test multithread spécial qui a fonctionné pendant plusieurs heures, qui calcule l’effet avalanche (le nombre de bits de sortie qui changent si un seul bit d’entrée est modifié, devrait être près de 16). le bit de sortie change (les bits de sortie ne doivent pas dépendre l’un de l’autre), et la probabilité d’un changement dans chaque bit de sortie si un bit d’entrée est modifié. Les valeurs calculées sont meilleures que le finaliseur 32 bits utilisé par MurmurHash , et presque aussi bon (pas tout à fait) que lorsque vous utilisez AES . Un léger avantage est que la même constante est utilisée deux fois (cela l’a rendu légèrement plus rapide la dernière fois que j’ai testé, je ne sais pas si c’est toujours le cas).

Vous pouvez inverser le processus (obtenir la valeur d’entrée du hachage) si vous remplacez le 0x45d9f3b par 0x119de1f3 (l’ inverse multiplicatif ):

 unsigned int unhash(unsigned int x) { x = ((x >> 16) ^ x) * 0x119de1f3; x = ((x >> 16) ^ x) * 0x119de1f3; x = (x >> 16) ^ x; return x; } 

Pour les nombres 64 bits, je suggère d’utiliser ce qui suit, même si cela n’est pas le plus rapide. Celui-ci est basé sur splitmix64 , qui semble être basé sur l’article du blog Better Bit Mixing (mix 13).

 uint64_t hash(uint64_t x) { x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9); x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb); x = x ^ (x >> 31); return x; } 

Pour Java, utilisez long , ajoutez L à la constante, remplacez >> par >>> et supprimez unsigned . Dans ce cas, l’inversion est plus compliquée:

 uint64_t unhash(uint64_t x) { x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3); x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089); x = x ^ (x >> 30) ^ (x >> 60); return x; } 

Mise à jour: Vous pouvez également consulter le projet Hash Function Prospector , où d’autres constantes (éventuellement meilleures) sont répertoriées.

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

 f(i) = i 

sera bon (je soupçonne optimal, mais je ne peux pas le prouver).

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

  • 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_SHIFT 
  • 32 bits et 64 bits (bonne dissortingbution) à: MurmurHash

  • Fonction de hachage d’entier

Il existe un bon aperçu de certains algorithmes de hachage chez Eternally Confuzzled . Je recommande le hachage unique de Bob Jenkins qui atteint rapidement les avalanches et peut donc être utilisé pour une recherche efficace dans les tables de hachage.

La réponse dépend de beaucoup de choses comme:

  • Où avez-vous l’intention de l’utiliser?
  • Qu’est-ce que tu essaies de faire avec le hash?
  • Avez-vous besoin d’une fonction de hachage cryptographiquement sécurisée?

Je vous suggère de regarder la famille de fonctions de hachage Merkle-Damgard comme SHA-1, etc.

Je ne pense pas que l’on puisse dire qu’une fonction de hachage est “bonne” sans connaître vos données à l’avance! et sans savoir ce que vous allez en faire.

Il existe de meilleures structures de données que les tables de hachage pour les tailles de données inconnues (je suppose que vous faites le hachage pour une table de hachage ici). J’utiliserais personnellement une table de hachage quand je sais que j’ai un nombre “fini” d’éléments qui doivent être stockés dans une quantité limitée de mémoire. J’essayerais de faire une parsing statistique rapide de mes données, de voir comment elles sont dissortingbuées, etc. avant de commencer à réfléchir à ma fonction de hachage.