Warum eine Primzahl in hashCode verwenden?

Ich habe mich nur gefragt, warum diese Primzahlen in der hashCode()Methode einer Klasse verwendet werden. Wenn Sie beispielsweise Eclipse zum Generieren meiner hashCode()Methode verwenden, wird immer die Primzahl 31verwendet:

public int hashCode() {
     final int prime = 31;
     //...
}

Verweise:

Hier ist eine gute Einführung in Hashcode und ein Artikel darüber, wie Hashing funktioniert, das ich gefunden habe (C #, aber die Konzepte sind übertragbar): Eric Lipperts Richtlinien und Regeln für GetHashCode ()

Weil Sie möchten, dass die Anzahl, mit der Sie multiplizieren, und die Anzahl der Buckets, in die Sie einfügen, orthogonale Primfaktoren enthalten.

Angenommen, es gibt 8 Eimer zum Einsetzen. Wenn die Zahl, mit der Sie multiplizieren, ein Vielfaches von 8 ist, wird der eingefügte Bucket nur durch den niedrigstwertigen Eintrag bestimmt (den, der überhaupt nicht multipliziert wird). Ähnliche Einträge kollidieren. Nicht gut für eine Hash-Funktion.

31 ist eine Primzahl, die groß genug ist, dass die Anzahl der Buckets wahrscheinlich nicht durch sie teilbar ist (und tatsächlich halten moderne Java-HashMap-Implementierungen die Anzahl der Buckets auf einer Potenz von 2).

Primzahlen werden ausgewählt, um Daten am besten auf Hash-Buckets zu verteilen. Wenn die Verteilung der Eingaben zufällig und gleichmäßig verteilt ist, spielt die Wahl des Hash-Codes / Moduls keine Rolle. Dies wirkt sich nur aus, wenn die Eingaben ein bestimmtes Muster aufweisen.

Dies ist häufig beim Umgang mit Speicherplätzen der Fall. Beispielsweise sind alle 32-Bit-Ganzzahlen an Adressen ausgerichtet, die durch 4 teilbar sind. In der folgenden Tabelle werden die Auswirkungen der Verwendung eines Prim- oder Nicht-Prim-Moduls dargestellt:

Input       Modulo 8    Modulo 7
0           0           0
4           4           4
8           0           1
12          4           5
16          0           2
20          4           6
24          0           3
28          4           0

Beachten Sie die nahezu perfekte Verteilung, wenn Sie einen Primzahlmodul im Vergleich zu einem Nicht-Primzahlmodul verwenden.

Obwohl das obige Beispiel weitgehend erfunden ist, besteht das allgemeine Prinzip darin, dass bei der Behandlung eines Musters von Eingaben die Verwendung eines Primzahlmoduls die beste Verteilung ergibt.

Für das, was es wert ist, verzichtet Effective Java 2nd Edition von Hand auf das Mathematikproblem und sagt nur, dass der Grund für die Wahl von 31 ist:

• Weil es eine seltsame Primzahl ist und es "traditionell" ist, Primzahlen zu verwenden
• Es ist auch eins weniger als eine Zweierpotenz, was eine bitweise Optimierung ermöglicht

Hier ist das vollständige Zitat aus Punkt 9: Immer überschreiben, hashCodewenn Sie überschreibenequals :

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 durch eine Verschiebung ( §15.19 ) und Subtraktion ersetzt werden kann, um eine bessere Leistung zu erzielen:

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

Moderne VMs führen diese Art der Optimierung automatisch durch.

---

Während das Rezept in diesem Artikel einigermaßen gute Hash-Funktionen liefert, liefert es weder Hash-Funktionen auf dem neuesten Stand der Technik, noch bieten Java-Plattformbibliotheken solche Hash-Funktionen ab Version 1.6. Das Schreiben solcher Hash-Funktionen ist ein Forschungsthema, das am besten Mathematikern und theoretischen Informatikern überlassen bleibt.

Möglicherweise bietet eine spätere Version der Plattform Hash-Funktionen für ihre Klassen und Dienstprogrammmethoden auf dem neuesten Stand der Technik, damit durchschnittliche Programmierer solche Hash-Funktionen erstellen können. In der Zwischenzeit sollten die in diesem Artikel beschriebenen Techniken für die meisten Anwendungen geeignet sein.

Eher vereinfacht kann gesagt werden, dass die Verwendung eines Multiplikators mit zahlreichen Teilern zu mehr Hash-Kollisionen führt . Da wir für ein effektives Hashing die Anzahl der Kollisionen minimieren möchten, versuchen wir, einen Multiplikator mit weniger Teilern zu verwenden. Eine Primzahl hat per Definition genau zwei unterschiedliche positive Teiler.

Verwandte Fragen

• Java-Hashcode aus einem Feld - das Rezept sowie ein Beispiel für die Verwendung der Builder von Apache Commons Lang
• Ist es falsch, einen Hashcode eines Objekts als Summe, Multiplikation aller Klassenvariablen-Hashcodes zu definieren?
• Absoluter Anfängerleitfaden zur Bitverschiebung?

Ich habe gehört, dass 31 gewählt wurde, damit der Compiler die Multiplikation optimieren kann, um 5 Bits nach links zu verschieben und dann den Wert zu subtrahieren.

Hier ist ein Zitat etwas näher an der Quelle.

Es läuft darauf hinaus:

• 31 ist eine Primzahl, die Kollisionen reduziert
• 31 ergibt eine gute Verteilung mit
• ein vernünftiger Kompromiss in der Geschwindigkeit

Zuerst berechnen Sie den Hashwert modulo 2 ^ 32 (die Größe von an int), also möchten Sie etwas relativ Primes bis 2 ^ 32 (relativ Prim bedeutet, dass es keine gemeinsamen Teiler gibt). Jede ungerade Zahl würde dafür ausreichen.

Dann wird für eine gegebene Hash-Tabelle der Index normalerweise aus dem Hash-Wert modulo der Größe der Hash-Tabelle berechnet, sodass Sie etwas wollen, das relativ prim zu der Größe der Hash-Tabelle ist. Oft werden aus diesem Grund die Größen von Hash-Tabellen als Primzahlen gewählt. Im Fall von Java stellt die Sun-Implementierung sicher, dass die Größe immer eine Zweierpotenz ist, sodass auch hier eine ungerade Zahl ausreichen würde. Es gibt auch einige zusätzliche Massagen der Hash-Schlüssel, um Kollisionen weiter zu begrenzen.

Der schlechte Effekt, wenn die Hash-Tabelle und der Multiplikator einen gemeinsamen Faktor nhätten, könnte sein, dass unter bestimmten Umständen nur 1 / n Einträge in der Hash-Tabelle verwendet werden.

Der Grund, warum Primzahlen verwendet werden, besteht darin, Kollisionen zu minimieren, wenn die Daten bestimmte Muster aufweisen.

Das Wichtigste zuerst: Wenn die Daten zufällig sind, ist keine Primzahl erforderlich. Sie können eine Mod-Operation für eine beliebige Zahl ausführen und haben für jeden möglichen Wert des Moduls die gleiche Anzahl von Kollisionen.

Aber wenn Daten nicht zufällig sind, passieren seltsame Dinge. Betrachten Sie beispielsweise numerische Daten, die immer ein Vielfaches von 10 sind.

Wenn wir Mod 4 verwenden, finden wir:

10 mod 4 = 2

20 mod 4 = 0

30 mod 4 = 2

40 mod 4 = 0

50 mod 4 = 2

Von den 3 möglichen Werten des Moduls (0,1,2,3) haben also nur 0 und 2 Kollisionen, das ist schlecht.

Wenn wir eine Primzahl wie 7 verwenden:

10 mod 7 = 3

20 mod 7 = 6

30 mod 7 = 2

40 mod 7 = 4

50 mod 7 = 1

etc

Wir stellen auch fest, dass 5 keine gute Wahl ist, aber 5 eine Primzahl ist. Der Grund dafür ist, dass alle unsere Schlüssel ein Vielfaches von 5 sind. Dies bedeutet, dass wir eine Primzahl wählen müssen, die unsere Schlüssel nicht teilt. Die Wahl einer großen Primzahl ist normalerweise genug.

Der Grund, warum Primzahlen verwendet werden, besteht darin, den Effekt von Mustern in den Schlüsseln bei der Verteilung von Kollisionen einer Hash-Funktion zu neutralisieren.

31 ist auch spezifisch für Java HashMap, das ein int als Hash-Datentyp verwendet. Somit beträgt die maximale Kapazität 2 ^ 32. Es macht keinen Sinn, größere Fermat- oder Mersenne-Primzahlen zu verwenden.

Dies hilft im Allgemeinen dabei, eine gleichmäßigere Verteilung Ihrer Daten auf die Hash-Buckets zu erreichen, insbesondere bei Schlüsseln mit niedriger Entropie.