Ist es sicher, Werte aus einer java.util.HashMap von mehreren Threads abzurufen (keine Änderung)?

Es gibt einen Fall, in dem eine Karte erstellt wird und nach ihrer Initialisierung nie wieder geändert wird. Der Zugriff (jedoch nur über get (Schlüssel)) erfolgt über mehrere Threads. Ist es sicher, a java.util.HashMapauf diese Weise zu verwenden?

(Derzeit verwende ich gerne a java.util.concurrent.ConcurrentHashMapund habe kein gemessenes Bedürfnis, die Leistung zu verbessern, bin aber einfach neugierig, ob ein einfaches HashMapausreichen würde. Daher lautet diese Frage weder "Welches soll ich verwenden?" Noch eine Leistungsfrage. Die Frage ist vielmehr "Wäre es sicher?")

Ihr Idiom ist sicher , wenn und nur wenn der Verweis auf das HashMapist sicher veröffentlicht . Die sichere Veröffentlichung befasst sich nicht mit den Interna von sich HashMapselbst, sondern damit, wie der Konstruktions-Thread den Verweis auf die Karte für andere Threads sichtbar macht.

Grundsätzlich besteht hier der einzig mögliche Wettlauf zwischen dem Aufbau des HashMapund aller Lesethreads, die darauf zugreifen können, bevor er vollständig aufgebaut ist. In den meisten Diskussionen geht es darum, was mit dem Status des Kartenobjekts geschieht. Dies ist jedoch irrelevant, da Sie es nie ändern. Der einzig interessante Teil ist daher, wie die HashMapReferenz veröffentlicht wird.

Stellen Sie sich zum Beispiel vor, Sie veröffentlichen die Karte folgendermaßen:

class SomeClass {
   public static HashMap<Object, Object> MAP;

   public synchronized static setMap(HashMap<Object, Object> m) {
     MAP = m;
   }
}

... und wird irgendwann setMap()mit einer Karte aufgerufen, und andere Threads verwenden, SomeClass.MAPum auf die Karte zuzugreifen, und suchen wie folgt nach Null:

HashMap<Object,Object> map = SomeClass.MAP;
if (map != null) {
  .. use the map
} else {
  .. some default behavior
}

Dies ist nicht sicher , obwohl es wahrscheinlich so aussieht, als ob es so wäre. Das Problem ist , dass es keine geschieht vor- Beziehung zwischen dem Satz SomeObject.MAPund der nachfolgenden Leseoperation auf einem anderen Thread, so dass der Lesefaden frei , um zu sehen eine teilweise konstruierten Karte ist. Dies kann so ziemlich alles und sogar in der Praxis Dinge tun , wie den Lesethread in eine Endlosschleife zu bringen .

Um sicher die Karte zu veröffentlichen, müssen Sie etablieren ein geschieht zuvor Beziehung zwischen dem Schreiben des Referenz auf die HashMap(dh der Veröffentlichung ) und die nachfolgenden Leser dieser Verweisung (dh der Verbrauch). Praktischerweise gibt es nur wenige leicht zu merkende Weise zu erreichen , dass ^[1] :

1. Tauschen Sie die Referenz über ein ordnungsgemäß gesperrtes Feld aus ( JLS 17.4.5 ).
2. Verwenden Sie den statischen Initialisierer, um die Speicher zu initialisieren ( JLS 12.4 ).
3. Tauschen Sie die Referenz über ein flüchtiges Feld ( JLS 17.4.5 ) oder als Folge dieser Regel über die AtomicX-Klassen aus
4. Initialisieren Sie den Wert in ein letztes Feld ( JLS 17.5 ).

Die für Ihr Szenario interessantesten sind (2), (3) und (4). Insbesondere gilt (3) direkt für den Code, den ich oben habe: Wenn Sie die Deklaration von MAPin transformieren :

public static volatile HashMap<Object, Object> MAP;

dann ist alles koscher: Leser , die einen sehen Nicht-Null - Wert unbedingt eine zuvor passiert Beziehung mit dem Laden MAPalle Geschäfte und damit mit der Karte Initialisierung zugeordnet sind .

