Czy pobieranie wartości z java.util.HashMap z wielu wątków jest bezpieczne (bez modyfikacji)?

Istnieje przypadek, w którym mapa zostanie skonstruowana i po zainicjowaniu nigdy nie zostanie ponownie zmodyfikowana. Dostęp do niego będzie jednak możliwy (tylko przez get (klucz)) z wielu wątków. Czy używanie java.util.HashMapw ten sposób jest bezpieczne ?

(Obecnie szczęśliwie używam a java.util.concurrent.ConcurrentHashMapi nie mam wymiernej potrzeby poprawy wydajności, ale jestem po prostu ciekawy, czy HashMapwystarczyłoby proste . Dlatego pytanie to nie brzmi „Którego powinienem użyć?” Ani nie jest to kwestia wydajności. Raczej pytanie brzmi: „Czy byłoby to bezpieczne?”)

Twój idiom jest bezpieczny wtedy i tylko wtedy, gdy odniesienie do HashMapjest bezpiecznie opublikowane . Zamiast czegoś odnoszącego wnętrzności HashMapsobie, bezpieczne publikacji zajmuje się jak nić budowy sprawia, że odniesienie do mapy widocznej na innych wątkach.

Zasadniczo jedyna możliwa wyścig jest tutaj między budową HashMapa wszelkimi wątkami czytającymi, które mogą uzyskać do niego dostęp, zanim zostanie w pełni skonstruowany. Większość dyskusji dotyczy tego, co dzieje się ze stanem obiektu mapy, ale nie ma to znaczenia, ponieważ nigdy go nie modyfikujesz - więc jedyną interesującą częścią jest sposób HashMappublikacji odniesienia.

Na przykład wyobraź sobie, że publikujesz mapę w ten sposób:

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

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

... iw pewnym momencie setMap()jest wywoływana z mapą, a inne wątki używają SomeClass.MAPdo uzyskania dostępu do mapy i sprawdzają wartość null w następujący sposób:

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

Nie jest to bezpieczne, chociaż prawdopodobnie wydaje się, że tak jest. Problem polega na tym, że nie ma związku między zbiorem SomeObject.MAPa kolejnym odczytem w innym wątku, więc wątek odczytu może zobaczyć częściowo skonstruowaną mapę. Może to zrobić prawie wszystko, a nawet w praktyce robi takie rzeczy, jak umieszczanie wątku odczytu w nieskończonej pętli .

Aby bezpiecznie opublikować mapę, musisz ustanowić relację zdarzają się przed zapisaniem odniesienia do HashMap(tj. Publikacji ) a późniejszymi czytelnikami tego odniesienia (tj. Konsumpcją). Dogodnie, istnieje tylko kilka łatwych do zapamiętania sposobów wykonać za które ^[1] :

1. Wymień odniesienie poprzez odpowiednio zablokowane pole ( JLS 17.4.5 )
2. Użyj statycznego inicjatora do inicjalizacji sklepów ( JLS 12.4 )
3. Zamień odniesienie przez zmienne pole ( JLS 17.4.5 ) lub w konsekwencji tej reguły za pośrednictwem klas AtomicX
4. Zainicjuj wartość w ostatnim polu ( JLS 17,5 ).

Te najbardziej interesujące dla twojego scenariusza to (2), (3) i (4). W szczególności (3) odnosi się bezpośrednio do kodu, który mam powyżej: jeśli przekształcisz deklarację MAPna:

public static volatile HashMap<Object, Object> MAP;

wtedy wszystko jest koszerne: czytelnicy, którzy widzą wartość różną od null, muszą koniecznie mieć relację „ zdarzenie przed” ze sklepem, MAPa tym samym zobaczyć wszystkie sklepy powiązane z inicjalizacją mapy.

Inne metody zmieniają semantykę twojej metody, ponieważ zarówno (2) (przy użyciu statycznego inicjatora), jak i (4) (przy użyciu final ) sugerują, że nie można ustawiać MAPdynamicznie w czasie wykonywania. Jeśli nie musisz tego robić, po prostu zadeklaruj MAPjako static final HashMap<>i masz gwarancję bezpiecznej publikacji.

W praktyce zasady bezpiecznego dostępu do „obiektów nigdy nie modyfikowanych” są proste:

Jeśli publikujesz obiekt, który nie jest z natury niezmienny (jak we wszystkich zadeklarowanych polach final) i:

• Możesz już stworzyć obiekt, który zostanie przypisany w momencie deklaracji ^a : wystarczy użyć finalpola (w tym static finaldla statycznych składowych).
• Chcesz przypisać obiekt później, gdy referencja jest już widoczna: użyj zmiennego pola ^b .

Otóż ​​to!

W praktyce jest bardzo wydajny. Na przykład użycie static finalpola pozwala JVM założyć, że wartość pozostaje niezmieniona przez cały okres istnienia programu i znacznie ją zoptymalizować. Użycie finalpola składowego umożliwia większości architektur odczytywanie pola w sposób równoważny z normalnym odczytem pola i nie hamuje dalszych optymalizacji . ^C.

