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

Question

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?

Answer 1

Nach dem Buch von Joshua Bloch Leistungsfähiges Java (ein Buch, das nicht genug empfohlen werden kann und das ich dank der ständigen Erwähnungen auf Stackoverflow gekauft habe):

Der Wert 31 wurde gewählt, weil er eine ungerade Primzahl ist. Wäre er gerade und die Multiplikation würde überlaufen, würden Informationen verloren gehen, da die Multiplikation mit 2 einer Verschiebung gleichkommt. Der Vorteil der Verwendung einer Primzahl ist weniger klar, aber er ist traditionell. Eine schöne Eigenschaft von 31 ist, dass die Multiplikation durch eine Verschiebung und eine Subtraktion ersetzt werden kann, um die Leistung zu verbessern: 31 * i == (i << 5) - i . Moderne VMs führen diese Art der Optimierung automatisch durch.

(aus Kapitel 3, Punkt 9: Überschreiben Sie immer den Hashcode, wenn Sie die Gleichung überschreiben, Seite 48)

Answer 2

Goodrich und Tamassia berechneten anhand von über 50.000 englischen Wörtern (gebildet aus der Vereinigung der Wortlisten zweier Unix-Varianten), dass die Verwendung der Konstanten 31, 33, 37, 39 und 41 jeweils zu weniger als 7 Kollisionen führt. Dies mag der Grund dafür sein, dass so viele Java-Implementierungen solche Konstanten wählen.

Siehe Abschnitt 9.2 Hash-Tabellen (Seite 522) von Datenstrukturen und Algorithmen in Java .

Answer 3

Auf (meist) alten Prozessoren kann die Multiplikation mit 31 relativ billig sein. Auf einem ARM ist es zum Beispiel nur eine Anweisung:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

Die meisten anderen Prozessoren würden eine separate Schiebe- und Subtraktionsanweisung erfordern. Wenn Ihr Multiplikator jedoch langsam ist, ist dies immer noch ein Gewinn. Moderne Prozessoren haben in der Regel schnelle Multiplizierer, so dass es keinen großen Unterschied macht, solange 32 auf die richtige Seite geht.

Es ist kein großartiger Hash-Algorithmus, aber er ist gut genug und besser als der 1.0-Code (und sehr viel besser als die 1.0-Spezifikation!).

Answer 4

Beim Multiplizieren werden die Bits nach links verschoben. Dadurch wird der verfügbare Platz der Hash-Codes besser genutzt und Kollisionen werden reduziert.

Da keine Zweierpotenz verwendet wird, werden auch die untergeordneten, ganz rechts liegenden Bits aufgefüllt und mit den nächsten Daten gemischt, die in den Hash eingehen.

Der Ausdruck n * 31 ist gleichbedeutend mit (n << 5) - n .

Answer 5

Die ursprüngliche Argumentation von Bloch können Sie unter "Kommentare" in http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 . Er untersuchte die Leistung verschiedener Hash-Funktionen im Hinblick auf die resultierende "durchschnittliche Kettengröße" in einer Hash-Tabelle. P(31) war eine der damals üblichen Funktionen, die er in dem Buch von K&R gefunden hatte (aber selbst Kernighan und Ritchie konnten sich nicht erinnern, woher sie stammte). Am Ende musste er sich im Grunde für eine entscheiden, und so nahm er P(31) da sie anscheinend gut genug funktioniert. Auch wenn P(33) nicht wirklich schlechter war und die Multiplikation mit 33 ebenso schnell zu berechnen ist (nur eine Verschiebung um 5 und eine Addition), entschied er sich für 31, da 33 keine Primzahl ist:

Von den übrigen würde ich wahrscheinlich P(31) wählen, da es auf einem RISC-Rechner am einfachsten zu berechnen ist (weil 31 die Differenz zweier Zweierpotenzen ist). Maschine zu berechnen ist (weil 31 die Differenz zweier Zweierpotenzen ist). P(33) ist ähnlich billig zu berechnen, aber seine Leistung ist geringfügig schlechter, und 33 ist zusammengesetzt, was mich ein wenig nervös macht.

Die Argumentation war also nicht so rational, wie viele der Antworten hier zu implizieren scheinen. Aber wir sind alle gut darin, nach Bauchentscheidungen rationale Gründe zu finden (und selbst Bloch könnte dazu neigen).