Czy HashMap jest bezpieczny dla wątków dla różnych kluczy?

87

Jeśli mam dwa wiele wątków uzyskujących dostęp do mapy HashMap, ale gwarantuję, że nigdy nie będą one miały dostępu do tego samego klucza w tym samym czasie, czy może to nadal prowadzić do sytuacji wyścigu?

Helder S Ribeiro
źródło

Odpowiedzi:

99

W odpowiedzi @ dotsid mówi tak:

Jeśli zmienisz HashMap w jakikolwiek sposób, twój kod zostanie po prostu uszkodzony.

On ma rację. HashMap, który jest aktualizowany bez synchronizacji, zepsuje się, nawet jeśli wątki używają rozłącznych zestawów kluczy. Oto kilka rzeczy, które mogą się nie udać.

  • Jeśli jeden wątek ma wartość put, inny wątek może zobaczyć nieaktualną wartość rozmiaru hashmap.

  • Gdy wątek wykonuje putoperację, która wyzwala przebudowę tabeli, inny wątek może zobaczyć przejściowe lub nieaktualne wersje odwołania do tablicy z tablicą mieszającą, jej rozmiar, zawartość lub łańcuchy skrótów. Może nastąpić chaos.

  • Gdy wątek wykonuje polecenie putdla klucza, który koliduje z jakimś kluczem używanym przez inny wątek, a drugi wątek wykonuje polecenie putdla swojego klucza, ten ostatni może zobaczyć nieaktualną kopię odwołania do łańcucha skrótu. Może nastąpić chaos.

  • Kiedy jeden wątek sonduje stół za pomocą klucza, który koliduje z jednym z kluczy innego wątku, może napotkać ten klucz na łańcuchu. Wywoła equals na tym kluczu, a jeśli wątki nie są zsynchronizowane, metoda equals może napotkać przestarzały stan w tym kluczu.

A jeśli masz jednocześnie dwa wątki, które wykonują putlub removeżądają, istnieje wiele okazji do warunków wyścigu.

Przychodzą mi do głowy trzy rozwiązania:

  1. Użyj ConcurrentHashMap.
  2. Używaj regularnego, HashMapale synchronizuj na zewnątrz; np. używanie prymitywnych muteksów, Lockobiektów itp.
  3. Użyj innego HashMapdla każdego wątku. Jeśli wątki naprawdę mają rozłączny zestaw kluczy, nie powinno być potrzeby (z perspektywy algorytmicznej), aby współdzieliły jedną mapę. Rzeczywiście, jeśli twoje algorytmy obejmują wątki iterujące klucze, wartości lub wpisy mapy w pewnym momencie, podzielenie pojedynczej mapy na wiele map może spowodować znaczne przyspieszenie tej części przetwarzania.
Stephen C.
źródło
30

Po prostu użyj ConcurrentHashMap. ConcurrentHashMap wykorzystuje wiele blokad, które obejmują szereg zasobników mieszania, aby zmniejszyć ryzyko zakwestionowania blokady. Uzyskanie niezakwestionowanej blokady ma marginalny wpływ na wydajność.

Odpowiadając na pierwotne pytanie: zgodnie z javadoc, dopóki struktura mapy nie ulegnie zmianie, wszystko jest w porządku. Oznacza to brak usuwania elementów i dodawania nowych kluczy, których nie ma jeszcze na mapie. Zastąpienie wartości skojarzonej z istniejącymi kluczami jest w porządku.

Jeśli wiele wątków uzyskuje dostęp do mapy skrótów jednocześnie, a co najmniej jeden z wątków modyfikuje mapę strukturalnie, musi zostać 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ą).

Chociaż nie gwarantuje widoczności. Musisz więc od czasu do czasu zaakceptować pobieranie nieaktualnych skojarzeń.

Tim Bender
źródło
6

Zależy to od tego, co masz na myśli pod pojęciem „dostęp”. Jeśli tylko czytasz, możesz odczytać nawet te same klucze, o ile widoczność danych jest gwarantowana w sekcji „ reguł zdarza się przed ”. Oznacza to, że HashMapnie powinno się zmieniać, a wszystkie zmiany (początkowe konstrukcje) powinny zostać zakończone, zanim jakikolwiek czytelnik zacznie uzyskiwać dostęp HashMap.

Jeśli zmienisz HashMapw jakikolwiek sposób, twój kod jest po prostu uszkodzony. @Stephen C bardzo dobrze wyjaśnia, dlaczego.

EDYCJA: Jeśli pierwszy przypadek jest Twoją rzeczywistą sytuacją, zalecam użycie, Collections.unmodifiableMap()aby mieć pewność, że HashMap nigdy nie zostanie zmieniony. Obiekty, na które wskazujeHashMap nie powinny się zmieniać, więc agresywne użycie finalsłowa kluczowego może ci pomóc.

I jak mówi @Lars Andren, ConcurrentHashMapw większości przypadków jest to najlepszy wybór.

Denis Bazhenov
źródło
2
ConcurrentHashMap to moim zdaniem najlepszy wybór. Jedyny powód, dla którego go nie polecałem, bo autor o to nie pytał :) Ma mniejszą przepustowość z powodu operacji CAS, ale jak mówi złota zasada programowania współbieżnego: „Zrób to dobrze, a dopiero potem zrób to szybko ":)
Denis Bazhenov
unmodifiableMapzapewnia, że ​​klient nie może zmienić mapy. Nie robi nic, aby zapewnić, że mapa bazowa nie zostanie zmieniona.
Pete Kirkham
Jak już wspomniałem: "Obiekty, które są wskazywane przez HashMap również nie powinny się zmieniać"
Denis Bazhenov
4

Modyfikacja HashMap bez odpowiedniej synchronizacji z dwóch wątków może łatwo doprowadzić do sytuacji wyścigu.

  • Kiedy put() prowadzi do zmiany rozmiaru tabeli wewnętrznej, zajmuje to trochę czasu, a drugi wątek kontynuuje zapisywanie w starej tabeli.
  • Dwa put()dla różnych kluczy prowadzą do aktualizacji tego samego zasobnika, jeśli skróty kluczy są równe modulo wielkości tabeli. (W rzeczywistości relacja między kodem skrótu a indeksem zasobnika jest bardziej skomplikowana, ale nadal mogą występować kolizje).
Christian Semrau
źródło
1
To jest gorsze niż tylko warunki wyścigu. W zależności od wewnętrznych elementów HashMapimplementacji, z której korzystasz, możesz uszkodzić HashMapstruktury danych itp. Spowodowane przez anomalie pamięci.
Stephen C