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?
źródło
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?
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 put
operację, 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 put
dla klucza, który koliduje z jakimś kluczem używanym przez inny wątek, a drugi wątek wykonuje polecenie put
dla 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ą put
lub remove
żądają, istnieje wiele okazji do warunków wyścigu.
Przychodzą mi do głowy trzy rozwiązania:
ConcurrentHashMap
.HashMap
ale synchronizuj na zewnątrz; np. używanie prymitywnych muteksów, Lock
obiektów itp.HashMap
dla 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.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ń.
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 HashMap
nie powinno się zmieniać, a wszystkie zmiany (początkowe konstrukcje) powinny zostać zakończone, zanim jakikolwiek czytelnik zacznie uzyskiwać dostęp HashMap
.
Jeśli zmienisz HashMap
w 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 final
słowa kluczowego może ci pomóc.
I jak mówi @Lars Andren, ConcurrentHashMap
w większości przypadków jest to najlepszy wybór.
unmodifiableMap
zapewnia, że klient nie może zmienić mapy. Nie robi nic, aby zapewnić, że mapa bazowa nie zostanie zmieniona.Modyfikacja HashMap bez odpowiedniej synchronizacji z dwóch wątków może łatwo doprowadzić do sytuacji wyścigu.
put()
prowadzi do zmiany rozmiaru tabeli wewnętrznej, zajmuje to trochę czasu, a drugi wątek kontynuuje zapisywanie w starej tabeli.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).źródło
HashMap
implementacji, z której korzystasz, możesz uszkodzićHashMap
struktury danych itp. Spowodowane przez anomalie pamięci.