Die anderen Methoden ändern die Semantik Ihrer Methode, da sowohl (2) (mit dem statischen Initializer) als auch (4) (mit final ) implizieren, dass Sie MAPzur Laufzeit nicht dynamisch festlegen können . Wenn Sie dies nicht tun müssen , deklarieren Sie es einfach MAPals static final HashMap<>und Sie erhalten eine sichere Veröffentlichung.

In der Praxis sind die Regeln für den sicheren Zugriff auf "nie geänderte Objekte" einfach:

Wenn Sie ein Objekt veröffentlichen, das nicht von Natur aus unveränderlich ist (wie in allen deklarierten Feldern final) und:

• Sie können bereits das Objekt erstellen, das zum Zeitpunkt der Deklaration zugewiesen wird. ^A : Verwenden Sie einfach ein finalFeld (auch static finalfür statische Elemente).
• Sie möchten das Objekt später zuordnen, nachdem die Referenz bereits sichtbar ist: ein flüchtiges Feld verwenden , ^b .

Das ist es!

In der Praxis ist es sehr effizient. Die Verwendung eines static finalFelds ermöglicht es der JVM beispielsweise, anzunehmen, dass der Wert für die Lebensdauer des Programms unverändert bleibt, und ihn stark zu optimieren. Die Verwendung eines finalMitgliedes Feld ermöglicht die meisten Architekturen , das Feld auf eine Weise äquivalent zu einem normalen Lesefeld zu lesen und nicht hemmt weitere Optimierungen ^c .

Schließlich hat die Verwendung von volatileeinige Auswirkungen: Auf vielen Architekturen (z. B. x86, insbesondere solchen, bei denen Lesevorgänge keine Lesevorgänge zulassen) ist keine Hardwarebarriere erforderlich, aber einige Optimierungen und Neuordnungen treten möglicherweise beim Kompilieren nicht auf - dies jedoch Effekt ist im Allgemeinen gering. Im Gegenzug erhalten Sie tatsächlich mehr als gewünscht HashMap- Sie können nicht nur eine sicher veröffentlichen , sondern auch so viele nicht geänderte HashMaps speichern, wie Sie möchten, und sicher sein, dass alle Leser eine sicher veröffentlichte Karte sehen .

Weitere Informationen finden Sie in Shipilev oder in diesen FAQ von Manson und Goetz .

[1] Direkt aus dem Schiff zitieren .

^a Das klingt kompliziert, aber ich meine, Sie können die Referenz zur Konstruktionszeit zuweisen - entweder am Deklarationspunkt oder im Konstruktor (Elementfelder) oder statischen Initialisierer (statische Felder).

^b Optional können Sie eine synchronizedMethode zum Abrufen / Festlegen oder eine AtomicReferenceoder etwas verwenden, aber wir sprechen über die Mindestarbeit, die Sie leisten können.

c Einige Architekturen mit sehr schwachen Speichermodellen (ich sehe Sie an , Alpha) erfordern möglicherweise eine Art Lesebarriere vor dem finalLesen - aber diese sind heute sehr selten.

Jeremy Manson, der Gott, wenn es um das Java-Speichermodell geht, hat einen dreiteiligen Blog zu diesem Thema - weil Sie im Wesentlichen die Frage "Ist es sicher, auf eine unveränderliche HashMap zuzugreifen" stellen - die Antwort darauf lautet ja. Aber Sie müssen das Prädikat auf die Frage beantworten: "Ist meine HashMap unveränderlich?". Die Antwort könnte Sie überraschen - Java verfügt über ein relativ kompliziertes Regelwerk zur Bestimmung der Unveränderlichkeit.

Weitere Informationen zum Thema finden Sie in Jeremys Blog-Beiträgen:

Teil 1 zur Unveränderlichkeit in Java: http://jeremymanson.blogspot.com/2008/04/immutability-in-java.html

Teil 2 zur Unveränderlichkeit in Java: http://jeremymanson.blogspot.com/2008/07/immutability-in-java-part-2.html

Teil 3 zur Unveränderlichkeit in Java: http://jeremymanson.blogspot.com/2008/07/immutability-in-java-part-3.html

