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

Javas String-hashCode()-Rätsel: Warum der Multiplikator von 31?

Javas hashCode()-Methode für Strings ist ein grundlegender Aspekt von ihnen effizientes Speichern und Abrufen in Datenstrukturen. Durch die Kombination der Zeichen einer Zeichenfolge in einer bestimmten Formel entsteht eine Ganzzahl, die die eindeutige Identität der Zeichenfolge darstellt. Allerdings wirft die Wahl des Multiplikators 31 in dieser Formel Fragen auf.

Warum 31 als Multiplikator?

Die Java-Dokumentation gibt an, dass eine relativ große Primzahl sein sollte Wird als Multiplikator verwendet, um Hash-Kollisionen zu vermeiden und eine gleichmäßige Verteilung zu erreichen. Aber warum nicht 29, 37 oder 97 statt 31?

Grund 1: Ungerade Primzahl

Laut Joshua Blochs „Effective Java“ ist die Wahl von 31 rührt daher, dass es sich um eine ungerade Primzahl handelt. Die Verwendung einer geraden Zahl könnte zu Informationsverlust führen, wenn die Multiplikation überläuft, da die Multiplikation mit 2 einer Verschiebung entspricht.

Grund 2: Leistungsoptimierung

Eine interessante Eigenschaft von 31 ist, dass die Multiplikation damit effizient durch eine Verschiebung und eine Subtraktion ersetzt werden kann: 31 * i == (i << 5) - ich. Moderne virtuelle Maschinen führen diese Optimierung oft automatisch durch und verbessern so die Leistung der hashCode()-Berechnung.

Bedeutung der Primzahl

Obwohl weniger offensichtlich, ist die Verwendung einer Primzahl hat auch Vorteile. Primzahlen verteilen Werte gleichmäßiger und verringern so die Wahrscheinlichkeit von Hash-Kollisionen im Vergleich zu Nicht-Primzahl-Multiplikatoren. Dies verbessert die Fähigkeit, eindeutige Zeichenfolgen zu unterscheiden und eine konsistente Abrufleistung aufrechtzuerhalten.

Daher ist der Multiplikator von 31 in der String hashCode()-Methode von Java keine willkürliche Wahl, sondern ein Ergebnis ihrer Optimierung, Effizienz und Kollisionsvermeidung Eigenschaften, was ihn zu einem effektiven Wert zum Identifizieren und Verwalten von Zeichenfolgenobjekten macht.

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!