Warum speichert String's hashCode () nicht 0?

Ich habe im Java 6-Quellcode für String festgestellt, dass hashCode nur andere Werte als 0 zwischenspeichert. Der Leistungsunterschied wird durch das folgende Snippet gezeigt:

public class Main{
   static void test(String s) {
      long start = System.currentTimeMillis();
      for (int i = 0; i < 10000000; i++) {
         s.hashCode();
      }
      System.out.format("Took %d ms.%n", System.currentTimeMillis() - start);
   }
   public static void main(String[] args) {
      String z = "Allocator redistricts; strict allocator redistricts strictly.";
      test(z);
      test(z.toUpperCase());
   }
}

Wenn Sie dies in ideone.com ausführen, erhalten Sie die folgende Ausgabe:

Took 1470 ms.
Took 58 ms.

Meine Fragen sind also:

• Warum speichert String's hashCode () nicht 0?
• Wie groß ist die Wahrscheinlichkeit, dass ein Java-String auf 0 gehasht wird?
• Was ist der beste Weg, um den Leistungsverlust zu vermeiden, wenn der Hash-Wert jedes Mal für Zeichenfolgen neu berechnet wird, deren Hash auf 0 gesetzt ist?
• Ist dies die bewährte Methode zum Zwischenspeichern von Werten? (dh alle außer einem zwischenspeichern?)

Zu Ihrer Unterhaltung ist jede Zeile hier eine Zeichenfolge mit dem Hash 0:

pollinating sandboxes
amusement & hemophilias
schoolworks = perversive
electrolysissweeteners.net
constitutionalunstableness.net
grinnerslaphappier.org
BLEACHINGFEMININELY.NET
WWW.BUMRACEGOERS.ORG
WWW.RACCOONPRUDENTIALS.NET
Microcomputers: the unredeemed lollipop...
Incentively, my dear, I don't tessellate a derangement.
A person who never yodelled an apology, never preened vocalizing transsexuals.

Du machst dir um nichts Sorgen. Hier ist eine Möglichkeit, über dieses Problem nachzudenken.

Angenommen, Sie haben eine Anwendung, die nichts anderes tut, als das ganze Jahr über Hashing-Strings herumzusitzen. Nehmen wir an, es werden tausend Zeichenfolgen benötigt, die sich alle im Speicher befinden. Sie rufen hashCode () wiederholt millionenfach im Round-Robin-Verfahren auf, erhalten dann weitere tausend neue Zeichenfolgen und wiederholen dies.

Nehmen wir an, dass die Wahrscheinlichkeit, dass der Hash-Code eines Strings Null ist, tatsächlich viel größer als 1/2 ^ 32 ist. Ich bin sicher, es ist etwas größer als 1/2 ^ 32, aber sagen wir, es ist viel schlimmer als das, wie 1/2 ^ 16 (die Quadratwurzel! Jetzt ist das viel schlimmer!).

In dieser Situation können Sie mehr von den Ingenieuren von Oracle profitieren, die die Zwischenspeicherung der Hash-Codes dieser Zeichenfolgen verbessern, als von allen anderen Lebenden. Also schreibst du ihnen und bittest sie, das Problem zu beheben. Und sie arbeiten ihre Magie so, dass immer wenn s.hashCode () Null ist, es sofort zurückkehrt (sogar beim ersten Mal! Eine 100% ige Verbesserung!). Nehmen wir an, sie tun dies, ohne die Leistung in einem anderen Fall zu beeinträchtigen.

Hurra! Jetzt ist Ihre App ... mal sehen ... 0,0015% schneller!

Was früher einen ganzen Tag dauerte, dauert jetzt nur noch 23 Stunden, 57 Minuten und 48 Sekunden!

Und denken Sie daran, wir haben das Szenario so eingerichtet, dass jeder mögliche Nutzen aus dem Zweifel gezogen wird, oft in einem lächerlichen Ausmaß.

Scheint Ihnen das wert zu sein?

BEARBEITEN: Seit ich dies vor ein paar Stunden gepostet habe, habe ich einen meiner Prozessoren wild laufen lassen, um nach Zwei-Wort-Phrasen mit null Hash-Codes zu suchen. Bisher hat es sich ausgedacht: Vermirtle Zorillo, Chronogrammic Schtoff, Contusive Cloisterlike, Creashaks Organzine, Drumwood Boulderhead, elektroanalytisch trainierbar und favosely nicht konstruierbar. Dies ist aus ungefähr 2 ^ 35 Möglichkeiten heraus, so dass wir bei perfekter Verteilung erwarten würden, nur 8 zu sehen. Wenn es fertig ist, werden wir ein paar Mal so viele haben, aber nicht ausgefallen mehr. Wichtiger ist, dass ich mir jetzt ein paar interessante Bandnamen / Albumnamen ausgedacht habe! Kein fairer Diebstahl!

