Czy w JDK Javy jest lista współbieżna?

277

Jak mogę utworzyć współbieżną instancję List, w której mogę uzyskać dostęp do elementów według indeksu? Czy JDK ma jakieś klasy lub metody fabryczne, których mogę użyć?

AlikElzin-kilaka
źródło
28
Dlaczego nie konstruktywny? Kilka proponowanych CopyOnWriteArrayList, które nie znajdują się w .Net. Można powiedzieć, że oba pytania odnoszą się do siebie, ale nie zamykają tego !!!
AlikElzin-kilaka
1
Nie mam pojęcia, dlaczego Jarrod Roberson uważa, że ​​dobrym pomysłem byłoby przejrzenie szczegółowych zmian dokonanych przez Stephana i przywrócenie ich do pierwotnego, źle sformułowanego pytania. Odpowiedź Jarroda jest nadal całkowicie akceptowalna. W rzeczywistości CopyOnWriteArrayList jest jedyną współbieżną klasą implementującą Listę w JDK. Zdziwiony ...
Matt Passell
10
Ponieważ zaakceptowana odpowiedź była na pierwotne pytanie, a Stephan zadał całkowicie niezwiązane pytanie z garścią kodu źródłowego, którego oryginalny plakat nie zawierał nigdzie całkowicie zmieniając pytanie, co wygenerowało więcej odpowiedzi sugerujących inne rzeczy niż te, Listktóre oryginalnie mówi, że jest to wymóg, który uważa się za wandalizm. Moderator już zablokował to pytanie z powodu osób, które narzekają, że odpowiedzi nie odpowiadają na zdewastowaną wersję pytania.
1
/ locked/ closed/ poprzedni komentarz
8
Nie ma powodu, aby to pytanie było zamknięte. Pyta o klasy w JDK, co niczym nie przypomina szukania biblioteki; to podstawa Java.
maaartinus,

Odpowiedzi:

175

W pliku java.util.concurrent istnieje jednoczesna implementacja listy . W szczególności CopyOnWriteArrayList .

Basil Bourque
źródło
84
Pamiętaj, że kopiuje całą listę na każdej wkładce, więc często jest nieefektywna.
dfrankow
22
@dfrankow Ale może być bardziej wydajny, jeśli iterujesz znacznie więcej niż aktualizujesz.
b1nary.atr0phy
Nie działa dobrze, jak pokazano tutaj. Mam wyjątki, mimo że po prostu używam jego metody addAll i czytam ją za pomocą stream. stackoverflow.com/questions/1527519/…
devssh
166

Jeśli nie zależy ci na dostępie opartym na indeksach i chcesz tylko właściwości listy zachowującej porządek wstawiania, możesz rozważyć java.util.concurrent.ConcurrentLinkedQueue . Ponieważ implementuje Iterable, po zakończeniu dodawania wszystkich elementów możesz zapętlać zawartość za pomocą rozszerzonej składni:

Queue<String> globalQueue = new ConcurrentLinkedQueue<String>();

//Multiple threads can safely call globalQueue.add()...

for (String href : globalQueue) {
    //do something with href
}
Matt Passell
źródło
4
Myślę, że uproszczona instrukcja for ( :) nazywa się foreach: docs.oracle.com/javase/1.5.0/docs/guide/language/foreach.html
AlikElzin-kilaka
2
@ AlikElzin-kilaka Masz rację. Myślę, że ta nazwa zawsze mnie niepokoiła, ponieważ rzeczywista składnia nie zawiera słowa „każdy”, ale zaktualizuję odpowiedź, aby użyć oficjalnej nazwy. :)
Matt Passell
3
@ AlikElzin-kilaka Nitpicking, ale zgodnie z wersją JLS 8 nazywa się to „ulepszoną instrukcją”. To samo w samouczku Java .
Roland
1
@Roland zdecydowanie NIE nitpicking. Istnieje (teraz) różnica między „dla każdego” a „ulepszonym dla” w Javie.
hfontanez
2
@Roland pośrednio. Wierzę, że zmienili nazwę „dla każdej pętli” na „ulepszoną dla”, aby wyeliminować zamieszanie między Stream.forEach a tym, co jest obecnie znane jako „ulepszone”.
hfontanez
128

Możesz bardzo dobrze korzystać z kolekcji.synchronizedList (List), jeśli wszystko, czego potrzebujesz, to prosta synchronizacja wywołań:

 List<Object> objList = Collections.synchronizedList(new ArrayList<Object>());
Yanick Rochon
źródło
70
Wynik synchronizedListjest „zsynchronizowany”, ale nie „równoczesny”. Jednym fundamentalnym problemem jest to, że wiele operacji List - które są oparte na indeksach - same w sobie nie są atomowe i muszą być częścią większej konstrukcji wzajemnego wykluczania.
6
IMO, asing a Vectorjest prostsze niż Collections.synchronizedList(new ArrayList<Object>()).
Stephan
8
Wynik synchronizedList jest „synchronizowany”, ale nie „współbieżny”.
Kanagavelu Sugumar
46

Ponieważ czynność uzyskania pozycji i pobrania elementu z danej pozycji naturalnie wymaga pewnego zablokowania (nie możesz mieć listy zawierającej zmiany strukturalne między tymi dwiema operacjami).

