Was ist eine sinnvolle Primzahl für die Hashcode-Berechnung?

Question 1

Eclipse 3.5 hat ein sehr nettes Feature, um Java hashCode()-Funktionen zu generieren. Es würde zum Beispiel (leicht gekürzt:)

class HashTest {
    int i;
    int j;        
    public int hashCode() {
        final int prime = 31;
        int result = prime + i;
        result = prime * result + j;
        return result;
    }
}

(Wenn Sie mehr Attribute in der Klasse haben, result = prime * result + attribute.hashCode(); wird für jedes weitere Attribut wiederholt. Bei ints kann .hashCode() weggelassen werden.)

Dies scheint in Ordnung zu sein, aber für die Wahl 31 für die Primzahl. Es stammt wahrscheinlich aus der hashCode-Implementierung von Java String, die aus Performance-Gründen verwendet wurde, die nach der Einführung von Hardware-Multiplikatoren längst vorbei sind. Hier haben Sie viele Hashcode-Kollisionen für kleine Werte von i und j: zum Beispiel (0,0) und (-1,31) haben denselben Wert. Ich denke, das ist eine schlechte Sache (TM), da häufig kleine Werte auftreten. Für String.hashCode finden Sie auch viele kurze Zeichenfolgen mit demselben Hashcode, zum Beispiel “Ca” und “DB”. Wenn Sie eine große Primzahl nehmen, verschwindet dieses Problem, wenn Sie die Primzahl rechts wählen.

Also meine Frage: Was ist eine gute Primzahl zu wählen? Nach welchen Kriterien finden Sie es?

Dies ist als allgemeine Frage gedacht – daher möchte ich keinen Bereich für i und j angeben. Aber ich nehme an, dass in den meisten Anwendungen relativ kleine Werte häufiger vorkommen als große Werte. (Wenn Sie große Werte haben, ist die Wahl der Primzahl wahrscheinlich unwichtig.) Es macht vielleicht keinen großen Unterschied, aber eine bessere Wahl ist eine einfache und offensichtliche Möglichkeit, dies zu verbessern – warum also nicht? Commons lang HashCodeBuilder schlägt auch merkwürdig kleine Werte vor.

(Klärung: das ist nicht ein Duplikat von Warum verwendet Javas hashCode() in String 31 als Multiplikator? da sich meine Frage nicht auf die Geschichte der 31 im JDK bezieht, sondern darauf, was ein besserer Wert in neuem Code wäre, der dieselbe grundlegende Vorlage verwendet. Keine der Antworten dort versuchen, das zu beantworten.)

Question 2

Ich empfehle die Verwendung 92821. Hier ist der Grund.

Um darauf eine sinnvolle Antwort zu geben, muss man etwas über die möglichen Werte von wissen i und j. Das einzige, was mir allgemein einfällt, ist, dass in vielen Fällen kleine Werte häufiger vorkommen als große Werte. (Die Wahrscheinlichkeit, dass 15 als Wert in Ihrem Programm erscheint, ist viel besser als beispielsweise 438281923.) Daher scheint es eine gute Idee zu sein, die kleinste Hashcode-Kollision so groß wie möglich zu machen, indem Sie eine geeignete Primzahl wählen. Für 31 eher schlecht – schon für i=-1 und j=31 Sie haben den gleichen Hashwert wie für i=0 und j=0.

Da dies interessant ist, habe ich ein kleines Programm geschrieben, das den gesamten int-Bereich nach der besten Primzahl in diesem Sinne durchsucht. Das heißt, für jede Primzahl suchte ich nach dem Mindestwert von Math.abs(i) + Math.abs(j) über alle Werte von i,j die den gleichen Hashcode haben wie 0,0und dann die Primzahl genommen, wo dieser minimale Wert so groß wie möglich ist.

Trommelwirbel: Die beste Primzahl in diesem Sinne ist 486187739 (wobei die kleinste Kollision ist i=-25486, j=67194). Fast genauso gut und viel leichter zu merken ist 92821 mit der kleinsten Kollision i=-46272 and j=46016.

Wenn Sie “klein” eine andere Bedeutung geben und das Minimum sein wollen Math.sqrt(i*i+j*j) für die möglichst große kollision sind die ergebnisse etwas anders: am besten wäre 1322837333 mit i=-6815 and j=70091aber mein Favorit 92821 (kleinste Kollision -46272,46016) ist wieder fast so gut wie der Bestwert.

Ich gebe zu, dass es ziemlich umstritten ist, ob diese Berechnungen in der Praxis viel Sinn machen. Aber ich denke, dass es viel sinnvoller ist, 92821 als Primzahl zu nehmen als 31, es sei denn, Sie haben gute Gründe, dies nicht zu tun.

Question 3

Eigentlich, wenn Sie eine Primzahl so groß nehmen, dass sie nahe kommt INT_MAX, haben Sie das gleiche Problem wegen der Modulo-Arithmetik. Wenn Sie erwarten, hauptsächlich Zeichenfolgen der Länge 2 zu hashen, vielleicht eine Primzahl in der Nähe der Quadratwurzel von INT_MAX wäre am besten, wenn die Zeichenfolgen, die Sie hashen, länger sind, spielt es keine Rolle, und Kollisionen sind sowieso unvermeidlich …

Question 4

Kollisionen sind vielleicht kein so großes Problem … Das Hauptziel des Hashs ist es, die Verwendung von Gleichheitszeichen für 1: 1-Vergleiche zu vermeiden. Wenn Sie eine Implementierung haben, bei der equals “im Allgemeinen” extrem billig für Objekte ist, die kollidierte Hashes haben, dann ist dies (überhaupt) kein Problem.

Letztendlich hängt die beste Art des Hashings davon ab, was Sie vergleichen. Im Fall eines int-Paares (wie in Ihrem Beispiel) könnte die Verwendung einfacher bitweiser Operatoren ausreichen (wie die Verwendung von & oder ^).

Question 5

Sie müssen Ihren Bereich für i und j definieren. Sie könnten für beide eine Primzahl verwenden.

public int hashCode() {
   http://primes.utm.edu/curios/ ;)
   return 97654321 * i ^ 12356789 * j;
}

Question 6

Ich würde 7243 wählen. Groß genug, um Kollisionen mit kleinen Zahlen zu vermeiden. Läuft nicht schnell zu kleinen Zahlen über.

Question 7

Ich möchte nur darauf hinweisen, dass Hashcode nichts mit Prime zu tun hat. In der JDK-Implementierung

for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }

Ich fand, wenn Sie ersetzen 31 mit 27das Ergebnis ist sehr ähnlich.