Es verwendet 0, um anzuzeigen, dass der Hashcode noch nicht ausgearbeitet wurde. Die Alternative wäre die Verwendung eines separaten Booleschen Flags, das mehr Speicherplatz beanspruchen würde. (Oder natürlich, um den Hashcode überhaupt nicht zwischenzuspeichern.)

Ich erwarte nicht viele Strings Hash auf 0; Es wäre wohl sinnvoll, wenn die Hashing-Routine absichtlich 0 vermeiden würde (z. B. einen Hash von 0 in 1 übersetzen und diesen zwischenspeichern). Das würde die Kollisionen erhöhen, aber ein erneutes Aufwärmen vermeiden. Dafür ist es jetzt jedoch zu spät, da der String-HashCode-Algorithmus explizit dokumentiert ist.

Ob dies im Allgemeinen eine gute Idee ist: Es ist ein sicherlich effizienter Caching-Mechanismus und könnte (siehe Bearbeiten) mit einer Änderung sogar noch besser sein, um ein erneutes Aufbereiten von Werten zu vermeiden, die mit einem Hash von 0 enden. Persönlich wäre ich interessiert zu sehen Die Daten, die Sun zu der Annahme veranlassten, dass es sich überhaupt gelohnt hat, dies zu tun - sie belegen zusätzliche 4 Bytes für jede jemals erstellte Zeichenfolge, unabhängig davon, wie oft oder selten sie gehasht wird, und der einzige Vorteil besteht für Zeichenfolgen, die mehr als einmal gehasht werden .

BEARBEITEN: Wie KevinB in einem Kommentar an anderer Stelle ausführt, kann der obige Vorschlag "0 vermeiden" durchaus Nettokosten verursachen, da er in einem sehr seltenen Fall hilfreich ist, jedoch für jede Hash-Berechnung einen zusätzlichen Vergleich erfordert .

Ich denke, es gibt etwas Wichtiges, dass die anderen Antworten bisher fehlen: Der Nullwert existiert, so dass der HashCode-Caching-Mechanismus in einer Multithread-Umgebung robust funktioniert.

Wenn Sie zwei Variablen hätten, wie cachedHashCode selbst und einen isHashCodeCalculated-Booleschen Wert, um anzugeben, ob cachedHashCode berechnet wurde, benötigen Sie eine Thread-Synchronisierung, damit die Dinge in einer Multithread-Umgebung funktionieren. Und die Synchronisation wäre schlecht für die Leistung, insbesondere da Strings sehr häufig in mehreren Threads wiederverwendet werden.

Mein Verständnis des Java-Speichermodells ist etwas lückenhaft, aber hier ist ungefähr, was los ist:

1. Wenn mehrere Threads auf eine Variable zugreifen (wie der zwischengespeicherte Hashcode), gibt es keine Garantie dafür, dass jeder Thread den neuesten Wert sieht. Wenn eine Variable mit Null beginnt, aktualisiert A sie (setzt sie auf einen Wert ungleich Null), und Thread B liest sie kurz danach. Thread B könnte immer noch den Nullwert sehen.

2. Es gibt ein weiteres Problem beim Zugriff auf gemeinsam genutzte Werte aus mehreren Threads (ohne Synchronisierung): Möglicherweise versuchen Sie, ein Objekt zu verwenden, das nur teilweise initialisiert wurde (das Erstellen eines Objekts ist kein atomarer Prozess). Multithread-Lese- und Schreibvorgänge von 64-Bit-Grundelementen wie Longs und Doubles sind ebenfalls nicht unbedingt atomar. Wenn also zwei Threads versuchen, den Wert eines Long- oder eines Double-Threads zu lesen und zu ändern, kann ein Thread etwas Seltsames und Teilweise sehen . Oder so ähnlich sowieso. Es gibt ähnliche Probleme, wenn Sie versuchen, zwei Variablen zusammen zu verwenden, z. B. cachedHashCode und isHashCodeCalculated. Ein Thread kann leicht die neueste Version einer dieser Variablen anzeigen, aber eine ältere Version einer anderen.

3. Der übliche Weg, um diese Multithreading-Probleme zu umgehen, ist die Verwendung der Synchronisation. Sie können beispielsweise den gesamten Zugriff auf den zwischengespeicherten Hashcode in einen synchronisierten Block einfügen oder das Schlüsselwort volatile verwenden (obwohl Sie damit vorsichtig sein sollten, da die Semantik etwas verwirrend ist).