Die Lesevorgänge sind unter dem Gesichtspunkt der Synchronisation sicher, jedoch nicht unter dem Gesichtspunkt des Speichers. Dies wird von Java-Entwicklern, einschließlich hier auf Stackoverflow, weitgehend missverstanden. (Beachten Sie die Bewertung dieser Antwort als Beweis.)

Wenn andere Threads ausgeführt werden, wird möglicherweise keine aktualisierte Kopie der HashMap angezeigt, wenn aus dem aktuellen Thread kein Speicher geschrieben wird. Speicherschreibvorgänge erfolgen durch die Verwendung synchronisierter oder flüchtiger Schlüsselwörter oder durch die Verwendung einiger Java-Parallelitätskonstrukte.

Weitere Informationen finden Sie in Brian Goetz 'Artikel über das neue Java-Speichermodell .

Nach einigem Hin und Her fand ich dies im Java-Dokument (Hervorhebung von mir):

Beachten Sie, dass diese Implementierung nicht synchronisiert ist. Wenn mehrere Threads gleichzeitig auf eine Hash-Map zugreifen und mindestens einer der Threads die Map strukturell ändert, muss sie extern synchronisiert werden. (Eine strukturelle Änderung ist eine Operation, die eine oder mehrere Zuordnungen hinzufügt oder löscht. Das bloße Ändern des Werts eines Schlüssels, den eine Instanz bereits enthält, ist keine strukturelle Änderung.)

Dies scheint zu implizieren, dass es sicher sein wird, vorausgesetzt, die Umkehrung der Aussage dort ist wahr.

Ein Hinweis ist, dass unter bestimmten Umständen ein get () von einer nicht synchronisierten HashMap eine Endlosschleife verursachen kann. Dies kann auftreten, wenn ein gleichzeitiges put () ein erneutes Aufbereiten der Karte bewirkt.

http://lightbody.net/blog/2005/07/hashmapget_can_cause_an_infini.html

Es gibt jedoch eine wichtige Wendung. Es ist sicher, auf die Karte zuzugreifen, aber im Allgemeinen kann nicht garantiert werden, dass alle Threads genau den gleichen Status (und damit die gleichen Werte) der HashMap sehen. Dies kann auf Multiprozessorsystemen passieren, bei denen die Änderungen an der HashMap, die von einem Thread (z. B. demjenigen, der sie gefüllt hat) vorgenommen wurden, im Cache dieser CPU gespeichert werden können und von Threads, die auf anderen CPUs ausgeführt werden, erst dann angezeigt werden, wenn eine Speicherzaunoperation ausgeführt wird durchgeführt, um die Cache-Kohärenz sicherzustellen. Die Java-Sprachspezifikation ist in diesem Fall explizit: Die Lösung besteht darin, eine Sperre (synchronisiert (...)) zu erwerben, die eine Speicherzaunoperation ausgibt. Wenn Sie also sicher sind, dass nach dem Auffüllen der HashMap jeder Thread eine beliebige Sperre erhält, ist es von diesem Punkt an in Ordnung, von einem beliebigen Thread aus auf die HashMap zuzugreifen, bis die HashMap erneut geändert wird.

Laut http://www.ibm.com/developerworks/java/library/j-jtp03304/ # Initialisierungssicherheit können Sie Ihre HashMap zu einem endgültigen Feld machen und sie nach Abschluss des Konstruktors sicher veröffentlichen.

... Unter dem neuen Speichermodell gibt es etwas Ähnliches wie eine Vorher-Beziehung zwischen dem Schreiben eines letzten Felds in einem Konstruktor und dem anfänglichen Laden eines gemeinsamen Verweises auf dieses Objekt in einem anderen Thread. ...

Das von Ihnen beschriebene Szenario besteht also darin, dass Sie eine Reihe von Daten in eine Karte einfügen müssen. Wenn Sie mit dem Auffüllen fertig sind, behandeln Sie sie als unveränderlich. Ein Ansatz, der "sicher" ist (dh Sie erzwingen, dass er wirklich als unveränderlich behandelt wird), besteht darin, die Referenz durch zu ersetzen, Collections.unmodifiableMap(originalMap)wenn Sie bereit sind, sie unveränderlich zu machen.

