Warum speichert String's hashCode () nicht 0?

75

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.
Polygenschmierstoffe
quelle
6
LOL! +1 für ein schönes Beispiel für Trolling auf übergeek Weise!
Mike Nakis

Antworten:

57

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!

Kevin Bourrillion
quelle
2
Dies ist ein sehr praktisches Argument. Ist diese Art von Caching-Mechanismus aus Neugier auch anderswo üblich? Wenn für den Versuch, alle Werte zwischenzuspeichern, ein zusätzliches Flag erforderlich ist, empfiehlt es sich, nur einen Wert zu opfern, um nicht zwischengespeichert zu werden.
Polygenelubricants
2
Ich bin sicher, ich habe diesen Trick ein oder zwei Mal angewendet. Natürlich sind die Anforderungen an die String-Klasse im Vergleich zu den meisten Klassen ziemlich außergewöhnlich. Schön passender Benutzername übrigens :)
Kevin Bourrillion
20
Ja, ich war in letzter Zeit ziemlich besessen von String's hashCode (), wie mein Benutzername zeigt. Joshua Bloch sagte im Google Tech Talk-Video vom 23. Juli 2007, dass er in 10 Minuten "Polygen-Schmierstoffe" unter (200.000) ^ 2 Wortpaaren gefunden habe. Ich habe die Eigenschaften der Hash-Funktion genutzt, um dies in wenigen Sekunden in O (N) zu tun. Die folgende Zeichenfolge hasst beispielsweise auch MIN_VALUE: "And so my fellow mismanagements: ask not what your newsdealer can sugarcoat for you -- ask what you can sugarcoat for your newsdealer."
Polygenelubricants
6
Wenn die Zeichenfolgen von Benutzern stammen, liegt die Wahrscheinlichkeit nahe bei 1. Sie wissen, dass jemand es versuchen wird.
Antimon
1
Ich denke, es kann sich für Polygenelubricants lohnen, da Server länger
brauchen
24

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 .

Jon Skeet
quelle
Ich habe gerade ein Best-Practice-Tag und eine vierte Frage hinzugefügt, um dies mehr zu einer Designfrage zu machen. Sollte es so sein? Sollte eine Wahrscheinlichkeit ungleich Null, O (n) zu speichern, jedes Mal funktionieren, wenn die Methode aufgerufen wird (und es wird viel genannt, da Strings und hashCode () solche grundlegenden Teile von Java sind), um zusätzlichen O (1) -Speicherplatz zu rechtfertigen? Oder ist es tatsächlich eine bewährte Methode, im Allgemeinen nur alle bis auf einen Wert zwischenzuspeichern, anstatt ein Flag zu haben?
Polygenelubricants
1
@ Stephen C: Das setzt einen perfekt verteilten Hash voraus. Ich weiß nicht, ob dies bei dem von String verwendeten der Fall ist.
Jon Skeet
1
"Ich erwarte nicht viele Strings Hash auf 0". Nun, es sei denn, die Saiten wurden absichtlich ausgewählt.
Tom Hawtin - Tackline
1
"Nun, nicht, wenn die Zeichenfolgen nicht absichtlich ausgewählt wurden." Nun ", ist wahrscheinlich die häufigste Zeichenfolge in der Java-Welt (wer weiß sogar, wie viele Zeichenfolgen" "aktiviert und nie geändert wurden, oder?) Und" .hashCode () ist 0. Ich kann nicht viele Anwendungsfälle für die Verwendung von "" als Kartenschlüssel sehen, aber ich bin mir sicher, dass dies passiert, daher ist dies wahrscheinlich unverhältnismäßig teuer. Das heißt, "" .hashCode () führt im Grunde nur eine Schleife von 0 bis 0 aus, also denke ich nicht, dass es genau langsam sein wird ... und selbst wenn es so wäre, wen interessiert das (siehe Kevins Antwort)
Cowan
1
@ Sergio: Ja, das tut es. "aaaaaa".hashCode()Gibt beispielsweise -1425372064 zurück.
Jon Skeet
19

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.

