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

Exploration du raisonnement derrière le multiplicateur 31 de Java pour le hashCode() de String

L'implémentation de String de Java utilise une formule spécifique pour calculer le code de hachage :

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

où s[i] désigne le i-ème caractère de la chaîne, n représente sa longueur et ^ signifie exponentiation. Cependant, une question pertinente se pose : pourquoi le multiplicateur est-il fixé à 31 ?

Ce choix découle des principes énoncés dans le célèbre livre de Joshua Bloch, "Effective Java, Second Edition". Le raisonnement de Bloch s'articule autour de deux critères clés pour le multiplicateur : il doit s'agir d'un nombre premier relativement grand.

Les avantages d'un multiplicateur premier impair

Bloch souligne que l'utilisation d'un un multiplicateur premier impair comme 31 garantit que l'opération de multiplication n'entraînera pas de perte d'informations due à un débordement. Si le multiplicateur était pair, un débordement pourrait se produire, et comme la multiplication par 2 est analogue à un décalage, des informations cruciales pourraient être compromises.

Les avantages plus subtils d'un multiplicateur principal

Bien que les avantages spécifiques de la sélection d'un multiplicateur premier soient moins évidents, cela correspond aux pratiques habituelles. Notamment, 31 possède un attribut unique : il permet de remplacer efficacement la multiplication par un décalage et une soustraction, conduisant à des performances améliorées. Cette optimisation est souvent exécutée automatiquement par les machines virtuelles (VM) modernes.

Le consensus

En résumé, l'utilisation par Java de 31 comme multiplicateur pour la méthode hashCode() de String découle de son statut de nombre premier impair. Ce choix protège contre la perte d'informations due au débordement et permet d'améliorer les performances grâce au remplacement de la multiplication par le décalage et la soustraction.

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!