Ein Beispiel dafür, wie schlecht Karten bei gleichzeitiger Verwendung fehlschlagen können, und die von mir erwähnte vorgeschlagene Problemumgehung finden Sie in diesem Eintrag zur Fehlerparade : bug_id = 6423457

Diese Frage wird in Brian Goetz 'Buch "Java Concurrency in Practice" (Listing 16.8, Seite 350) behandelt:

@ThreadSafe
public class SafeStates {
    private final Map<String, String> states;

    public SafeStates() {
        states = new HashMap<String, String>();
        states.put("alaska", "AK");
        states.put("alabama", "AL");
        ...
        states.put("wyoming", "WY");
    }

    public String getAbbreviation(String s) {
        return states.get(s);
    }
}

Da statesals deklariert wird finalund seine Initialisierung im Klassenkonstruktor des Besitzers erfolgt, wird jedem Thread, der diese Map später liest, garantiert, dass sie zum Zeitpunkt des Abschlusses des Konstruktors angezeigt wird, vorausgesetzt, kein anderer Thread versucht, den Inhalt der Map zu ändern.

Seien Sie gewarnt, dass das Ersetzen einer ConcurrentHashMap durch eine HashMap selbst in Single-Thread-Code möglicherweise nicht sicher ist. ConcurrentHashMap verbietet null als Schlüssel oder Wert. HashMap verbietet sie nicht (nicht fragen).

In der unwahrscheinlichen Situation, dass Ihr vorhandener Code der Sammlung während des Setups eine Null hinzufügt (vermutlich in einem Fehlerfall), ändert das Ersetzen der Sammlung wie beschrieben das Funktionsverhalten.

Vorausgesetzt, Sie tun nichts anderes, sind gleichzeitige Lesevorgänge von einer HashMap sicher.

[Bearbeiten: Mit "gleichzeitigen Lesevorgängen" meine ich, dass es nicht auch gleichzeitige Änderungen gibt.

Andere Antworten erklären, wie dies sichergestellt werden kann. Eine Möglichkeit besteht darin, die Karte unveränderlich zu machen, dies ist jedoch nicht erforderlich. Beispielsweise definiert das JSR133-Speichermodell das Starten eines Threads explizit als synchronisierte Aktion, was bedeutet, dass Änderungen, die in Thread A vor dem Start von Thread B vorgenommen wurden, in Thread B sichtbar sind.

Ich möchte diesen detaillierteren Antworten zum Java-Speichermodell nicht widersprechen. Diese Antwort soll darauf hinweisen, dass es neben Nebenläufigkeitsproblemen mindestens einen API-Unterschied zwischen ConcurrentHashMap und HashMap gibt, der sogar ein Single-Thread-Programm, das eines durch das andere ersetzt, zunichte machen könnte.]

http://www.docjar.com/html/api/java/util/HashMap.java.html

Hier ist die Quelle für HashMap. Wie Sie sehen, gibt es dort absolut keinen Sperr- / Mutex-Code.

Dies bedeutet, dass es zwar in einer Multithread-Situation in Ordnung ist, aus einer HashMap zu lesen, ich aber definitiv eine ConcurrentHashMap verwenden würde, wenn es mehrere Schreibvorgänge gäbe.

Interessant ist, dass sowohl .NET HashTable als auch Dictionary <K, V> Synchronisationscode integriert haben.

Wenn die Initialisierung und jeder Put synchronisiert sind, sind Sie gespeichert.

Der folgende Code wird gespeichert, da sich der Klassenladeprogramm um die Synchronisierung kümmert:

public static final HashMap<String, String> map = new HashMap<>();
static {
  map.put("A","A");

}

Der folgende Code wird gespeichert, da das Schreiben von flüchtig die Synchronisation übernimmt.

class Foo {
  volatile HashMap<String, String> map;
  public void init() {
    final HashMap<String, String> tmp = new HashMap<>();
    tmp.put("A","A");
    // writing to volatile has to be after the modification of the map
    this.map = tmp;
  }
}

Dies funktioniert auch, wenn die Mitgliedsvariable final ist, da final ebenfalls volatil ist. Und wenn die Methode ein Konstruktor ist.