Was ist eine vernünftige prime für hashcode Berechnung?

Question

Eclipse 3.5 hat eine sehr schöne Funktion Java hashCode () Funktionen zu erzeugen. Es wäre zum Beispiel erzeugen (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(); für jedes zusätzliches Attribut wiederholt. Für Ints .hashCode () verzichtet werden kann.)

Das scheint in Ordnung, aber für die Wahl 31 für die besten Jahre. Es wird wahrscheinlich von der hashCode Implementierung von Java genommen String , die aus Performance-Gründen verwendet wurden, die lange nach der Einführung von Hardware-Multiplizierer gegangen. Hier haben Sie viele hashcode Kollisionen für kleine Werte von i und j: zum Beispiel (0,0) und (bis 1,31) den gleichen Wert. Ich denke, das ist eine schlechte Sache (TM), da kleine Werte häufig auftreten. Für String.hashCode Sie werden auch viele kurze Strings mit dem gleichen Hash-Code, zum Beispiel „Ca“ und „DB“ finden. Wenn Sie eine große Primzahl nehmen, dieses Problem verschwindet, wenn Sie die prime rechts wählen.

Also meine Frage: Was ist ein guter prim zu wählen? Welche Kriterien gelten Sie es zu finden?

Dies wird als eine allgemeine Frage gemeint - so will ich nicht einen Bereich für i und j geben. Aber ich nehme an, in den meisten Anwendungen relativ kleine Werte treten häufiger als große Werte. (Wenn Sie die Wahl der prime große Werte haben, ist wahrscheinlich unwichtig.) Es ist vielleicht nicht viel Unterschied machen, aber eine bessere Wahl ist ein einfacher und offensichtlicher Weg, dies zu verbessern - also warum es nicht tun? Commons lang HashCodeBuilder schlägt auch neugierig kleine Werte.

( Klarstellung : Das ist nicht ein Duplikat Warum Java hashCode () in String verwendet 31 als Multiplikator? da meine Frage ist mit der Geschichte der 31 in der JDK nicht betroffen, sondern auf dem, was wäre ein besserer Wert in neuem Code sein, um die gleiche Grundvorlage. Keine der Antworten dort versuchen, das zu beantworten.)

Answer 1

Ich empfehle, mit 92821 . Hier ist der Grund.

Um eine sinnvolle Antwort auf diese Frage geben Sie etwas über die möglichen Werte von i und j wissen müssen. Das einzige, was ich im Allgemeinen denken kann ist, dass in vielen Fällen kleine Werte als große Werte häufiger sein werden. (Die Quote von 15 als Wert in Ihrem Programm erscheint, ist viel besser als, sagt, 438281923.) So scheint es eine gute Idee, das kleinste hashcode Kollision so groß wie möglich zu machen, indem eine geeignete Primzahl wählen. Für 31 dieser eher schlecht - bereits für i=-1 und j=31 haben Sie den gleichen Hash-Wert wie für i=0 und j=0

.

Da dies interessant ist, habe ich ein kleines Programm geschrieben, das den ganzen int Bereich für die beste Prime in diesem Sinne gesucht. Das heißt, für jede Primzahl I für den Minimalwert von Math.abs(i) + Math.abs(j) über alle Werte von i,j gesucht, die den gleichen Hash-Code wie 0,0 haben, und nahm dann die prime wo dieser Minimalwert so groß wie möglich ist.

Paukenwirbel : Die beste prime in diesem Sinne ist 486187739 (mit dem kleinsten Kollision zu sein i=-25486, j=67194). Fast so gut und viel leichter zu merken ist 92821 mit dem kleinsten Kollision zu sein i=-46272 and j=46016.

Wenn Sie geben „kleine“ eine andere Bedeutung und wollen das Minimum von Math.sqrt(i*i+j*j) für die Kollision so groß wie möglich sein, sind die Ergebnisse ein wenig anders: die beste 1322837333 mit i=-6815 and j=70091 sein würde, aber mein Favorit 92821 (kleinste Kollision -46272,46016 ) ist wieder fast so gut wie der beste Wert.

ich bestätigen, dass es durchaus fraglich ist, ob diese Berechnung viel Sinn in der Praxis machen. Aber ich glaube, dass 92821 als Haupt nehmen macht viel mehr Sinn als 31, es sei denn, Sie gute Gründe haben, nicht zu tun.

Answer 2

Eigentlich, wenn Sie eine erstklassige so groß nehmen, dass es nahe kommt zu INT_MAX, Sie haben das gleiche Problem, weil der Modulo-Arithmetik. Wenn Sie meistens Strings der Länge 2, um Hash erwarten vielleicht eine Primzahl in der Nähe der Quadratwurzel INT_MAX wäre am besten, wenn die Strings Sie Hash länger es spielt keine Rolle, so viel und Kollisionen unvermeidbar sind sowieso ...

Answer 3

Collisions kann nicht so ein großes Problem sein ... Das primäre Ziel des Hash zu vermeiden, ist equals mit 1: 1 Vergleich. Wenn Sie eine Implementierung haben, wo gleich ist „in der Regel“ extrem billig für Objekte, die hashs kollidiert, dann ist dies kein Problem (überhaupt).

Am Ende, was ist der beste Weg, Hashing hängt davon ab, was Sie vergleichen. Im Fall eines int Paares (wie in Ihrem Beispiel) könnte grundlegende Bitoperatoren mit ausreichend sein (wie mit & oder ^).

Answer 4

Sie benötigen Bereich für i und j zu definieren. Sie könnten eine Primzahl für beide verwenden.

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

Answer 5

würde ich 7243. Groß genug, um wählen collissions mit kleinen Stückzahlen zu vermeiden. Nicht schnell auf kleine Zahlen überlaufen.

Answer 6

Ich möchte nur darauf hinweisen, dass hashcode nichts mit prim zu tun hat. In JDK-Implementierung

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

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