Pourquoi le « hashCode() » de Java pour les chaînes utilise-t-il 31 comme multiplicateur ?

Pourquoi 31 est-il utilisé comme multiplicateur dans la méthode hashCode() de Java pour les chaînes ?

La documentation Java spécifie le calcul de la valeur d'un objet String. code de hachage comme suit :

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 de la chaîne et ^ représente l'exponentiation. Cette formule intègre un multiplicateur fixe de 31.

Raison d'être de l'utilisation de 31 comme multiplicateur

Selon l'ouvrage estimé de Joshua Bloch, "Effective Java", le choix de 31 car le multiplicateur repose sur plusieurs facteurs :

• Odd Premier : Étant un nombre premier impair, 31 garantit que si la multiplication entraîne un débordement, l'information n'est pas perdue (contrairement à l'utilisation d'un multiplicateur pair, ce qui équivaut à un décalage).
• Tradition : Il est habituel d'utiliser un nombre premier comme multiplicateur.
• Optimisation des performances : 31 possède une propriété unique qui permet des performances améliorations : 31 * je peux être remplacé efficacement par (i << 5) - i. Cette optimisation est couramment appliquée par les machines virtuelles modernes.

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!