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).
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/
1 Stimmen
@DushyantSabharwal Ich will damit sagen, dass es auch wurde 29 oder 37 oder 97 oder 41 oder viele andere Werte, ohne dass dies einen großen praktischen Unterschied macht. Wir haben 1976 37 verwendet.