4. Die Synchronisation verlangsamt jedoch die Arbeit. Schlechte Idee für so etwas wie einen String hashCode. Zeichenfolgen werden in HashMaps sehr häufig als Schlüssel verwendet. Daher benötigen Sie die hashCode-Methode, um eine gute Leistung zu erzielen, auch in Umgebungen mit mehreren Threads.

5. Java-Grundelemente mit 32 Bit oder weniger wie int sind etwas Besonderes. Im Gegensatz zu beispielsweise einem langen Wert (64-Bit-Wert) können Sie sicher sein, dass Sie niemals einen teilweise initialisierten Wert eines int (32 Bit) lesen. Wenn Sie ein int ohne Synchronisation lesen, können Sie nicht sicher sein, dass Sie den neuesten eingestellten Wert erhalten, aber Sie können sicher sein, dass der Wert, den Sie erhalten, ein Wert ist, der zu einem bestimmten Zeitpunkt von Ihrem Thread oder explizit festgelegt wurde ein anderer Thread.

Der HashCode-Caching-Mechanismus in java.lang.String ist so eingerichtet, dass er sich auf Punkt 5 oben stützt. Sie können es besser verstehen, wenn Sie sich die Quelle von java.lang.String.hashCode () ansehen. Wenn mehrere Threads gleichzeitig hashCode aufrufen, wird hashCode möglicherweise mehrmals berechnet (entweder wenn der berechnete Wert Null ist oder wenn mehrere Threads hashCode gleichzeitig aufrufen und beide einen zwischengespeicherten Wert von Null sehen), aber Sie können sicher sein, dass hashCode () gibt immer den gleichen Wert zurück. Es ist also robust und auch performant (da es keine Synchronisation gibt, die in Umgebungen mit mehreren Threads als Engpass fungiert).

Wie gesagt, mein Verständnis des Java-Speichermodells ist ein wenig lückenhaft, aber ich bin mir ziemlich sicher, dass ich den Kern des oben genannten richtig verstanden habe. Letztendlich ist es eine sehr clevere Redewendung zum Zwischenspeichern des HashCodes ohne den Aufwand der Synchronisation.

0 wird nicht zwischengespeichert, da die Implementierung einen zwischengespeicherten Wert von 0 als "zwischengespeicherten Wert noch nicht initialisiert" interpretiert. Die Alternative wäre gewesen, a zu verwenden java.lang.Integer, wobei null impliziert, dass der Wert noch nicht zwischengespeichert wurde. Dies hätte jedoch einen zusätzlichen Speicheraufwand bedeutet.

In Bezug auf die Wahrscheinlichkeit, dass der Hash-Code eines Strings als 0 berechnet wird, würde ich sagen, dass die Wahrscheinlichkeit ziemlich gering ist und in den folgenden Fällen auftreten kann:

• Der String ist leer (obwohl die Neuberechnung dieses Hash-Codes jedes Mal effektiv O (1) ist).
• Es tritt ein Überlauf auf, bei dem der endgültig berechnete Hashcode 0 ( e.g. Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0) ist.
• Der String enthält nur das Unicode-Zeichen 0. Sehr unwahrscheinlich, da dies ein Steuerzeichen ohne Bedeutung ist, außer in der "Papierbandwelt" (!):

Aus Wikipedia :

Code 0 (ASCII-Codename NUL) ist ein Sonderfall. Bei Papierbändern ist dies der Fall, wenn keine Löcher vorhanden sind. Es ist zweckmäßig, dies als Füllzeichen zu behandeln, ohne etwas anderes zu bedeuten .

Dies stellt sich als gute Frage im Zusammenhang mit einer Sicherheitslücke heraus .

"Beim Hashing eines Strings speichert Java auch den Hash-Wert im Hash-Attribut zwischen, jedoch nur, wenn das Ergebnis von Null abweicht. Daher ist der Zielwert Null für einen Angreifer besonders interessant, da er das Caching verhindert und ein erneutes Hashing erzwingt."

Zehn Jahre später haben sich die Dinge geändert. Ich kann das ehrlich gesagt nicht glauben (aber der Geek in mir ist extrem glücklich).

