Warum verwendet Javas „String.hashCode()' 31 als Multiplikator?

Warum Javas hashCode() in String 31 als Multiplikator verwendet

In Java verwendet die hashCode()-Methode für String-Objekte Folgendes Formel:

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

wobei s[i] das i-te Zeichen ist, n die Stringlänge ist und ^ bezeichnet Potenzierung. Dies wirft die Frage auf: Warum wird speziell 31 als Multiplikator gewählt?

Begründung für einen Primzahlmultiplikator

Die Dokumentation schlägt vor, eine relativ große Primzahl als Multiplikator zu verwenden Minimieren Sie Kollisionen in Hash-Tabellen. Kollisionen treten auf, wenn unterschiedliche Objekte denselben Hash-Code erzeugen, was möglicherweise zu Leistungsproblemen führt. Primzahlen bieten eine bessere Verteilung von Hash-Codes, wodurch die Wahrscheinlichkeit von Kollisionen verringert wird.

Warum nicht andere Primzahlen?

Die Auswahl von 31 unter anderen Primzahlen wird auf zwei zurückgeführt Faktoren:

1. Überlaufverhinderung: Wenn der Multiplikator gerade wäre und die Wenn die Multiplikation überläuft, gehen Informationen verloren. Dies liegt daran, dass die Multiplikation mit 2 einer Verschiebungsoperation entspricht.
2. Leistungsoptimierung: Der Wert 31 ermöglicht eine Optimierung, bei der die Multiplikation durch eine Verschiebung und Subtraktion ersetzt werden kann: 31 * i = = (i << 5) - i. Moderne virtuelle Maschinen führen diese Optimierung automatisch durch.

Daher erfüllt 31 beide Kriterien einer Primzahl, um Kollisionen zu verhindern und gleichzeitig effiziente Hashing-Operationen für String-Objekte in Java zu ermöglichen.

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!