Warum verwendet Javas String hashCode() 31 als Multiplikator?

Warum Javas hashCode() in String 31 als Multiplikator verwendet

In Java wird der Hash-Code für ein String-Objekt mithilfe von berechnet Formel:

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

wobei s[i] das i-te Zeichen der Zeichenfolge ist, n die Länge von die Zeichenfolge, und ^ gibt Potenzierung an.

Die Bedeutung eines Primzahlmultiplikators

Ein wichtiger Aspekt dieser Formel ist die Verwendung eines Primzahlmultiplikators, in diesem Fall 31. Die Verwendung einer Primzahl hat den Vorteil, dass die Wahrscheinlichkeit von Hash-Kollisionen verringert wird. Wenn ein Nicht-Primzahl-Multiplikator verwendet würde, könnten zwei Zeichenfolgen mit demselben Hash-Wert einen gemeinsamen Faktor haben, was das Auftreten von Hash-Kollisionen erleichtert.

Warum nicht eine andere Primzahl?

Während 31 eine ungerade Primzahl ist, könnten auch andere Primzahlen gewählt werden, wie zum Beispiel 29, 37 oder 97. Die Wahl von 31 basierte auf einer Kombination von Faktoren:

• Überlauf vermeiden: 31 ist eine relativ kleine Primzahl, die das Risiko eines ganzzahligen Überlaufs während des Multiplikationsprozesses verringert. Wenn eine gerade Primzahl verwendet würde, könnte es bei der Multiplikation mit 2 zu einem Überlauf kommen, wodurch möglicherweise Informationen verloren gehen.
• Leistungsoptimierung: Wie von Joshua Bloch in „Effective Java“ festgestellt, kann die Multiplikation mit 31 durch eine effizientere Verschiebungs- und Subtraktionsoperation ersetzt werden: 31 * i == (i << 5) - i. Diese Optimierung wird üblicherweise von modernen virtuellen Maschinen aus Leistungsgründen durchgeführt.
• Tradition: Die Verwendung eines Primzahlmultiplikators für Hash-Funktionen ist eine langjährige Praxis, und 31 ist eine besonders beliebte Wahl. Obwohl es keinen eindeutigen Grund dafür gibt, warum 31 speziell ausgewählt wurde, ist es in vielen Programmiersprachen und Anwendungen zur Standardauswahl geworden.

Das obige ist der detaillierte Inhalt vonWarum verwendet Javas String hashCode() 31 als Multiplikator?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!