Wie Sie bemerkt haben, gibt es Chancen, wo einige String::hashCodefür einige Saiten sind zeround dies war nicht im Cache gespeichert (wird dazu kommen). Viele Leute argumentierten (auch in diesem Q & A), warum es kein zusätzliches Feld gab java.lang.String, so etwas wie: hashAlreadyComputedund verwenden Sie das einfach. Das Problem liegt auf der Hand: zusätzlicher Speicherplatz für jede einzelne String-Instanz. Es gibt übrigens einen Grund, der java-9 eingeführt compact Stringwurde, weil viele Benchmarks gezeigt haben, dass dies in den meisten Anwendungen eine eher ( über- ) verwendete Klasse ist. Mehr Platz hinzufügen ? Die Entscheidung war: nein. Vor allem , da die kleinste mögliche Ergänzung gewesen wäre 1 byte, nicht 1 bit(für 32 bit JMVs, würde der zusätzliche Platz gewesen8 bytes : 1 für die Flagge, 7 für die Ausrichtung).

Also, Compact Strings kam herein java-9, und wenn Sie genau hinschauen (oder sich darum kümmern), werden sie taten in ein Feld hinzufügen java.lang.String: coder. Habe ich nicht einfach dagegen gestritten? Es ist nicht so leicht. Es scheint, dass die Bedeutung kompakter Zeichenfolgen das Argument "zusätzlicher Platz" überwogen hat. Es ist auch wichtig zu sagen, dass zusätzlicher Platz 32 bits VMnur für wichtig ist (weil es keine Lücke in der Ausrichtung gab). Im Gegensatz dazu ist im jdk-8Layout von java.lang.String:

java.lang.String object internals:
 OFFSET  SIZE     TYPE DESCRIPTION                           VALUE
  0    12          (object header)                           N/A
 12     4   char[] String.value                              N/A
 16     4      int String.hash                               N/A
 20     4          (loss due to the next object alignment)
 Instance size: 24 bytes
 Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

Beachten Sie genau dort eine wichtige Sache:

Space losses : ... 4 bytes total.

Da jedes Java-Objekt ausgerichtet ist (wie stark es von der JVM und einigen Startflags abhängt, wie UseCompressedOopszum Beispiel), Stringgibt es eine Lücke 4 bytes, die nicht verwendet wird. Beim Hinzufügen coderdauerte es einfach 1 byte ohne zusätzlichen Speicherplatz hinzuzufügen. Als solche nach Compact String s hinzugefügt wurden, hat das Layout geändert:

java.lang.String object internals:
 OFFSET  SIZE     TYPE DESCRIPTION                           VALUE
  0    12          (object header)                           N/A
 12     4   byte[] String.value                              N/A
 16     4      int String.hash                               N/A
 20     1     byte String.coder                              N/A
 21     3          (loss due to the next object alignment)
 Instance size: 24 bytes
 Space losses: 0 bytes internal + 3 bytes external = 3 bytes total

coderisst 1 byteund die Lücke wurde geschrumpft3 bytes . Der "Schaden" wurde also schon in angerichtet jdk-9. Denn 32 bits JVMes gab eine Zunahme mit 8 bytes : 1 coder + 7 gapund für 64 bit JVM- es gab keine Zunahme, coderdie etwas Platz von der Lücke einnahm.

Und jetzt in jdk-13 sie beschlossen, das zu nutzen gap, da es sowieso existiert. Ich möchte Sie nur daran erinnern, dass die Wahrscheinlichkeit, einen String mit null Hashcode zu haben, 1 zu 4 Milliarden beträgt. Es gibt immer noch Leute, die sagen: na und? Lass uns das beheben! Voilá: jdk-13Layout von java.lang.String:

java.lang.String object internals:
OFFSET  SIZE      TYPE DESCRIPTION                            VALUE
  0    12           (object header)                           N/A
 12     4    byte[] String.value                              N/A
 16     4       int String.hash                               N/A
 20     1      byte String.coder                              N/A
 21     1   boolean String.hashIsZero                         N/A
 22     2           (loss due to the next object alignment)
 Instance size: 24 bytes
 Space losses: 0 bytes internal + 2 bytes external = 2 bytes total

Und hier ist es : boolean String.hashIsZero. Und hier ist es in der Codebasis:

public int hashCode() {
    int h = hash;
    if (h == 0 && !hashIsZero) {
        h = isLatin1() ? StringLatin1.hashCode(value)
                       : StringUTF16.hashCode(value);
        if (h == 0) {
            hashIsZero = true;
        } else {
            hash = h;
        }
    }
    return h;
}

Warten! h == 0 und hashIsZero Feld? Sollte das nicht so heißen wie : hashAlreadyComputed? Warum ist die Implementierung nicht so:

    @Override
    public int hashCode(){
        if(!hashCodeComputed){
            // or any other sane computation
            hash = 42;
            hashCodeComputed = true;
        }

        return hash;
    }

