Konsistenz von hashCode () in einer Java-Zeichenfolge

134

Der hashCode-Wert eines Java- Strings wird wie folgt berechnet: ( String.hashCode () ):

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

Gibt es Umstände (z. B. JVM-Version, Anbieter usw.), unter denen der folgende Ausdruck als falsch ausgewertet wird?

boolean expression = "This is a Java string".hashCode() == 586653468

Update Nr. 1: Wenn Sie behaupten, dass die Antwort "Ja, es gibt solche Umstände" lautet, geben Sie bitte ein konkretes Beispiel dafür, wann "Dies ist eine Java-Zeichenfolge" .hashCode ()! = 586653468. Versuchen Sie, so spezifisch / konkret zu sein wie möglich.

Update Nr. 2: Wir alle wissen, dass es im Allgemeinen schlecht ist, sich auf die Implementierungsdetails von hashCode () zu verlassen. Ich spreche jedoch speziell über String.hashCode (). Bitte konzentrieren Sie die Antwort auf String.hashCode (). Object.hashCode () ist im Kontext dieser Frage völlig irrelevant.

knorv
quelle
2
Benötigen Sie diese Funktionalität tatsächlich? Warum brauchen Sie den genauen Wert?
Brian Agnew
26
@Brian: Ich versuche den Vertrag von String.hashCode () zu verstehen.
Knorv
3
@Knorv Es ist nicht notwendig, genau zu verstehen, wie es funktioniert - es ist wichtiger, den Vertrag und seine hintergründige Bedeutung zu verstehen.
mP.
45
@mP: Danke für deine Eingabe, aber ich denke, es liegt an mir zu entscheiden.
Knorv
Warum gaben sie dem ersten Charakter die größte Kraft? Wenn Sie die Geschwindigkeit optimieren möchten, um zusätzliche Berechnungen beizubehalten, speichern Sie die Leistung des vorherigen Zeichens, während das vorherige vom letzten bis zum ersten Zeichen reicht. Dies bedeutet, dass es auch zu Cache-Fehlern kommen würde. Ist es nicht effizienter, einen Algorithmus zu haben von: s [0] + s [1] * 31 + s [2] * 31 ^ 2 + ... + s [n-1] * 31 ^ [n-1 ]?
Android-Entwickler

Antworten:

101

Ich kann diese Dokumentation bereits in Java 1.2 sehen.

Zwar sollten Sie sich im Allgemeinen nicht darauf verlassen, dass eine Hash-Code-Implementierung gleich bleibt, aber das Verhalten ist jetzt dokumentiert. Eine java.lang.StringÄnderung würde daher als Bruch bestehender Verträge gelten.

Wo immer möglich, sollten Sie nicht auf Hash - Codes angewiesen , um das gleiche über Versionen bleiben usw. - aber in meinem Kopf java.lang.Stringist ein Sonderfall , weil der Algorithmus hat angegeben ... solange Sie bereit bist , die Kompatibilität verlassen mit Releases vor dem Natürlich wurde ein Algorithmus angegeben.

Jon Skeet
quelle
7
Das dokumentierte Verhalten von String wurde seit Java 1.2 angegeben. In Version 1.1 der API ist die Hash-Code-Berechnung für die String-Klasse nicht angegeben.
Martin OConnor
In diesem Fall schreiben wir besser unsere eigenen Hashing-Codes.
Felype
@Felype: Ich weiß wirklich nicht, was du hier sagen willst, fürchte ich.
Jon Skeet
@ JonSkeet Ich meine, in diesem Fall können wir vielleicht unseren eigenen Code schreiben, um unseren eigenen Hash zu generieren und Portabilität zu gewähren. Ist es?
Felype
@Felype: Es ist überhaupt nicht klar, um welche Art von Portabilität es sich handelt und was Sie unter "in diesem Fall" verstehen - in welchem ​​speziellen Szenario? Ich vermute, Sie sollten eine neue Frage stellen.
Jon Skeet
18

Ich habe etwas über JDK 1.0 und 1.1 gefunden und> = 1.2:

In JDK 1.0.x und 1.1.x arbeitete die HashCode-Funktion für lange Strings, indem jedes n-te Zeichen abgetastet wurde. Dies ist ziemlich sicher, dass Sie viele Strings-Hashing auf den gleichen Wert haben würden, wodurch die Hashtable-Suche verlangsamt wird. In JDK 1.2 wurde die Funktion verbessert, um das bisherige Ergebnis mit 31 zu multiplizieren und dann das nächste Zeichen nacheinander hinzuzufügen. Dies ist etwas langsamer, kann aber Kollisionen viel besser vermeiden. Quelle: http://mindprod.com/jgloss/hashcode.html

