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

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

En Java, la méthode hashCode() pour les objets String utilise ce qui suit formule :

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

où s[i] est le ième caractère, n est la longueur de la chaîne et ^ désigne une exponentiation. Cela soulève la question : pourquoi 31 est-il spécifiquement choisi comme multiplicateur ?

Justification d'un multiplicateur premier

La documentation suggère d'utiliser un nombre premier relativement grand comme multiplicateur pour minimiser les collisions dans les tables de hachage. Des collisions se produisent lorsque des objets distincts produisent le même code de hachage, ce qui peut entraîner des problèmes de performances. Les nombres premiers offrent une meilleure répartition des codes de hachage, réduisant ainsi le risque de collisions.

Pourquoi pas d'autres nombres premiers ?

La sélection de 31 parmi d'autres nombres premiers est attribuée à deux facteurs :

1. Prévention des débordements : Si le multiplicateur était pair et que la multiplication débordait, les informations seraient être perdu. En effet, multiplier par 2 équivaut à une opération de décalage.
2. Optimisation des performances : La valeur 31 permet une optimisation où la multiplication peut être remplacée par un décalage et une soustraction : 31 * i = = (je ≪≪ 5) - je. Les machines virtuelles modernes effectuent cette optimisation automatiquement.

Par conséquent, 31 satisfait aux deux critères d'être un nombre premier pour éviter les collisions tout en permettant des opérations de hachage efficaces pour les objets String en Java.

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!