590 Stimmen

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

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?

16 Stimmen

Wenn es 29 oder 37 oder sogar 97 wäre, würden Sie fragen: "Warum nicht 31?

3 Stimmen

@EJP es ist wichtig, den Grund für die Wahl einer Nummer zu kennen, es sei denn, die Nummer ist das Ergebnis eines schwarzen Zaubertricks.

0 Stimmen

Es gibt einen Blogbeitrag von @peter-lawrey darüber hier: vanilla-java.github.io/2018/08/12/ und hier: vanilla-java.github.io/2018/08/15/

5voto

Do Nhu Vy Punkte 38281

In der neuesten Version von JDK wird immer noch 31 verwendet. [https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode()](https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode())

Der Zweck einer Hash-Zeichenkette ist

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

31 ist der maximale Wert, der in einem 8-Bit-Register (= 1 Byte) abgelegt werden kann, ist die größte Primzahl, die in einem 1-Byte-Register abgelegt werden kann, ist eine ungerade Zahl.

Multiplizieren Sie 31 ist <<5 dann subtrahieren Sie sich, deshalb brauchen billige Ressourcen.

3voto

Dave L. Punkte 42559

Ich bin mir nicht sicher, aber ich würde vermuten, dass sie eine Stichprobe von Primzahlen getestet und festgestellt haben, dass 31 die beste Verteilung über eine Stichprobe möglicher Zeichenketten ergibt.

1voto

Altan Punkte 83

Eine große Erwartung an Hash-Funktionen ist, dass die gleichmäßige Zufälligkeit ihres Ergebnisses eine Operation wie die folgende übersteht hash(x) % N wobei N eine beliebige Zahl (und in vielen Fällen eine Zweierpotenz) ist. Ein Grund dafür ist, dass solche Operationen häufig in Hash-Tabellen zur Bestimmung von Slots verwendet werden. Die Verwendung von Primzahlmultiplikatoren bei der Berechnung des Hashwerts verringert die Wahrscheinlichkeit, dass Ihr Multiplikator und N einen gemeinsamen Teiler haben, was das Ergebnis der Operation weniger gleichmäßig zufällig machen würde.

Andere haben auf die schöne Eigenschaft hingewiesen, dass die Multiplikation mit 31 durch eine Multiplikation und eine Subtraktion erfolgen kann. Ich möchte nur darauf hinweisen, dass es einen mathematischen Begriff für solche Primzahlen gibt: Mersenne-Primzahl

Alle Mersenne-Primzahlen sind um eins kleiner als eine Zweierpotenz, so dass wir sie als schreiben können:

p = 2^n - 1

Multiplikation von x mit p:

x * p = x * (2^n - 1) = x * 2^n - x = (x << n) - x

Verschiebungen (SAL/SHL) und Subtraktionen (SUB) sind auf vielen Maschinen im Allgemeinen schneller als Multiplikationen (MUL). Siehe Anweisungstabellen von Agner Fog

Deshalb scheint der GCC Multiplikationen mit Mersenne-Primzahlen zu optimieren, indem er sie durch Shifts und Subs ersetzt, siehe hier .

Meiner Meinung nach ist eine so kleine Primzahl jedoch eine schlechte Wahl für eine Hash-Funktion. Bei einer relativ guten Hash-Funktion würde man erwarten, dass in den höheren Bits des Hashes Zufälligkeit herrscht. Bei der Java-Hash-Funktion gibt es jedoch bei kürzeren Zeichenketten fast keine Zufälligkeit in den höheren Bits (und immer noch höchst fragwürdige Zufälligkeit in den unteren Bits). Das macht es schwieriger, effiziente Hash-Tabellen zu erstellen. Siehe diesen netten Trick, den man mit der Java-Hash-Funktion nicht machen kann .

In einigen Antworten wird erwähnt, dass sie es für gut halten, dass 31 in ein Byte passt. Dies ist eigentlich nutzlos, da:

(1) Wir führen Verschiebungen anstelle von Multiplikationen durch, so dass die Größe des Multiplikators keine Rolle spielt.

(2) Soweit ich weiß, gibt es keinen speziellen x86-Befehl, um einen 8-Byte-Wert mit einem 1-Byte-Wert zu multiplizieren, so dass Sie "31" ohnehin in einen 8-Byte-Wert hätten umwandeln müssen, selbst wenn Sie multipliziert hätten. Siehe aquí multiplizieren Sie ganze 64-Bit-Register.

(Und 127 ist tatsächlich die größte Mersenne-Primzahl, die in ein Byte passt.)

Erhöht ein kleinerer Wert die Zufälligkeit in den mittleren und unteren Bits? Vielleicht, aber es scheint auch die möglichen Kollisionen stark zu erhöhen :).

Man könnte viele verschiedene Probleme aufzählen, aber im Allgemeinen laufen sie auf zwei Kernprinzipien hinaus, die nicht gut erfüllt werden: Konfusion und Diffusion

Aber ist es schnell? Wahrscheinlich, denn er macht nicht viel. Wenn es hier jedoch wirklich um Leistung geht, ist ein Zeichen pro Schleife ziemlich ineffizient. Warum nicht 4 Zeichen auf einmal (8 Byte) pro Schleifenwiederholung für längere Zeichenfolgen? wie diese ? Nun, das wäre schwierig, mit der aktuellen Definition von Hash zu tun, wo Sie jedes Zeichen einzeln multiplizieren müssen (bitte sagen Sie mir, wenn es einen kleinen Hack gibt, um dies zu lösen :D).

CodeJaeger.com

CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.

Powered by:

X