1) CopyOnWriteArraySet
Implementacja jest dość prosta - w zasadzie ma listę elementów w tablicy, a po zmianie listy kopiuje tablicę. Iteracje i inne dostępy, które są uruchomione w tym czasie, są kontynuowane ze starą tablicą, unikając konieczności synchronizacji między czytnikami i piszącymi (chociaż samo pisanie wymaga synchronizacji). Normalnie szybkie operacje na zbiorach (szczególnie contains()
) są tutaj dość wolne, ponieważ tablice będą przeszukiwane w czasie liniowym.
Używaj tego tylko dla naprawdę małych zestawów, które będą często czytane (iterowane) i rzadko zmieniane. (Przykładem byłyby zestawy słuchaczy swingów, ale nie są to tak naprawdę zestawy i powinny być używane tylko z EDT).
2) Collections.synchronizedSet
po prostu zawinie zsynchronizowany blok wokół każdej metody z oryginalnego zestawu. Nie powinieneś uzyskiwać bezpośredniego dostępu do oryginalnego zestawu. Oznacza to, że żadne dwie metody z zestawu nie mogą być wykonywane jednocześnie (jedna będzie blokować, dopóki druga nie zakończy się) - jest to bezpieczne wątkowo, ale nie będziesz mieć współbieżności, jeśli wiele wątków naprawdę używa zestawu. Jeśli używasz iteratora, zwykle nadal musisz zsynchronizować zewnętrzną, aby uniknąć ConcurrentModificationExceptions podczas modyfikowania zestawu między wywołaniami iteratora. Wydajność będzie podobna do oryginalnego zestawu (ale z pewnym narzutem synchronizacji i blokowaniem, jeśli jest używany jednocześnie).
Użyj tego, jeśli masz tylko niską współbieżność i chcesz mieć pewność, że wszystkie zmiany są natychmiast widoczne dla innych wątków.
3) ConcurrentSkipListSet
jest równoczesną SortedSet
implementacją, z większością podstawowych operacji w O (log n). Pozwala na jednoczesne dodawanie / usuwanie i odczytywanie / iterację, gdzie iteracja może lub nie może informować o zmianach od czasu utworzenia iteratora. Operacje zbiorcze to po prostu wielokrotne pojedyncze wywołania, a nie atomowo - inne wątki mogą obserwować tylko niektóre z nich.
Oczywiście możesz tego użyć tylko wtedy, gdy masz jakiś całkowity porządek na swoich elementach. Wygląda na to, że jest to idealny kandydat do sytuacji z dużą współbieżnością, dla niezbyt dużych zestawów (ze względu na O (log n)).
4) Dla ConcurrentHashMap
(i zbioru pochodnego): Tutaj najbardziej podstawowe opcje są (średnio, jeśli masz dobre i szybkie hashCode()
) w O (1) (ale mogą się zdegenerować do O (n)), jak dla HashMap / HashSet. Istnieje ograniczona współbieżność zapisu (tabela jest podzielona na partycje, a dostęp do zapisu zostanie zsynchronizowany na wymaganej partycji), podczas gdy dostęp do odczytu jest w pełni współbieżny z nim samym i zapisywanymi wątkami (ale może jeszcze nie widzieć wyników aktualnie wprowadzanych zmian pisemny). Iterator może, ale nie musi, widzieć zmiany od czasu jego utworzenia, a operacje zbiorcze nie są atomowe. Zmiana rozmiaru jest powolna (jak w przypadku HashMap / HashSet), dlatego staraj się tego uniknąć, szacując wymagany rozmiar podczas tworzenia (i wykorzystując o około 1/3 więcej, ponieważ zmienia rozmiar, gdy jest zapełniony w 3/4).
Użyj tego, gdy masz duże zestawy, dobrą (i szybką) funkcję skrótu i możesz oszacować rozmiar zestawu i wymaganą współbieżność przed utworzeniem mapy.
5) Czy istnieją inne współbieżne implementacje map, których można by tutaj użyć?
ConcurrentHashMap
oparciu o zestaw „staraj się więc tego uniknąć, szacując wymagany rozmiar podczas tworzenia”. Rozmiar, który podasz mapie, powinien być o ponad 33% większy niż szacunek (lub znana wartość), ponieważ rozmiar zestawu zmienia się przy 75% obciążeniu. UżywamexpectedSize + 4 / 3 + 1
+
ma być*
?expectedSize * 4 / 3 + 1
ConcurrentMap
(lubHashMap
) w Javie 8, jeśli liczba wpisów mapowanych do tego samego zasobnika osiągnie wartość progową (uważam, że jest to 16), lista zostanie zmieniona na drzewo wyszukiwania binarnego (drzewo czerwono-czarne do dokładnego określenia) iw takim przypadku wyszukaj czas byłbyO(lg n)
i nieO(n)
.Możliwe jest połączenie
contains()
wydajnościHashSet
z właściwościami związanymi ze współbieżnością,CopyOnWriteArraySet
używającAtomicReference<Set>
i zastępując cały zestaw przy każdej modyfikacji.Szkic wdrożeniowy:
źródło
AtomicReference
oznacza wartość zmienną. Oznacza to, że żaden wątek nie odczytuje nieaktualnych danych i zapewniahappens-before
gwarancję, że kompilator nie może zmienić kolejności kodu. Ale jeśliAtomicReference
używane są tylko metody get / set of , to faktycznie oznaczamy naszą zmienną jako zmienną w fantazyjny sposób.abstract
, najwyraźniej aby uniknąć konieczności pisania kilku metod. Zacząłem je dodawać, ale napotkałem blokadę za pomocąiterator()
. Nie wiem, jak utrzymać iterator nad tą rzeczą bez niszczenia modelu. Wydaje się, że zawsze muszę przechodzić przezref
i za każdym razem mogę uzyskać inny zestaw bazowy, co wymaga uzyskania nowego iteratora na zestawie bazowym, co jest dla mnie bezużyteczne, ponieważ zacznie się od pozycji zero. Jakieś spostrzeżenia?Jeśli Javadocs nie pomoże, prawdopodobnie powinieneś po prostu znaleźć książkę lub artykuł, aby przeczytać o strukturach danych. W skrócie:
źródło
Jednoczesny zestaw słabych odniesień
Kolejnym zwrotem akcji jest bezpieczny dla wątków zestaw słabych odniesień .
Taki zestaw jest przydatny do śledzenia subskrybentów w scenariuszu pub-sub . Kiedy subskrybent znajduje się poza zasięgiem w innych miejscach i dlatego zmierza w kierunku zostania kandydatem do zbierania śmieci, nie trzeba mu przeszkadzać z wdzięcznym anulowaniem subskrypcji. Słabe odwołanie umożliwia subskrybentowi dokończenie jego przejścia do bycia kandydatem do czyszczenia pamięci. Kiedy śmieci zostaną ostatecznie zebrane, wpis w zestawie jest usuwany.
Chociaż żaden taki zestaw nie jest dostarczany bezpośrednio z dołączonymi klasami, możesz go utworzyć za pomocą kilku wywołań.
Najpierw zaczynamy od tworzenia
Set
słabych referencji, wykorzystującWeakHashMap
klasę. Jest to pokazane w dokumentacji klasy dlaCollections.newSetFromMap
.Wartość mapy,
Boolean
nie ma znaczenia tutaj jako Key mapy sprawia, że naszeSet
.W scenariuszu takim jak pub-sub potrzebujemy bezpieczeństwa wątków, jeśli subskrybenci i wydawcy działają w oddzielnych wątkach (całkiem prawdopodobne).
Idź o krok dalej, pakując jako zsynchronizowany zestaw, aby uczynić ten zestaw bezpiecznym dla wątków. Przekaż wezwanie do
Collections.synchronizedSet
.Teraz możemy dodawać i usuwać subskrybentów z naszego wynikowego
Set
. A wszyscy „znikający” subskrybenci zostaną ostatecznie automatycznie usunięci po wykonaniu operacji czyszczenia pamięci. To, kiedy nastąpi to wykonanie, zależy od implementacji modułu odśmiecania pamięci maszyny JVM i aktualnej sytuacji w środowisku wykonawczym. AbyWeakHashMap
zapoznać się z dyskusją i przykładem, kiedy i jak baza usuwa wygasłe wpisy, zobacz pytanie: * Czy WeakHashMap stale rośnie, czy też czyści klucze śmieci? * .źródło