Pourquoi « String.hashCode() » de Java utilise-t-il 31 comme multiplicateur ?

Mystère String hashCode() de Java : pourquoi le multiplicateur de 31 ?

La méthode hashCode() de Java pour les chaînes est un aspect fondamental de leur stockage et récupération efficaces dans les structures de données. En combinant les caractères d'une chaîne dans une formule spécifique, il produit un entier qui représente l'identité unique de la chaîne. Cependant, le choix du multiplicateur 31 dans cette formule suscite des questions.

Pourquoi 31 comme multiplicateur ?

La documentation Java indique qu'un nombre premier relativement grand devrait être utilisé comme multiplicateur pour éviter les collisions de hachage et obtenir une distribution uniforme. Cependant, pourquoi pas 29, 37 ou 97 au lieu de 31 ?

Raison 1 : Odd Prime

Selon "Effective Java" de Joshua Bloch, le choix de 31 vient du fait qu’il s’agit d’un nombre premier impair. L'utilisation d'un nombre pair pourrait entraîner une perte d'informations si la multiplication débordait, car multiplier par 2 équivaut à un décalage.

Raison 2 : Optimisation des performances

Une propriété intéressante de 31 est-ce que la multiplication par celui-ci peut être efficacement remplacée par un décalage et une soustraction : 31 * i == (i << 5) - i. Les machines virtuelles modernes effectuent souvent cette optimisation automatiquement, améliorant ainsi les performances du calcul hashCode().

Importance de la primauté

Bien que moins évidente, l'utilisation d'un nombre premier présente également des avantages. Les nombres premiers répartissent les valeurs plus uniformément, réduisant ainsi le risque de collisions de hachage par rapport aux multiplicateurs non premiers. Cela améliore la capacité de distinguer des chaînes uniques et de maintenir des performances de récupération cohérentes.

Par conséquent, le multiplicateur de 31 dans la méthode String hashCode() de Java n'est pas un choix arbitraire mais le résultat de son optimisation, de son efficacité et de son évitement des collisions. propriétés, ce qui en fait une valeur efficace pour identifier et gérer les objets chaîne.

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!