Pourquoi le String hashCode() de Java utilise-t-il 31 comme multiplicateur ?

Pourquoi le hashCode() de Java dans String utilise 31 comme multiplicateur

En Java, le code de hachage d'un objet String est calculé à l'aide du formule :

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

où s[i] est le ième caractère de la chaîne, n est la longueur du chaîne, et ^ indique l'exponentiation.

L'importance d'un multiplicateur premier

Un aspect clé de cette formule est l'utilisation d'un multiplicateur premier, dans ce cas, 31 L'utilisation d'un nombre premier présente l'avantage de réduire le risque de collisions de hachage. Si un multiplicateur non premier était utilisé, deux chaînes avec la même valeur de hachage pourraient partager un facteur commun, ce qui faciliterait les collisions de hachage.

Pourquoi pas un autre nombre premier ?

Bien que 31 soit un nombre premier impair, il existe d'autres nombres premiers qui auraient pu être choisis, comme 29, 37 ou 97. Le choix de 31 était basé sur une combinaison de facteurs :

• Éviter le débordement : 31 est un nombre premier relativement petit, ce qui réduit le risque de débordement d'entier pendant le processus de multiplication. Si un nombre premier pair était utilisé, un débordement pourrait se produire lors de la multiplication par 2, entraînant potentiellement une perte d'informations.
• Optimisation des performances : Comme l'a noté Joshua Bloch dans "Effective Java", la multiplication par 31 peut être remplacé par une opération de décalage et de soustraction plus efficace : 31 * i == (i << 5) - i. Cette optimisation est généralement effectuée par les machines virtuelles modernes à des fins de performances.
• Tradition : L'utilisation d'un multiplicateur premier pour les fonctions de hachage est une pratique de longue date, et 31 est un choix particulièrement populaire. Bien qu'il n'y ait aucune raison définitive pour laquelle 31 a été spécifiquement sélectionné, il est devenu un choix standard dans de nombreux langages et applications de programmation.

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!