Warum verwendet Java's hashCode() in String 31 als Multiplikator?

Question

Gemäß der Java-Dokumentation ist die [Hash-Code](http://java.sun.com/javase/6/docs/api/java/lang/String.html#hashCode()) für eine String Objekt wird wie folgt berechnet:

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

mit int Arithmetik, wobei s[i] ist die i Zeichen der Zeichenkette, n ist die Länge von der Zeichenkette, und ^ bedeutet Potenzierung.

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?

Answer 1

Eigentlich würden 37 ziemlich gut funktionieren! z := 37 * x kann wie folgt berechnet werden y := x + 8 * x; z := x + 4 * y . Beide Schritte entsprechen einem LEA x86-Befehl, so dass dies extrem schnell ist.

Die Multiplikation mit der noch größeren Primzahl 73 könnte mit der gleichen Geschwindigkeit durchgeführt werden, indem die y := x + 8 * x; z := x + 8 * y .

Die Verwendung von 73 oder 37 (anstelle von 31) könnte besser sein, da dies zu folgenden Ergebnissen führt dichterer Code : Die beiden LEA-Befehle benötigen nur 6 Bytes im Vergleich zu den 7 Bytes für Move+Shift+Subtract für die Multiplikation mit 31. Ein möglicher Vorbehalt ist, dass die hier verwendeten LEA-Befehle mit 3 Argumenten auf Intels Sandy-Bridge-Architektur langsamer geworden sind, mit einer erhöhten Latenz von 3 Zyklen.

Außerdem, 73 ist die Lieblingszahl von Sheldon Cooper.

Answer 2

Neil Coffey erklärt warum 31 verwendet wird unter Beseitigung der Vorurteile .

Die Verwendung von 31 ergibt eine gleichmäßigere Verteilung der Bit-Wahrscheinlichkeit für die Hash-Funktion.

Answer 3

から JDK-4045622 in dem Joshua Bloch die Gründe beschreibt, warum diese besondere (neue) String.hashCode() Implementierung gewählt wurde

Die nachstehende Tabelle gibt einen Überblick über die Leistung der verschiedenen Hashwerte Funktionen für drei Datensätze zusammen:

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

2) Alle Zeichenketten 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 Web-Crawler gesammelt wurden, der letzte Nacht mehrere Stunden lang lief Stunden lang lief (28.372 Zeichenfolgen, durchschnittliche Länge 49 Zeichen).

Die in der Tabelle angegebene Leistungskennzahl ist die "durchschnittliche Kettengröße" über alle Elemente in der Hashtabelle (d. h. der Erwartungswert der Anzahl der Schlüsselvergleiche zum Nachschlagen eines Elements).

                          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

Ein Blick auf diese Tabelle zeigt, dass alle Funktionen mit Ausnahme der Funktion die aktuelle Java-Funktion und die beiden kaputten Versionen von Weinbergers eine ausgezeichnete, nahezu ununterscheidbare Leistung bieten. I vermute stark, dass diese Leistung im Wesentlichen das "theoretische Ideal" ist, das man erreichen würde, wenn man einen echten Zufallsgenerator Zufallszahlengenerator anstelle einer Hash-Funktion verwenden würde.

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 übrigen sechs Funktionen scheint ausgezeichnete Wahl, aber wir müssen uns für eine entscheiden. Ich denke, ich würde ausschließen Vo's Variante und Weinberger's Funktion ausschließen, weil sie zusätzlich Komplexität ausschließen, auch wenn sie gering ist. Von den verbleibenden vier Funktionen würde ich mich wahrscheinlich für P(31) wählen, da sie auf einer RISC-Maschine am einfachsten zu berechnen ist (weil 31 die Differenz von zwei Zweierpotenzen ist). P(33) ist ähnlich billig zu berechnen berechnen, aber die Leistung ist geringfügig schlechter, und 33 ist zusammengesetzt, was mich ein wenig nervös macht.

Josh

Answer 4

Java String hashCode() und 31

Das liegt daran, dass 31 eine schöne Eigenschaft hat - seine Multiplikation kann durch eine bitweise Verschiebung ersetzt werden, die schneller ist als die Standardmultiplikation:

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

Answer 5

Bloch geht nicht ganz darauf ein, aber die Begründung, die ich immer gehört bzw. geglaubt habe, ist, dass es sich um grundlegende Algebra handelt. Hashes laufen auf Multiplikations- und Modulusoperationen hinaus, was bedeutet, dass man niemals Zahlen mit gemeinsamen Faktoren verwenden sollte, wenn es sich vermeiden lässt. Mit anderen Worten: Relativ primäre Zahlen sorgen für eine gleichmäßige Verteilung der Antworten.

Die Zahlen, aus denen ein Hash besteht, sind in der Regel:

• Modulus des Datentyps, in den Sie ihn einfügen (2^32 oder 2^64)
• Modulus der Bucket-Anzahl in Ihrer Hashtabelle (variiert. In Java war es früher prime, jetzt 2^n)
• Multiplizieren oder Verschieben mit einer magischen Zahl in Ihrer Mischfunktion
• Der Eingabewert

Da Sie nur einige dieser Werte wirklich kontrollieren können, ist ein wenig mehr Sorgfalt angebracht.