Warum Java hashCode () in String verwenden 31 als Multiplikator?

StackOverflow https://stackoverflow.com/questions/299304

  •  08-07-2019
  •  | 
  •  

Frage

Per Java-Dokumentation, die Hashcode für eine String Aufgabe wird berechnet als: 

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

mit int Arithmetik, wo s[i] das ist     i te Zeichen der Zeichenkette, n ist die Länge    die Zeichenfolge, und ^ zeigen Potenzierung.

Warum 31 als Multiplikator verwendet?

Ich verstehe, dass der Multiplikator ein relativ großer Primzahl sein sollte. Warum also nicht 29 oder 37, oder sogar 97?

War es hilfreich?

Lösung

Nach Joshua Bloch Effective Java (ein Buch, das nicht sein kann genug, um zu empfehlen, und die ich gekauft durch ständige auf Stackoverflow Nennungen):

  

Der Wert 31 wurde gewählt, weil es eine ungerade Primzahl ist. Wenn es selbst und die Multiplikation übergelaufen ist, würden Informationen verloren, da die Multiplikation mit 2 äquivalent zu verschieben. Der Vorteil einer Primzahl mit weniger klar, aber es ist traditionell. Eine nette Eigenschaft von 31 ist, dass die Multiplikation durch eine Verschiebung und eine Subtraktion für eine bessere Leistung ersetzt werden kann: 31 * i == (i << 5) - i. Moderner VMs tun, um diese Art von Optimierung automatisch.

(aus Kapitel 3, Punkt 9: Immer außer Kraft setzen hashcode wenn Sie überschreiben equals, Seite 48)

Andere Tipps

Wie und Goodrich Tamassia weisen darauf hin, wenn Sie nehmen mehr als 50.000 englische Wörter (als Vereinigung gebildet die Wortlisten in zwei Varianten von Unix) vorgesehen ist, unter Verwendung der Konstanten 31, 33, 37, 39, und 41 produzieren weniger als 7 Kollisionen in jedem Fall. Wenn man das weiß, sollte es nicht überraschen, dass viele Java-Implementierungen eine dieser Konstanten wählen.

Zufälligerweise war ich in der Mitte des Abschnitts „Polynom Hash-Codes“ zu lesen, wenn ich diese Frage sah.

EDIT: Hier ist Link zu dem ~ 10 MB PDF Buch, das ich über mich beziehen. Siehe Abschnitt 10.2 Hash Tables (Seite 413) von Datenstrukturen und Algorithmen in Java

Ein (meist) alte Prozessoren, um 31 multiplizieren können relativ billig sein. Auf einer ARM, zum Beispiel, es ist nur eine Anweisung: 

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

Die meisten anderen Prozessoren würde eine separate Verschiebung erfordern und Anweisung subtrahieren. Allerdings, wenn Ihr Multiplikator langsam ist dies immer noch ein Gewinn. Moderne Prozessoren sind in der Regel schnell Multiplikatoren haben, so dass es nicht viel Unterschied machen, so lange wie 32 auf der richtigen Seite geht.

Es ist kein großer Hash-Algorithmus, aber es ist gut genug, und besser als der 1,0-Code (und sehr viel besser als die 1.0-Spezifikation!).

Durch Multiplikation werden Bits nach links verschoben. Dies wird mehr von dem verfügbaren Platz von Hash-Codes, Kollisionen zu reduzieren.

Durch die nicht eine Zweierpotenz verwendet wird, desto niedriger Ordnung werden am weitesten rechts liegenden Bits als auch besiedelt, mit dem nächsten Teil der Daten gemischt werden gehen in die hash.

Der Ausdruck n * 31 entspricht (n << 5) - n.

Sie können Blochs ursprünglichen Argumentation unter "Kommentare" in http: // bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 . Er untersuchte die Leistung verschiedener Hash-Funktionen in Bezug auf die daraus resultierende „durchschnittliche Kettengröße“ in einer Hash-Tabelle. P(31) war eine der häufigsten Funktionen, die während dieser Zeit, die er in K & R Buch gefunden (aber auch Kernighan und Ritchie konnte sich nicht erinnern, woher es kam). Am Ende hatte er im Grunde ein zu wählen, und so nahm er P(31), da es gut genug, um durchzuführen schien. Obwohl P(33) war nicht wirklich schlechter und Multiplikation mit 33 ist ebenso schnell zu (nur eine Verschiebung um 5 und eine Addition) zu berechnen, er entschied sich für 31 seit 33 keine Primzahl ist:

  

Von den verbleibenden   vier, würde ich wahrscheinlich wählen P (31), wie es die billigste ist auf einem RISC zu berechnen   Maschine (31, weil die Differenz zweier Potenzen von beiden ist). P (33)   ähnlich billig zu berechnen, aber es ist Leistung ist geringfügig schlechter, und   33 ist zusammengesetzt, das macht mich ein bisschen nervös.

So die Argumentation nicht so rational, wie viele der Antworten war hier scheinen zu implizieren. Aber wir sind alle gut in der kommenden mit rationalen Gründen nach Bauchentscheidungen (und sogar Bloch könnte, dass anfällig sein).

Eigentlich, 37 wäre ziemlich gut funktionieren! z: = 37 * x kann als y := x + 8 * x; z := x + 4 * y berechnet werden. Beide Schritte entsprechen einer LEA x86-Befehle, so ist dies extrem schnell.