MB.
quelle
Sie brauchen nicht unbedingt eine Synchronisation - wie Sie bereits erwähnt haben, gibt es Dinge wie flüchtig. Während Sie in der Tat vorsichtig mit volatil sein müssen, kann man mit Sicherheit sagen, dass die Autoren der String-Klasse wahrscheinlich wissen, wie man sie richtig verwendet, oder dass sie geeignete Personen zu Rate ziehen. Ich verstehe Ihren Standpunkt ... aber ich bin immer noch nicht wirklich davon überzeugt, dass es sich überhaupt lohnt, zwischenzuspeichern, und die Speicherkosten sind immer noch für jede Zeichenfolge im System vorhanden :(
Jon Skeet
1
So wie ich es verstehe, ist flüchtig eine Form der Synchronisation, nur mit weniger Aufwand als das synchronisierte Schlüsselwort. Ich habe diesen Link cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html gefunden, der auf halbem Weg die im String-Hashcode verwendete Redewendung erklärt. Ich mag es lieber selbst - ich denke, ich werde es tatsächlich mehr verwenden :) Obwohl ich Ihren Standpunkt zur Erinnerung sehr schätze, könnte dies für einige Dinge ein Problem sein. BTW String.intern () ist ein Grund, warum die Multithread-Leistung für Strings wichtig ist - sie können von der JVM intern wiederverwendet werden.
MB.
1
Das mag ein guter Grund sein, Null als speziell zu betrachten, aber es ist kein guter Grund, eine Hash-Funktion zu haben, die einen nicht zwischenspeicherbaren Wert zurückgibt. Hätte es Schwierigkeiten gegeben, etwas in die Hash-Funktion aufzunehmen : if (computedHash != 0) return computedHash; else return «some other function»;? Selbst wenn die andere Funktion einfach die ASCII-Werte des ersten Zeichens in der Zeichenfolge plus das 991-fache der letzten Zeichen in der Zeichenfolge verwendet und 1234567890 hinzugefügt hätte, würde dies die Verteilung nicht stark beeinträchtigen.
Supercat
if (computedHash != 0) return computedHash; else return «some other function»;ist effektiv , was ist in der hashCodeFunktion, nur mit Vorsicht angewendet werden um was es geschieht , wenn von mehreren Threads aufgerufen wird . Sie können einen Blick auf die Quelle werfen. Abgesehen von Multithreading bedeutet dies nur, dass der Hash-Code bei jedem Aufruf der Funktion neu berechnet wird, wenn der berechnete Hash-Code Null ist (was ohnehin sehr unwahrscheinlich ist).
MB.
Ich stimme dem ersten Punkt zu . @supercat es hat eine ganze Weile gedauert, aber sie haben das behoben.
Eugene
8

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 .

Adamski
quelle
\ u0000 ist noch aktiv, wenn Sie eine Schnittstelle mit der neuen Datei mit nativem Code ("C: \\ CONFIG.SYS \ u0000ignored") herstellen. isFile () == true auf meinem Windows-Computer. Es ist eine Quelle aller Arten von Sicherheitsproblemen. Für die meisten Apps filtern Sie diesen Charakter!
Thomas Jung
@Thomas Jung Wenn Sie sich einen Dateipfad ansehen müssen, normalisieren Sie ihn zuerst (und Whitelist-Zeichen werden natürlich nicht auf die schwarze Liste gesetzt). Auch das hilft dir nicht gegen Symlinks.
Tom Hawtin - Tackline
1
Hinweis: Wenn Sie Nicht-NUL-Zeichen haben, muss die Zeichenfolge sechs oder sieben Zeichen lang sein, bevor sie einen Null-Hash-Code haben kann.
Tom Hawtin - Tackline
6

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."

cdunn2001
quelle
nicht mehr
Eugene
2

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.

Eugene
quelle
0
  • 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.)

Stephen C.
quelle
Ich glaube nicht, dass 1 in 2 ^ 32 richtig ist: Bei kürzeren Zeichenfolgen liegt der Hash-Code im Bereich: [0, Integer.MAX_VALUE] und bei allen Zeichenfolgen, die lang genug sind, um einen Überlauf zu verursachen, liegt der Hash-Code im Bereich: [ Integer.MIN_VALUE, Integer.MAX_VALUE]. Daher ist für zufällig erzeugte Zeichenfolgen (und unter der Annahme eines gleichmäßig verteilten Hashing-Algorithmus) die Verteilung nicht vollständig gleichmäßig; Es besteht eine höhere Wahrscheinlichkeit für einen positiven oder Null- Hash-Code als für einen negativen.
Adamski
Der hashCodeAlgorithmus verursacht ziemlich schnell einen ganzzahligen Überlauf. Adamski . Anhand einiger zufälliger Beispiele scheinen 6 Wortzeichen ausreichend zu sein - aber ich denke, Ihre Argumentation ist stichhaltig. Dies führt zu einer Verschiebung in Richtung positiver Hash-Werte (die sich verschlechtern, wenn Ihre Strings länger werden)
oxbow_lakes
Zufällig generierte Strings haben zufällige Längen sowie zufällige Zeichen.
Stephen C
@Stephen: Zufällige Längen sind mein genauer Punkt: Für eine völlig gleichmäßige Verteilung von Zeichenfolgen mit zufälliger Länge, die zufällige Zeichen enthalten, gibt es etwas mehr Zeichenfolgen, die auf> = 0 gehasht werden, da kürzere Zeichenfolgen keinen Überlauf verursachen.
Adamski
Sie haben die Option, die ich in meiner Antwort aufgeführt habe, vernachlässigt: Hinzufügen eines "if (hash == 0) hash = 1;" am Ende des Algorithmus. Auf diese Weise verlieren Sie nicht die Hälfte der normalen Hash-Werte, sondern nur einen weniger.
Jon Skeet
0

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 Koordinator
quelle
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.

Mike Liddell
quelle