Warum verwendet Javas hashCode () in String 31 als Multiplikator?

480

Gemäß der Java-Dokumentation wird der Hash-Code für ein StringObjekt wie folgt berechnet:

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

Verwenden der intArithmetik, wobei s[i]das i- te Zeichen der Zeichenfolge ndie 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?

Jacobko
quelle
1
Vergleichen Sie auch stackoverflow.com/questions/1835976/… - Ich denke, 31 ist eine schlechte Wahl, wenn Sie Ihre eigenen hashCode-Funktionen schreiben.
Hans-Peter Störr
6
Wenn es 29 oder 37 oder sogar 97 wäre, würden Sie fragen, warum nicht 31?
Marquis von Lorne
2
@EJP Es ist wichtig, den Grund für die Wahl einer Nr. Zu kennen. es sei denn, die Zahl ist das Ergebnis eines schwarzen Zaubertricks.
Dushyant Sabharwal
Es gibt einen Blog-Beitrag von @ peter-lawrey darüber hier: vanilla-java.github.io/2018/08/12/… und hier: vanilla-java.github.io/2018/08/15/…
Christophe Roussy
@DushyantSabharwal Mein Punkt ist , dass es hätte gewesen 29 oder 37 oder 97 oder 41 oder viele andere Werte, ohne viel praktische Unterschied zu machen. Wir haben 1976 37 verwendet.
Marquis von Lorne

Antworten:

405

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):

Der Wert 31 wurde gewählt, weil es sich um eine ungerade Primzahl handelt. Wenn es gerade wäre und die Multiplikation überläuft, würden Informationen verloren gehen, da die Multiplikation mit 2 einer Verschiebung entspricht. Der Vorteil der Verwendung einer Primzahl ist weniger klar, aber traditionell. Eine schöne Eigenschaft von 31 ist, dass die Multiplikation für eine bessere Leistung durch eine Verschiebung und eine Subtraktion ersetzt werden kann : 31 * i == (i << 5) - i. Moderne VMs führen diese Art der Optimierung automatisch durch.

(ab Kapitel 3, Punkt 9: Hashcode immer überschreiben, wenn Sie gleich überschreiben, Seite 48)

matt b
quelle
346
Nun, alle Primzahlen sind seltsam, außer 2. Sag es einfach.
Kip
38
Ich glaube nicht, dass Bloch sagt, dass es gewählt wurde, weil es eine ungerade Primzahl war, sondern weil es ungerade war UND weil es eine Primzahl war (UND weil es leicht in eine Verschiebung / Subtraktion optimiert werden kann).
Matt B
50
31 wurde gewählt, weil es eine ungerade Primzahl ist ??? Das macht keinen Sinn - ich sage, 31 wurde ausgewählt, weil es die beste Verteilung ergab - überprüfen Sie Computinglife.wordpress.com/2008/11/20/…
Computinglife
65
Ich denke, die Wahl von 31 ist ziemlich unglücklich. Sicher, es kann einige CPU-Zyklen auf alten Computern einsparen, aber Sie haben bereits Hash-Kollisionen mit kurzen ASCII-Zeichenfolgen wie "@ und #!" Oder "Ca" und "DB". Dies geschieht nicht, wenn Sie beispielsweise 1327144003 oder at auswählen mindestens 524287, was auch eine Bitverschiebung erlaubt: 524287 * i == i << 19 - i.
Hans-Peter Störr
15
@ Jason Siehe meine Antwort stackoverflow.com/questions/1835976/… . Mein Punkt ist: Sie erhalten viel weniger Kollisionen, wenn Sie eine größere Primzahl verwenden, und verlieren heutzutage nichts. Das Problem ist schlimmer, wenn Sie nicht-englische Sprachen mit gebräuchlichen Nicht-ASCII-Zeichen verwenden. Und 31 war für viele Programmierer ein schlechtes Beispiel, wenn sie ihre eigenen HashCode-Funktionen schrieben.
Hans-Peter Störr
80

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