Wreszcie, użycie programu volatilema pewien wpływ: na wielu architekturach (takich jak x86, szczególnie te, które nie pozwalają odczytom na przekazywanie odczytów) nie jest potrzebna bariera sprzętowa, ale pewna optymalizacja i zmiana kolejności mogą nie wystąpić w czasie kompilacji - ale to efekt jest na ogół niewielki. W zamian otrzymujesz więcej niż to, o co prosiłeś - nie tylko możesz bezpiecznie opublikować jedną HashMap, ale możesz przechowywać dowolną liczbę niezmodyfikowanych HashMapplików w tym samym numerze referencyjnym i mieć pewność, że wszyscy czytelnicy zobaczą bezpiecznie opublikowaną mapę .

Więcej krwawych informacji można znaleźć w Shipilev lub w tym FAQ autorstwa Mansona i Goetza .

[1] Cytat bezpośrednio z Shipilev .

^a To brzmi skomplikowanie, ale mam na myśli to, że można przypisać odwołanie w czasie tworzenia - albo w punkcie deklaracji, albo w konstruktorze (pola składowe) lub inicjalizatorze statycznym (pola statyczne).

^b Opcjonalnie możesz użyć synchronizedmetody, aby uzyskać / ustawić, AtomicReferencelub coś w tym stylu, ale mówimy o minimalnej pracy, którą możesz wykonać.

c Niektóre architektury z bardzo słabymi modelami pamięci (patrzę na ciebie , Alpha) mogą wymagać pewnego rodzaju bariery odczytu przed finalodczytem - ale są one obecnie bardzo rzadkie.

Jeremy Manson, bóg, jeśli chodzi o model pamięci w Javie, prowadzi na ten temat trzyczęściowy blog - ponieważ w istocie zadajesz pytanie „Czy dostęp do niezmiennej mapy HashMap jest bezpieczny” - odpowiedź na to pytanie brzmi: tak. Ale musisz odpowiedzieć na predykat na to pytanie, które brzmi - „Czy moja mapa HashMap jest niezmienna”. Odpowiedź może Cię zaskoczyć - Java ma stosunkowo skomplikowany zestaw reguł określania niezmienności.

Aby uzyskać więcej informacji na ten temat, przeczytaj posty na blogu Jeremy'ego:

Część 1 dotycząca niezmienności w Javie: http://jeremymanson.blogspot.com/2008/04/immutability-in-java.html

Część 2 dotycząca niezmienności w Javie: http://jeremymanson.blogspot.com/2008/07/immutability-in-java-part-2.html

Część 3 dotycząca niezmienności w Javie: http://jeremymanson.blogspot.com/2008/07/immutability-in-java-part-3.html

Odczyty są bezpieczne z punktu widzenia synchronizacji, ale nie z punktu widzenia pamięci. Jest to coś, co jest powszechnie źle rozumiane przez programistów Java, w tym tutaj w Stackoverflow. (Obserwuj ocenę tej odpowiedzi, aby uzyskać dowód).

Jeśli masz uruchomione inne wątki, mogą nie widzieć zaktualizowanej kopii mapy HashMap, jeśli nie ma żadnego zapisu do pamięci z bieżącego wątku. Zapisy do pamięci są wykonywane przy użyciu zsynchronizowanych lub nietrwałych słów kluczowych lub przy użyciu niektórych konstrukcji współbieżności języka Java.

Więcej informacji można znaleźć w artykule Briana Goetza na temat nowego modelu pamięci Java .

Po dokładniejszym przyjrzeniu się, znalazłem to w dokumentacji java (moje podkreślenie):

Zauważ, że ta implementacja nie jest zsynchronizowana. Jeśli wiele wątków jednocześnie uzyskuje dostęp do mapy skrótów, a co najmniej jeden z wątków modyfikuje mapę strukturalnie, musi być zsynchronizowany zewnętrznie. (Modyfikacja strukturalna to dowolna operacja, która dodaje lub usuwa jedno lub więcej mapowań; sama zmiana wartości skojarzonej z kluczem, który już zawiera instancja, nie jest modyfikacją strukturalną).

Wydaje się to sugerować, że będzie to bezpieczne, zakładając, że stwierdzenie jest odwrotne do prawdy.

Należy zauważyć, że w pewnych okolicznościach metoda get () z niezsynchronizowanej HashMap może powodować nieskończoną pętlę. Może się tak zdarzyć, jeśli współbieżna metoda put () powoduje ponowne zhaszowanie mapy.

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