Auch wenn ich den Kommentar unter dem Quellcode gelesen habe:

    // The hash or hashIsZero fields are subject to a benign data race,
    // making it crucial to ensure that any observable result of the
    // calculation in this method stays correct under any possible read of
    // these fields. Necessary restrictions to allow this to be correct
    // without explicit memory fences or similar concurrency primitives is
    // that we can ever only write to one of these two fields for a given
    // String instance, and that the computation is idempotent and derived
    // from immutable state

Es ist nur sinnvoll , nachdem ich gelesen dies . Ziemlich knifflig, aber dies schreibt man nach dem anderen, viel mehr Details in der obigen Diskussion.

• Warum speichert String's hashCode () nicht 0?

Der Wert Null ist reserviert und bedeutet "der Hash-Code wird nicht zwischengespeichert".

• Wie groß ist die Wahrscheinlichkeit, dass ein Java-String auf 0 gehasht wird?

Laut Javadoc lautet die Formel für den Hashcode eines Strings:

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

mit intArithmetik, wobei s[i]das i-te Zeichen der Zeichenfolge und istn die Länge der Zeichenfolge ist. (Der Hash des leeren Strings wird als Sonderfall als Null definiert.)

Meine Intuition ist, dass die Hashcode-Funktion wie oben eine gleichmäßige Verteilung der String-Hash-Werte über den Wertebereich intergibt. Eine gleichmäßige Streuung, die bedeuten würde, dass die Wahrscheinlichkeit eines zufällig generierten String-Hashing auf Null 1 zu 2 ^ 32 betrug.

• Was ist der beste Weg, um den Leistungsverlust zu vermeiden, wenn der Hash-Wert jedes Mal für Zeichenfolgen neu berechnet wird, deren Hash auf 0 gesetzt ist?

Die beste Strategie ist, das Problem zu ignorieren. Wenn Sie wiederholt denselben String-Wert hashen, hat Ihr Algorithmus etwas Seltsames.

• Ist dies die bewährte Methode zum Zwischenspeichern von Werten? (dh alle außer einem zwischenspeichern?)

Dies ist ein Kompromiss zwischen Raum und Zeit. AFAIK, die Alternativen sind:

• Fügen Sie cachedjedem String-Objekt ein Flag hinzu, sodass jeder Java-String ein zusätzliches Wort enthält.

• Verwenden Sie das oberste Bit des hashElements als zwischengespeicherte Flagge. Auf diese Weise können Sie alle Hash-Werte zwischenspeichern, aber Sie haben nur halb so viele mögliche String-Hash-Werte.

• Zwischenspeichern Sie Hashcodes überhaupt nicht in Strings.

Ich denke, dass die Java-Designer den richtigen Aufruf für Strings gemacht haben, und ich bin sicher, dass sie umfangreiche Profile erstellt haben, die die Richtigkeit ihrer Entscheidung bestätigen. Es ist jedoch nicht folgen , dass dies würde immer der beste Weg , um Caching zu umgehen sein.

(Beachten Sie, dass es zwei "allgemeine" Zeichenfolgenwerte gibt, die auf Null gehasht werden: die leere Zeichenfolge und die Zeichenfolge, die nur aus einem NUL-Zeichen besteht. Die Kosten für die Berechnung der Hashcodes für diese Werte sind jedoch im Vergleich zu den Kosten für die Berechnung der Werte gering Hashcode für einen typischen String-Wert.)

Nun Leute, es behält 0, denn wenn es eine Länge von Null hat, wird es sowieso als Null enden.

Und es dauert nicht lange, um herauszufinden, dass die Länge Null ist, und der Hashcode muss es auch sein.

Also, für Ihre Code-Überprüfung! Hier ist es in allem Java 8 Ruhm:

 public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

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

Wie Sie sehen können, gibt dies immer eine schnelle Null zurück, wenn die Zeichenfolge leer ist:

  if (h == 0 && value.length > 0) ...

Der Vorschlag "0 vermeiden" erscheint angemessen, um als bewährte Methode zu empfehlen, da er einem echten Problem (ernsthaft unerwartete Leistungsverschlechterung in konstruierbaren Fällen, die vom Angreifer bereitgestellt werden können) bei den geringen Kosten einer Verzweigungsoperation vor einem Schreibvorgang hilft. Es gibt einige verbleibende "unerwartete Leistungseinbußen", die ausgeübt werden können, wenn die einzigen Dinge, die in einen Satz gehen, auf den speziell angepassten Wert gehen. Dies ist jedoch im schlimmsten Fall eher eine zweifache als eine unbegrenzte Verschlechterung.

Natürlich kann die Implementierung von String nicht geändert werden, aber es besteht keine Notwendigkeit, das Problem fortzusetzen.