JohnZaj
quelle
6
Beachten Sie jedoch, dass Sie möglicherweise viel mehr Kollisionen erhalten, wenn Sie einen internationalen Zeichensatz mit gemeinsamen Zeichen außerhalb des ASCII-Bereichs verwenden. Zumindest habe ich das für 31 und Deutsch überprüft. Ich denke also, die Wahl von 31 ist gebrochen.
Hans-Peter Störr
1
@jJack, Der in Ihrer Antwort angegebene Link ist defekt.
SK Venkat
Beide Links in dieser Antwort sind fehlerhaft. Auch das Argument im ersten Absatz ist etwas unvollständig; Wie vergleichen sich andere ungerade Zahlen mit den fünf, die Sie in dieser Benchmark auflisten?
Mark Amery
58

Auf (meistens) alten Prozessoren kann das Multiplizieren mit 31 relativ billig sein. Auf einem ARM ist es beispielsweise nur eine Anweisung:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

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!).

Tom Hawtin - Tackline
quelle
7
Komischerweise ist die Multiplikation mit 31 auf meinem Desktop-Computer tatsächlich etwas langsamer als die Multiplikation mit beispielsweise 92821. Ich denke, der Compiler versucht, sie in Shift zu "optimieren" und auch hinzuzufügen. :-)
Hans-Peter Störr
1
Ich glaube nicht, dass ich jemals einen ARM verwendet habe, der nicht mit allen Werten im Bereich +/- 255 gleich schnell war. Die Verwendung einer Potenz von 2 minus eins hat den unglücklichen Effekt, dass eine übereinstimmende Änderung auf zwei Werte den Hash-Code um eine Potenz von zwei ändert. Ein Wert von -31 wäre besser gewesen, und ich würde denken, dass etwas wie -83 (64 + 16 + 2 + 1) noch besser gewesen wäre (Bits etwas besser mischen).
Supercat
@supercat Nicht vom Minus überzeugt. Scheint, als würden Sie zurück zu Nullen gehen. / String.hashCodeist ä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.
Tom Hawtin - Tackline
1
@ TomHawtin-Tackline: Bei Verwendung von 31 wäre der Hash von vier Werten 29791 * a + 961 * b + 31 * c + d; unter Verwendung von -31 wäre es -29791 * a + 961 * b - 31 * c + d. Ich denke nicht, dass der Unterschied signifikant wäre, wenn die vier Elemente unabhängig sind, aber wenn Paare benachbarter Elemente übereinstimmen, ist der resultierende Hash-Code der Beitrag aller ungepaarten Elemente plus ein Vielfaches von 32 (von den gepaarten). Für Zeichenfolgen ist es vielleicht nicht so wichtig, aber wenn man eine Allzweckmethode für Hashing-Aggregationen schreibt, ist die Situation, in der benachbarte Elemente übereinstimmen, unverhältnismäßig häufig.
Supercat
3
@supercat Spaß Tatsache, der Hash - Code Map.Entryist durch die Spezifikation festgelegt worden zu sein , key.hashCode() ^ value.hashCode()obwohl es ist nicht einmal ein ungeordnetes Paar, wie keyund valueganz andere Bedeutung hat. Ja, das bedeutet, dass Map.of(42, 42).hashCode()oder Map.of("foo", "foo", "bar", "bar").hashCode()usw. vorhersehbar Null sind. Verwenden Sie also keine Karten als Schlüssel für andere Karten…
Holger
33

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 * 31ist äquivalent zu (n << 5) - n.

erickson
quelle
29

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. Obwohl P(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:

Von den verbleibenden vier würde ich wahrscheinlich P (31) auswählen, da dies auf einer RISC-Maschine am billigsten zu berechnen ist (da 31 die Differenz zweier Zweierpotenzen ist). P (33) ist ähnlich billig zu berechnen, aber seine Leistung ist geringfügig schlechter, und 33 ist zusammengesetzt, was mich etwas nervös macht.

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).

David Ongaro
quelle
2
Eine gründliche Recherche und unvoreingenommene Antwort!
Vishal K
22

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.