Jest jednak ważny zwrot akcji. Dostęp do mapy jest bezpieczny, ale generalnie nie ma gwarancji, że wszystkie wątki zobaczą dokładnie ten sam stan (a tym samym wartości) HashMap. Może się to zdarzyć w systemach wieloprocesorowych, w których modyfikacje HashMap wykonane przez jeden wątek (np. Ten, który ją zapełnił) mogą znajdować się w pamięci podręcznej tego procesora i nie będą widoczne dla wątków działających na innych procesorach, dopóki operacja ogrodzenia pamięci nie zostanie wykonywane z zapewnieniem spójności pamięci podręcznej. Specyfikacja języka Java jest jasna w tym przypadku: rozwiązaniem jest uzyskanie blokady (zsynchronizowanej (...)), która emituje operację ogrodzenia pamięci. Tak więc, jeśli jesteś pewien, że po wypełnieniu HashMap każdy z wątków uzyskuje DOWOLNĄ blokadę, od tego momentu można uzyskać dostęp do HashMap z dowolnego wątku, aż do ponownej modyfikacji HashMap.

Zgodnie z http://www.ibm.com/developerworks/java/library/j-jtp03304/ # Bezpieczeństwo inicjalizacji możesz uczynić swój HashMap ostatnim polem i po zakończeniu konstruktora zostanie bezpiecznie opublikowany.

... W nowym modelu pamięci istnieje coś podobnego do relacji zdarzenie przed zapisem między zapisem końcowego pola w konstruktorze a początkowym ładowaniem współdzielonego odniesienia do tego obiektu w innym wątku. ...

Tak więc scenariusz, który opisałeś, polega na tym, że musisz umieścić zbiór danych w mapie, a kiedy skończysz ją wypełniać, traktujesz ją jako niezmienną. Jednym z podejść, które jest „bezpieczne” (co oznacza, że ​​wymuszasz, aby było traktowane jako niezmienne) jest zastąpienie odniesienia Collections.unmodifiableMap(originalMap)momentem gotowości do uczynienia go niezmiennym.

Aby zapoznać się z przykładem tego, jak źle mapy mogą zawieść, jeśli są używane jednocześnie, oraz sugerowane obejście, o którym wspomniałem, sprawdź ten wpis dotyczący parady błędów: bug_id = 6423457

To pytanie jest omówione w książce Briana Goetza „Java Concurrency in Practice” (Listing 16.8, s. 350):

@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);
    }
}

Ponieważ statesjest zadeklarowany jako, finala jego inicjalizacja jest wykonywana w konstruktorze klasy właściciela, każdy wątek, który później odczytuje tę mapę, ma gwarancję, że zobaczy ją w momencie zakończenia konstruktora, pod warunkiem, że żaden inny wątek nie będzie próbował zmodyfikować zawartości mapy.

Ostrzegamy, że nawet w kodzie jednowątkowym zastąpienie ConcurrentHashMap przez HashMap może nie być bezpieczne. ConcurrentHashMap zabrania null jako klucza lub wartości. HashMap ich nie zabrania (nie pytaj).

Tak więc w mało prawdopodobnej sytuacji, gdy istniejący kod może dodać wartość null do kolekcji podczas instalacji (prawdopodobnie w przypadku awarii), zastąpienie kolekcji zgodnie z opisem zmieni zachowanie funkcjonalne.

To powiedziawszy, pod warunkiem, że nie robisz nic innego, równoczesne odczyty z HashMap są bezpieczne.

[Edycja: przez „współbieżne odczyty” rozumiem, że nie ma też jednoczesnych modyfikacji.

Inne odpowiedzi wyjaśniają, jak to zapewnić. Jednym ze sposobów jest uczynienie mapy niezmienną, ale nie jest to konieczne. Na przykład model pamięci JSR133 jawnie definiuje rozpoczęcie wątku jako akcję synchroniczną, co oznacza, że ​​zmiany wprowadzone w wątku A przed rozpoczęciem wątku B są widoczne w wątku B.

Nie zamierzam zaprzeczać bardziej szczegółowym odpowiedziom na temat modelu pamięci Java. Ta odpowiedź ma na celu zwrócenie uwagi, że nawet poza kwestiami współbieżności istnieje co najmniej jedna różnica API między ConcurrentHashMap i HashMap, która może zlikwidować nawet program jednowątkowy, który zastąpił jeden z nich.]

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

tutaj jest źródło HashMap. Jak widać, nie ma tam absolutnie żadnego kodu blokującego / mutex.

Oznacza to, że chociaż można czytać z HashMap w sytuacji wielowątkowej, zdecydowanie użyłbym ConcurrentHashMap, gdyby było wiele zapisów.

Co ciekawe, zarówno .NET HashTable, jak i Dictionary <K, V> mają wbudowany kod synchronizacji.

Jeśli inicjalizacja i każde wprowadzenie jest zsynchronizowane, zapisujesz.

Poniższy kod jest zapisywany, ponieważ classloader zajmie się synchronizacją:

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

}

Poniższy kod jest zapisywany, ponieważ zapis volatile zajmie się synchronizacją.

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;
  }
}

Będzie to również działać, jeśli zmienna składowa jest ostateczna, ponieważ final jest również niestabilna. A jeśli metoda jest konstruktorem.