Gemäß der Java-Dokumentation wird der Hash-Code für ein String
Objekt wie folgt berechnet:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
Verwenden der
int
Arithmetik, wobeis[i]
das i- te Zeichen der Zeichenfolgen
die Länge der Zeichenfolge ist und^
die Exponentiation angibt.
Warum wird 31 als Multiplikator verwendet?
Ich verstehe, dass der Multiplikator eine relativ große Primzahl sein sollte. Warum also nicht 29 oder 37 oder sogar 97?
Antworten:
Laut Joshua Blochs Effective Java (ein Buch, das nicht genug zu empfehlen ist und das ich dank ständiger Erwähnungen zum Stackoverflow gekauft habe):
(ab Kapitel 3, Punkt 9: Hashcode immer überschreiben, wenn Sie gleich überschreiben, Seite 48)
quelle
Wie Goodrich und Tamassia hervorheben , führt die Verwendung der Konstanten 31, 33, 37, 39 und 41 zu weniger als 7 Kollisionen, wenn Sie mehr als 50.000 englische Wörter (gebildet als Vereinigung der in zwei Unix-Varianten bereitgestellten Wortlisten) verwenden in jedem Fall. In diesem Wissen sollte es nicht überraschen, dass viele Java-Implementierungen eine dieser Konstanten wählen.
Zufälligerweise war ich gerade dabei, den Abschnitt "Polynom-Hash-Codes" zu lesen, als ich diese Frage sah.
BEARBEITEN: Hier ist ein Link zu dem ~ 10 MB PDF-Buch, auf das ich mich oben beziehe. Siehe Abschnitt 10.2 Hash-Tabellen (Seite 413) von Datenstrukturen und Algorithmen in Java
quelle
Auf (meistens) alten Prozessoren kann das Multiplizieren mit 31 relativ billig sein. Auf einem ARM ist es beispielsweise nur eine Anweisung:
Die meisten anderen Prozessoren würden eine separate Verschiebungs- und Subtraktionsanweisung erfordern. Wenn Ihr Multiplikator jedoch langsam ist, ist dies immer noch ein Gewinn. Moderne Prozessoren tendieren dazu, schnelle Multiplikatoren zu haben, so dass es keinen großen Unterschied macht, solange 32 auf der richtigen Seite steht.
Es ist kein großartiger Hash-Algorithmus, aber es ist gut genug und besser als der 1.0-Code (und sehr viel besser als die 1.0-Spezifikation!).
quelle
String.hashCode
ist älter als der StrongARM, der, IIRC, einen 8-Bit-Multiplikator eingeführt und möglicherweise auf zwei Zyklen für die kombinierte arithmetische / logische mit Verschiebungsoperationen erhöht hat.Map.Entry
ist durch die Spezifikation festgelegt worden zu sein ,key.hashCode() ^ value.hashCode()
obwohl es ist nicht einmal ein ungeordnetes Paar, wiekey
undvalue
ganz andere Bedeutung hat. Ja, das bedeutet, dassMap.of(42, 42).hashCode()
oderMap.of("foo", "foo", "bar", "bar").hashCode()
usw. vorhersehbar Null sind. Verwenden Sie also keine Karten als Schlüssel für andere Karten…Durch Multiplizieren werden Bits nach links verschoben. Dadurch wird mehr Speicherplatz für Hash-Codes genutzt, wodurch Kollisionen reduziert werden.
Wenn keine Zweierpotenz verwendet wird, werden auch die Bits niedrigerer Ordnung ganz rechts gefüllt, um mit den nächsten Daten gemischt zu werden, die in den Hash eingehen.
Der Ausdruck
n * 31
ist äquivalent zu(n << 5) - n
.quelle
Sie können Blochs ursprüngliche Argumentation unter "Kommentare" unter http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 lesen . Er untersuchte die Leistung verschiedener Hash-Funktionen in Bezug auf die resultierende "durchschnittliche Kettengröße" in einer Hash-Tabelle.
P(31)
war eine der häufigsten Funktionen in dieser Zeit, die er in K & Rs Buch fand (aber selbst Kernighan und Ritchie konnten sich nicht erinnern, woher es kam). Am Ende musste er sich im Grunde genommen für einen entscheiden und so nahm er,P(31)
da es gut genug zu funktionieren schien. ObwohlP(33)
es nicht wirklich schlimmer war und die Multiplikation mit 33 gleich schnell zu berechnen ist (nur eine Verschiebung um 5 und eine Addition), entschied er sich für 31, da 33 keine Primzahl ist:Die Argumentation war also nicht so rational, wie viele der Antworten hier zu implizieren scheinen. Aber wir sind alle gut darin, nach Darmentscheidungen rationale Gründe zu finden (und sogar Bloch könnte dazu neigen).
quelle
Eigentlich würde 37 ziemlich gut funktionieren! z: = 37 * x kann berechnet werden als
y := x + 8 * x; z := x + 4 * y
. Beide Schritte entsprechen einer LEA x86-Anweisung, daher ist dies extrem schnell.Tatsächlich könnte die Multiplikation mit der noch größeren Primzahl 73 durch Einstellen mit der gleichen Geschwindigkeit erfolgen
y := x + 8 * x; z := x + 8 * y
.Die Verwendung von 73 oder 37 (anstelle von 31) ist möglicherweise besser, da dies zu einem dichteren Code führt : Die beiden LEA-Befehle benötigen nur 6 Byte gegenüber den 7 Byte für Verschieben + Verschieben + Subtrahieren für die Multiplikation mit 31. Eine mögliche Einschränkung ist die folgende Die hier verwendeten LEA-Anweisungen mit drei Argumenten wurden in der Sandy-Bridge-Architektur von Intel langsamer, mit einer erhöhten Latenz von 3 Zyklen.
Darüber hinaus ist 73 Sheldon Coopers Lieblingsnummer.
quelle
Neil Coffey erklärt, warum 31 unter Ausbügeln der Vorspannung verwendet wird .
Grundsätzlich ergibt die Verwendung von 31 eine gleichmäßigere Set-Bit-Wahrscheinlichkeitsverteilung für die Hash-Funktion.
quelle
Aus JDK-4045622 , wo Joshua Bloch die Gründe beschreibt, warum diese bestimmte (neue)
String.hashCode()
Implementierung ausgewählt wurdequelle
Bloch geht nicht ganz darauf ein, aber das Grundprinzip, das ich immer gehört / geglaubt habe, ist, dass dies eine grundlegende Algebra ist. Hashes laufen auf Multiplikations- und Moduloperationen hinaus, was bedeutet, dass Sie niemals Zahlen mit gemeinsamen Faktoren verwenden möchten, wenn Sie helfen können. Mit anderen Worten, relativ Primzahlen sorgen für eine gleichmäßige Verteilung der Antworten.
Die Zahlen, aus denen ein Hash besteht, sind normalerweise:
Sie können wirklich nur ein paar dieser Werte kontrollieren, daher ist ein wenig zusätzliche Sorgfalt geboten.
quelle
In der neuesten Version von JDK wird 31 weiterhin verwendet. https://docs.oracle.com/de/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode ()
Der Zweck der Hash-Zeichenfolge ist
^
im Hashcode-Berechnungsdokument, es hilft eindeutig)31 ist der maximale Wert, der in ein 8-Bit-Register (= 1 Byte) eingegeben werden kann, die größte Primzahl, die in ein 1-Byte-Register eingegeben werden kann, ist eine ungerade Zahl.
Multiplizieren Sie 31 ist << 5 und subtrahieren Sie sich dann selbst. Benötigen Sie daher billige Ressourcen.
quelle
Ich bin mir nicht sicher, aber ich würde vermuten, dass sie eine Stichprobe von Primzahlen getestet haben und festgestellt haben, dass 31 die beste Verteilung über eine Stichprobe möglicher Strings ergab.
quelle
Dies liegt daran, dass 31 eine nette Eigenschaft hat - seine Multiplikation kann durch eine bitweise Verschiebung ersetzt werden, die schneller als die Standardmultiplikation ist:
quelle