Fonctions de hachage et codes de hachage

Une fonction de hachage typique convertit d'abord une clé de recherche en une valeur entière appelée code de hachage, puis compresse le code de hachage en un index de la table de hachage. La classe racine de Java Object possède la méthode hashCode, qui renvoie un code de hachage entier. Par défaut, la méthode renvoie l'adresse mémoire de l'objet. Le contrat général de la méthode hashCode est le suivant :

1. Vous devez remplacer la méthode hashCode chaque fois que la méthode equals est remplacée pour garantir que deux objets égaux renvoient le même code de hachage.
2. Lors de l'exécution d'un programme, invoquer plusieurs fois la méthode hashCode renvoie le même entier, à condition que les données de l'objet ne soient pas modifiées.
3. Deux objets inégaux peuvent avoir le même code de hachage, mais vous devez implémenter la méthode hashCode pour éviter trop de cas de ce type.

Codes de hachage pour les types primitifs

Pour les clés de recherche de type byte, short, int et char, convertissez-les simplement en int . Par conséquent, deux clés de recherche différentes de l’un de ces types auront des codes de hachage différents.

Pour une clé de recherche du type float, utilisez Float.floatToIntBits(key) comme code de hachage. Notez que floatToIntBits(float f) renvoie une valeur int dont la représentation binaire est la même que la représentation binaire du nombre flottant f. Ainsi, deux clés de recherche différentes de type float auront des codes de hachage différents.

Pour une clé de recherche du type long, la simplement convertir en int ne serait pas un bon choix, car toutes les clés qui diffèrent uniquement par les 32 premiers bits auront le même code de hachage. Pour prendre en compte les 32 premiers bits, divisez les 64 bits en deux moitiés et effectuez l'opération ou exclusif pour combiner les deux moitiés. Ce processus est appelé pliage. Le code de hachage d'une clé longue est

int hashCode = (int)(clé ^ (clé >> 32));

Notez que >> est l'opérateur de décalage vers la droite qui décale les bits de 32 positions vers la droite. Par exemple, 1010110 >> 2 donne 0010101. Le ^ est l'opérateur ou exclusif au niveau du bit. Il opère sur deux bits correspondants des opérandes binaires. Par exemple, 1010110 ^ 0110111 donne 1100001.

Pour une clé de recherche de type double, convertissez-la d'abord en une valeur long à l'aide de la méthode Double.doubleToLongBits, puis effectuez un pliage comme suit :

bits longs = Double.doubleToLongBits(key);
int hashCode = (int)(bits ^ (bits >> 32));

Codes de hachage pour les chaînes

Les clés de recherche sont souvent des chaînes, il est donc important de concevoir une bonne fonction de hachage pour les chaînes. Une approche intuitive consiste à additionner l'Unicode de tous les caractères comme code de hachage de la chaîne. Cette approche peut fonctionner si deux clés de recherche dans une application ne contiennent pas les mêmes lettres, mais elle produira de nombreuses collisions si les clés de recherche contiennent les mêmes lettres, telles que tod et dot .

Une meilleure approche consiste à générer un code de hachage qui prend en compte la position des caractères. Plus précisément, laissez le code de hachage être

s0*b(n - 1) + s1*b(n - 2) + c + sn-1

où si est s.charAt(i). Cette expression est un polynôme pour un b positif, c'est pourquoi on l'appelle un code de hachage polynomial. En utilisant la règle de Horner pour l'évaluation polynomiale (voir Étude de cas : Conversion d'hexadécimaux en décimales), le code de hachage peut être calculé efficacement comme suit :

(...((s0*b + s1)b + s2)b + ... + sn-2)b + sn-1

Ce calcul peut provoquer un débordement pour les chaînes longues, mais le débordement arithmétique est ignoré en Java. Vous devez choisir une valeur b appropriée pour minimiser les collisions. Les expériences montrent que les bons choix pour b sont 31, 33, 37, 39 et 41. Dans la classe String, le hashCode est remplacé à l'aide du code de hachage polynomial, b étant 31.

Compression des codes de hachage

Le code de hachage d'une clé peut être un grand entier hors de la plage de l'index de la table de hachage, vous devez donc le réduire pour l'adapter à la plage de l'index. Supposons que l'index d'une table de hachage soit compris entre 0 et N-1. La façon la plus courante de mettre à l'échelle un entier entre 0 et N-1 est d'utiliser

h(hashCode) = hashCode % N

Pour vous assurer que les indices sont répartis uniformément, choisissez N pour être un nombre premier supérieur à 2.

Idéalement, vous devriez choisir un nombre premier pour N. Cependant, trouver un grand nombre premier prend beaucoup de temps. Dans l'implémentation de l'API Java pour java.util.HashMap, N est défini sur une valeur de la puissance de 2. Il y a une bonne raison à ce choix. Lorsque N est une valeur de la puissance de 2,

h(hashCode) = hashCode % N

est la même chose que

h(hashCode) = hashCode & (N – 1)

L'esperluette, &, est un opérateur ET au niveau du bit. Le ET de deux bits correspondants donne un 1 si les deux bits sont 1. Par exemple, supposons N = 4 et hashCode = 11, 11 % 4 = 3, ce qui équivaut à 01011 & 00011 = 11. L'opérateur & peut être exécuté beaucoup plus rapidement que l'opérateur %.

Pour garantir que le hachage est uniformément réparti, une fonction de hachage supplémentaire est également utilisée avec la fonction de hachage principale dans l'implémentation de java.util.HashMap. Cette fonction est définie comme :

private static int supplémentHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
retourner h ^ (h >>> 7) ^ (h >>> 4);
>

^ et >>> sont des opérations de décalage à droite exclusives au niveau du bit et non signées. Les opérations au niveau du bit sont beaucoup plus rapides que les opérations de multiplication, de division et de reste. Vous devez remplacer ces opérations par les opérations au niveau du bit autant que possible.

La fonction de hachage complète est définie comme :

h(hashCode) = supplémentalHash(hashCode) % N

C'est la même chose que

h(hashCode) = supplémentalHash(hashCode) & (N – 1)

puisque N est une valeur de la puissance de 2.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!