Etwas anderes, weil Sie anscheinend eine Nummer benötigen: Wie wäre es mit CRC32 oder MD5 anstelle von Hashcode und Sie können loslegen - keine Diskussionen und überhaupt keine Sorgen ...

ReneS
quelle
8

Sie sollten sich nicht darauf verlassen, dass ein Hash-Code einem bestimmten Wert entspricht. Nur dass es konsistente Ergebnisse innerhalb derselben Ausführung zurückgibt. In den API-Dokumenten heißt es:

Der allgemeine Vertrag von hashCode lautet:

  • Immer wenn es während einer Ausführung einer Java-Anwendung mehr als einmal für dasselbe Objekt aufgerufen wird, muss die hashCode-Methode konsistent dieselbe Ganzzahl zurückgeben, sofern keine Informationen geändert werden, die für gleiche Vergleiche für das Objekt verwendet werden. Diese Ganzzahl muss von einer Ausführung einer Anwendung zu einer anderen Ausführung derselben Anwendung nicht konsistent bleiben.

BEARBEITEN Da das Javadoc für String.hashCode () angibt, wie der Hash-Code eines Strings berechnet wird, würde ein Verstoß gegen diese die öffentliche API-Spezifikation verletzen.

Martin OConnor
quelle
1
Ihre Antwort ist gültig, geht jedoch nicht auf die gestellte Frage ein.
Knorv
6
Das ist der allgemeine Hash-Code-Vertrag - aber der spezifische Vertrag für String enthält Details zum Algorithmus und überschreibt diesen IMO-Generalvertrag effektiv.
Jon Skeet
4

Wie oben erwähnt, sollten Sie sich im Allgemeinen nicht darauf verlassen, dass der Hash-Code einer Klasse gleich bleibt. Beachten Sie, dass auch nachfolgende Ausführungen derselben Anwendung auf derselben VM ausgeführt werden möglicherweise unterschiedliche Hashwerte erzeugen. Die Hash-Funktion von AFAIK the Sun JVM berechnet bei jedem Lauf den gleichen Hash, dies ist jedoch nicht garantiert.

Beachten Sie, dass dies nicht theoretisch ist. Die Hash-Funktion für java.lang.String wurde in JDK1.2 geändert (der alte Hash hatte Probleme mit hierarchischen Zeichenfolgen wie URLs oder Dateinamen, da er tendenziell denselben Hash für Zeichenfolgen erzeugte, die sich nur am Ende unterschieden).

java.lang.String ist ein Sonderfall, da der Algorithmus von hashCode () (jetzt) ​​dokumentiert ist, sodass Sie sich wahrscheinlich darauf verlassen können. Ich würde es immer noch als schlechte Praxis betrachten. Wenn Sie einen Hash-Algorithmus mit speziellen, dokumentierten Eigenschaften benötigen, schreiben Sie einfach einen :-).

sleske
quelle
4
Aber wurde der Algorithmus in den Dokumenten vor JDK 1.2 angegeben? Wenn nicht, ist es eine andere Situation. Der Algorithmus ist jetzt in den Dokumenten festgelegt. Eine Änderung wäre also eine bahnbrechende Änderung eines öffentlichen Auftrags.
Jon Skeet
(Ich erinnere mich an 1.1.) Der ursprüngliche (schlechtere) Algorithmus wurde dokumentiert. Falsch. Der dokumentierte Algorithmus hat tatsächlich eine ArrayIndexOutOfBoundsException ausgelöst.
Tom Hawtin - Tackline
@ Jon Skeet: Ah, wusste nicht, dass der Algorithmus von String.hashCode () dokumentiert ist. Das ändert natürlich die Dinge. Mein Kommentar wurde aktualisiert.
Sleske
3

Ein weiteres (!) Problem, über das Sie sich Sorgen machen müssen, ist die mögliche Änderung der Implementierung zwischen frühen / späten Java-Versionen. Ich glaube nicht, dass die Implementierungsdetails in Stein gemeißelt sind, und daher könnte ein Upgrade auf eine zukünftige Java-Version möglicherweise Probleme verursachen.

Fazit ist, ich würde mich nicht auf die Implementierung von verlassen hashCode().

Vielleicht können Sie mit diesem Mechanismus hervorheben, welches Problem Sie tatsächlich lösen möchten, und dies wird einen geeigneteren Ansatz hervorheben.