In der Tat, Multiplikation mit der geraden größerer Primzahl 73 könnte durch y := x + 8 * x; z := x + 8 * y mit der gleichen Geschwindigkeit durchgeführt werden.

73 oder 37 Verwendung (statt 31) könnte besser sein, weil es dazu führt, dichteren Code : Die beiden LEA Anweisungen nehmen nur 6 Bytes gegen die 7 Byte für unterwegs + Shift + subtrahieren für die Multiplikation mit 31. eine mögliche Einschränkung ist, dass die 3-Argument LEA Anweisungen verwendet hier wurde langsamer auf Intels Sandy-Bridge-Architektur, mit einer erhöhten Latenzzeit von 3 Zyklen.

Darüber hinaus 73 ist die Lieblingszahl von Sheldon Cooper.

Neil Coffey erklärt warum 31 unter verwendet wird Bügeln aus der Bias .

Im Grunde genommen mit 31 gibt Ihnen eine noch Set-Bit-Wahrscheinlichkeitsverteilung für die Hash-Funktion.

JDK-4.045.622 , wo Joshua Bloch die Gründe beschrieben, warum diese bestimmten (neu) String.hashCode() Implementierung wurde gewählt,

  

Die folgende Tabelle fasst die Leistung der verschiedenen Hash   Funktionen, die oben beschrieben wurde, für drei Datensätze:

     

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

     

2) alle Saiten in / bin / / usr / bin / , / usr / lib / / usr / ucb /          und / usr / openwin / bin / * (66.304 Strings, avg Länge 21 Zeichen).

     

3) Eine Liste von URLs von einem Web-Crawler gesammelt, die für mehr lief          Stunden gestern Abend (28.372 Strings, avg Länge 49 Zeichen).

     

Die Performance-Metrik in der Tabelle dargestellt ist die „durchschnittliche Kettengröße“   über alle Elemente in der Hash-Tabelle (das heißt der erwartete Wert der   Anzahl der Schlüssel vergleicht ein Element zu sehen). 

                          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
     

an diesem Tisch suchen, ist es klar, dass alle Funktionen mit Ausnahme   die aktuelle Java-Funktion und die beiden gebrochenen Versionen von Weinbergers   Funktion bietet eine hervorragende, fast nicht zu unterscheiden Leistung. ich   stark vermutet, dass diese Leistung im Wesentlichen der   „Theoretisches Ideal“, das ist, was Sie erhalten würden, wenn Sie einen echten Zufall verwendet   Zahlengenerator anstelle einer Hash-Funktion.

     

Ich würde die WAIS-Funktion ausschließen wie seine Spezifikation Seiten von Zufallszahlen enthält, und seine Leistung ist nicht besser als eine der   weit einfachere Funktionen. Jede der verbleibenden sechs Funktionen scheinen, wie   eine ausgezeichnete Wahl, aber wir haben eine holen. Ich glaube, ich würde ausschließen   Vo der Variante und Weinbergers Funktion wegen ihrer zusätzlichen   Komplexität, wenn auch gering. Von den verbleibenden vier, würde ich wahrscheinlich wählen   P (31), wie es ist die billigste auf einer RISC-Maschine zu berechnen (weil 31   ist der Unterschied von zwei Zweierpotenzen). P (33) ist in ähnlicher Weise billig   berechnen, aber es ist Leistung ist geringfügig schlechter, und 33 ist   Verbund, was mich ein bisschen nervös macht.

     

Josh

Ich bin mir nicht sicher, aber ich würde vermuten, sie eine Probe von Primzahlen getestet und festgestellt, dass 31 die beste Verteilung über einige Beispiele von möglichen Strings gab.

Bloch nicht ganz in diesen gehen, aber die Begründung Ich habe immer gehört / angenommen, dass diese einfache Algebra ist. Hashes einkochen zu Multiplikation und Modul-Operationen, was bedeutet, dass Sie nie mit gemeinsamen Faktoren verwenden Zahlen wollen, wenn Sie ihm helfen können. Mit anderen Worten, eine relativ Primzahlen eine gleichmäßige Verteilung der Antworten.

Die Zahlen, die einen Hash mit Make-up sind in der Regel:

  • Modul des Datentyps man es in eine (2 ^ 32 oder 2 ^ 64)
  • Modul der Eimer Zahl in Ihrer Hash-Tabelle (variiert. In Java verwendet prim zu sein, jetzt 2 ^ n)
  • multiplizieren oder durch eine magische Zahl in der Mischfunktion verschieben
  • Der Eingangswert

Sie erhalten wirklich nur ein paar dieser Werte zu steuern, so dass ein wenig zusätzliche Pflege fällig ist.

neueste Version von JDK, 31 ist nach wie vor verwendet. https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html#hashCode ()

Der Zweck des Hash-String

  • unique (Let Operator ^ in hashcode Berechnung Dokument sehen, die es einzigartig helfen)
  • billig Kosten für die Berechnung

31 max-Wert kann in 8-Bit gesetzt (= 1 Byte) -Register. ist, kann größte Primzahl in 1-Byte-Register gesetzt, eine ungerade Zahl ist.

Multiply 31 << 5 dann selbst subtrahieren, müssen daher billig Ressourcen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top