hrr
quelle
5
Bist du ein Pascal-Programmierer oder so? Was ist mit dem: = Zeug?
Mainguy
11
@ Mainguy Es ist eigentlich ALGOL-Syntax und wird ziemlich oft im Pseudocode verwendet.
Annäherung an
4
Aber in der ARM-Assembly kann die Multiplikation mit 31 in einer einzigen Anweisung erfolgen
phuclv
In TPOP (1999) kann man über frühes Java lesen (S.57): "... Das Problem wurde gelöst, indem der Hash durch ein Äquivalent zu dem von uns gezeigten ersetzt wurde (mit einem Multiplikator von 37 ) ..."
Miku
19

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.

Der Saft
quelle
12

Aus JDK-4045622 , wo Joshua Bloch die Gründe beschreibt, warum diese bestimmte (neue) String.hashCode()Implementierung ausgewählt wurde

Die folgende Tabelle fasst die Leistung der verschiedenen oben beschriebenen Hash-Funktionen für drei Datensätze zusammen:

1) Alle Wörter und Phrasen mit Einträgen in Merriam-Websters 2nd Int'l Unabridged Dictionary (311.141 Zeichenfolgen, durchschnittliche Länge 10 Zeichen).

2) Alle Zeichenfolgen in / bin / , / usr / bin / , / usr / lib / , / usr / ucb / und / usr / openwin / bin / * (66.304 Zeichenfolgen, durchschnittliche Länge 21 Zeichen).

3) Eine Liste von URLs, die von einem Webcrawler gesammelt wurden, der letzte Nacht mehrere Stunden lang ausgeführt wurde (28.372 Zeichenfolgen, durchschnittliche Länge 49 Zeichen).

Die in der Tabelle angezeigte Leistungsmetrik ist die "durchschnittliche Kettengröße" über alle Elemente in der Hash-Tabelle (dh der erwartete Wert der Anzahl der Schlüssel wird verglichen, um ein Element nachzuschlagen).

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439

Wenn man sich diese Tabelle ansieht, ist klar, dass alle Funktionen außer der aktuellen Java-Funktion und den beiden defekten Versionen der Weinberger-Funktion eine hervorragende, nahezu ununterscheidbare Leistung bieten. Ich vermute stark, dass diese Leistung im Wesentlichen das "theoretische Ideal" ist, was Sie erhalten würden, wenn Sie einen echten Zufallszahlengenerator anstelle einer Hash-Funktion verwenden würden.

Ich würde die WAIS-Funktion ausschließen, da ihre Spezifikation Seiten mit Zufallszahlen enthält und ihre Leistung nicht besser ist als die der weitaus einfacheren Funktionen. Jede der verbleibenden sechs Funktionen scheint eine ausgezeichnete Wahl zu sein, aber wir müssen eine auswählen. Ich nehme an, ich würde Vos Variante und Weinbergers Funktion wegen ihrer zusätzlichen Komplexität ausschließen, wenn auch geringfügig. Von den verbleibenden vier würde ich wahrscheinlich P (31) auswählen, da dies auf einer RISC-Maschine am billigsten zu berechnen ist (da 31 die Differenz zweier Zweierpotenzen ist). P (33) ist ähnlich billig zu berechnen, aber seine Leistung ist geringfügig schlechter, und 33 ist zusammengesetzt, was mich etwas nervös macht.

Josh

Fließen
quelle
5

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:

  • Modul des Datentyps, in den Sie ihn eingefügt haben (2 ^ 32 oder 2 ^ 64)
  • Modul der Bucket-Anzahl in Ihrer Hashtabelle (variiert. In Java war früher Primzahl, jetzt 2 ^ n)
  • Multiplizieren oder verschieben Sie Ihre Mischfunktion mit einer magischen Zahl
  • Der Eingabewert

Sie können wirklich nur ein paar dieser Werte kontrollieren, daher ist ein wenig zusätzliche Sorgfalt geboten.

Jason
quelle
4

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

  • unique (Siehe Operator ^im Hashcode-Berechnungsdokument, es hilft eindeutig)
  • günstige Kosten für die Berechnung

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.

Mach Nhu Vy
quelle
3

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.

Dave L.
quelle
1

Dies liegt daran, dass 31 eine nette Eigenschaft hat - seine Multiplikation kann durch eine bitweise Verschiebung ersetzt werden, die schneller als die Standardmultiplikation ist:

31 * i == (i << 5) - i
yoAlex5
quelle