Ideą współbieżnego zbierania jest to, że każda operacja jest atomowa i może być wykonana bez wyraźnego blokowania / synchronizacji.

Dlatego ustalenie pozycji elementu nz danej Listoperacji atomowej nie ma zbyt dużego sensu w sytuacji, w której przewiduje się równoczesny dostęp.

Joachim Sauer
źródło
6
Joachim, myślę, że trafiłeś w sedno. Weźmy na przykład listę tylko do odczytu jako listę współbieżną. Uzyskiwanie elementu w pozycji N z listy nie tylko ma sens, ale jest sednem problemu. Zatem niezmienna lista (mała litera L) byłaby dobrym przykładem, ale nie jest to lista (duża litera L). CopyOnWriteArrayList jest równoległy, ale wiele osób nie lubi wydajności. Rozwiązanie wzdłuż lin (lin sznurkowych) prawdopodobnie byłoby dobrym zwycięzcą.
johnstosh
1
Bardzo dobra uwaga. Ale lista, z której korzysta OP, może mieć bardzo specyficzne zastosowanie. Np. Można go wypełnić w równoczesnym środowisku, a następnie „zablokować” (cokolwiek to znaczy), a następnie bezpiecznie uzyskać dostęp przez indeks. Tak więc w pierwszej fazie wypełniania taka lista nadal będzie wymagała implementacji bezpiecznej dla wątków. Niestety PO nie sprecyzował, w jaki sposób zostanie wykorzystana lista, której szuka.
igor.zh
13

Masz następujące opcje:

  • Collections.synchronizedList(): Można owinąć każdą Listrealizacji ( ArrayList, LinkedListlub listę 3rd-party). Dostęp do każdej metody (odczyt i zapis) będzie chroniony przy użyciu synchronized. Podczas używania iterator()lub rozszerzania pętli należy ręcznie zsynchronizować; podczas iteracji inne wątki są całkowicie blokowane nawet przed czytaniem. Możesz także zsynchronizować osobno dla każdego hasNexti nextpołączeń, ale wtedy ConcurrentModificationExceptionjest to możliwe.

  • CopyOnWriteArrayList: modyfikacja jest kosztowna, ale czytanie jest bez czekania. Iteratory nigdy nie rzucają ConcurrentModificationException, zwracają migawkę listy w momencie tworzenia iteratora, nawet jeśli lista jest modyfikowana przez inny wątek podczas iteracji. Przydatne w przypadku rzadko aktualizowanych list. Operacje zbiorcze, takie jak, addAllsą preferowane w przypadku aktualizacji - tablica wewnętrzna jest kopiowana rzadziej.

  • Vector: bardzo podobnie synchronizedList, ale iteracja również jest zsynchronizowana. Jednak iteratory mogą rzucać ConcurrentModificationException, jeśli wektor jest modyfikowany przez inny wątek podczas iteracji.

Inne opcje:

  • Collections.unmodifiableList(): bez blokady, bezpieczny dla wątków, ale niemodyfikowalny
  • Queuelub Dequemoże być alternatywą, jeśli dodajesz / usuwasz tylko na końcach listy i iterujesz listę. Brak dostępu według indeksu i dodawanie / usuwanie w dowolnych miejscach. Mają wiele współbieżnych implementacji o lepszej wydajności i lepszym współbieżnym dostępie, ale wykracza to poza zakres tego pytania. Możesz także zajrzeć na JCTools , zawierają one bardziej wydajne implementacje kolejek przeznaczone dla pojedynczego konsumenta lub pojedynczego producenta.
Oliv
źródło
4

wprowadź opis zdjęcia tutaj

CopyOnWriteArrayList jest bezpiecznym dla wątków wariantem ArrayList, w którym wszystkie operacje mutacyjne (dodawanie, ustawianie itp.) Są realizowane przez utworzenie nowej kopii podstawowej tablicy.

CopyOnWriteArrayList to współbieżna alternatywa dla zsynchronizowanej listy, która implementuje interfejs List i jego część pakietu java.util.concurrent oraz jego kolekcję bezpieczną dla wątków.

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

CopyOnWriteArrayList jest bezpieczny w razie awarii i nie zgłasza ConcurrentModificationException, gdy podstawowa CopyOnWriteArrayList jest modyfikowana podczas iteracji, użyj osobnej kopii ArrayList.

Jest to zwykle zbyt kosztowne, ponieważ tablica kopiowania obejmowała każdą operację aktualizacji, w której zostanie utworzona sklonowana kopia. CopyOnWriteArrayList to najlepszy wybór tylko w przypadku częstych operacji odczytu.

/**
         * Returns a shallow copy of this list.  (The elements themselves
         * are not copied.)
         *
         * @return a clone of this list
         */
        public Object clone() {
            try {
                @SuppressWarnings("unchecked")
                CopyOnWriteArrayList<E> clone =
                    (CopyOnWriteArrayList<E>) super.clone();
                clone.resetLock();
                return clone;
            } catch (CloneNotSupportedException e) {
                // this shouldn't happen, since we are Cloneable
                throw new InternalError();
            }
        }
Vaquar Khan
źródło