Brian Agnew
quelle
1
Danke für deine Antwort. Können Sie konkrete Beispiele dafür geben, wann "Dies ist eine Java-Zeichenfolge" .hashCode ()! = 586653468?
Knorv
1
Nein Entschuldigung. Mein Punkt ist, dass alles, was Sie testen, so funktionieren kann, wie Sie es möchten. Das ist aber noch keine Garantie. Wenn Sie also an einem (sagen wir) kurzfristigen Projekt arbeiten, bei dem Sie die Kontrolle über die VM usw. haben, kann das oben Genannte für Sie funktionieren. Aber in der ganzen Welt kann man sich nicht darauf verlassen.
Brian Agnew
2
"Ein Upgrade auf eine zukünftige Java-Version kann Probleme verursachen". Ein Upgrade auf eine zukünftige Java-Version könnte die hashCode-Methode vollständig entfernen. Oder lassen Sie es immer 0 für Zeichenfolgen zurückgeben. Das sind inkompatible Änderungen für dich. Die Frage ist, ob Sun ^ HOracle ^ HThe JCP dies als eine bahnbrechende Änderung betrachten würde und es daher wert ist, vermieden zu werden. Da der Algorithmus im Vertrag enthalten ist, hofft man, dass sie dies tun würden.
Steve Jessop
@SteveJessop gut, da switchAnweisungen über Zeichenfolgen zu Code kompiliert werden, der auf einem bestimmten festen Hash-Code basiert , würden Änderungen am StringHash-Code-Algorithmus definitiv vorhandenen Code
Holger
3

Nur um Ihre Frage zu beantworten und keine Diskussionen fortzusetzen. Die Apache Harmony JDK-Implementierung scheint einen anderen Algorithmus zu verwenden, zumindest sieht sie völlig anders aus:

Sun JDK

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

Apache Harmony

public int hashCode() {
    if (hashCode == 0) {
        int hash = 0, multiplier = 1;
        for (int i = offset + count - 1; i >= offset; i--) {
            hash += value[i] * multiplier;
            int shifted = multiplier << 5;
            multiplier = shifted - multiplier;
        }
        hashCode = hash;
    }
    return hashCode;
}

Fühlen Sie sich frei, es selbst zu überprüfen ...

ReneS
quelle
23
Ich denke, sie sind einfach cool und optimieren es. :) "(Multiplikator << 5) - Multiplikator" ist immerhin nur 31 * Multiplikator ...
Entspannen Sie sich am
Ok, war zu faul, um das zu überprüfen. Vielen Dank!
ReneS
1
Aber um es von meiner Seite klar zu machen ... Verlassen Sie sich niemals auf den Hashcode, da der Hashcode etwas Internes ist.
ReneS
1
Was bedeuten die Variablen "Offset", "Count" und "HashCode"? Ich nehme an, "Hashcode" wird als zwischengespeicherter Wert verwendet, um zukünftige Berechnungen zu vermeiden, und "count" ist die Anzahl der Zeichen, aber was ist der "Offset"? Angenommen, ich möchte diesen Code verwenden, damit er angesichts einer Zeichenfolge konsistent ist. Was soll ich damit tun?
Android-Entwickler
1
@androiddeveloper Nun, das ist eine interessante Frage - obwohl ich sie aufgrund Ihres Benutzernamens hätte erraten sollen. Aus den Android-Dokumenten geht hervor, dass der Vertrag derselbe ist: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]Wenn ich mich nicht irre, liegt dies daran, dass Android die Implementierung des String-Objekts durch Sun ohne Änderungen verwendet.
Kartik Chugh
2

Wenn Sie sich Sorgen über Änderungen und möglicherweise inkompatible VMs machen, kopieren Sie einfach die vorhandene Hashcode-Implementierung in Ihre eigene Dienstprogrammklasse und generieren Sie damit Ihre Hashcodes.

Sam Barnum
quelle
Ich wollte das sagen. Während die anderen Antworten die Frage beantworten, ist das Schreiben einer separaten hashCode-Funktion wahrscheinlich die geeignete Lösung für das Problem von knorv.
Nick
1

Der Hashcode wird basierend auf den ASCII-Werten der Zeichen in der Zeichenfolge berechnet.

Dies ist die Implementierung in der String-Klasse wie folgt

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                              : StringUTF16.hashCode(value);
    }
    return h;
}

Kollisionen im Hashcode sind unvermeidlich. Beispielsweise geben die Zeichenfolgen "Ea" und "FB" den gleichen Hashcode wie 2236 an

Lourdes
quelle