Kiedy ConcurrentSkipListSet jest przydatny?

Właśnie zobaczyłem tę strukturę danych w Java 6 API i jestem ciekawy, kiedy będzie to przydatny zasób. Przygotowuję się do egzaminu scjp i nie widzę tego w książce Kathy Sierra, chociaż widziałem próbne pytania egzaminacyjne, które o tym wspominają.

ConcurrentSkipListSet i ConcurrentSkipListMap są przydatne, gdy potrzebujesz posortowanego kontenera, do którego będzie uzyskiwać dostęp wiele wątków. Są to zasadniczo odpowiedniki TreeMap i TreeSet dla współbieżnego kodu.

Implementacja JDK 6 jest oparta na wysokowydajnych dynamicznych tabelach skrótów bez blokad i zestawach opartych na listach autorstwa Maged Michaela z IBM, co pokazuje, że wiele operacji na listach pomijania można zaimplementować niepodzielnie za pomocą operacji porównania i wymiany (CAS) . Są one wolne od blokad, więc nie musisz się martwić o narzut synchronized(w przypadku większości operacji) podczas korzystania z tych klas.

Obecnie w Javie nie ma współbieżnej implementacji Map / Set opartej na drzewie czerwono-czarnym . Przejrzałem trochę literaturę i znalazłem kilka artykułów, które pokazały, że współbieżne drzewa RB przewyższają listy pominięć, ale wiele z tych testów zostało wykonanych z pamięcią transakcyjną , która nie jest obecnie obsługiwana sprzętowo na żadnej z głównych architektur.

Zakładam, że faceci z JDK wybrali tutaj listę pominięć, ponieważ implementacja była dobrze znana i ponieważ uczynienie jej bez blokad było proste i przenośne (przy użyciu CAS). Jeśli ktoś chce wyjaśnić, proszę. Jestem ciekawy.

listy pomijane są listami posortowanymi i można je skutecznie modyfikować za pomocą wydajności log (n). pod tym względem jest jak TreeSet. jednak nie ma ConcurrentTreeSet. słyszałem, że lista pomijana jest bardzo łatwa do zaimplementowania, prawdopodobnie dlatego.

W każdym razie, gdy potrzebujesz współbieżnego, posortowanego i wydajnego zestawu, możesz użyć ConcurrentSkipListSet

Są one przydatne, gdy potrzebujesz zestawu, do którego można bezpiecznie uzyskiwać dostęp przez wiele wątków jednocześnie. Zapewnia również przyzwoitą wydajność, będąc słabo spójnym - wstawki można bezpiecznie tworzyć podczas iteracji zestawu, ale nie ma gwarancji, że Twój Iterator zobaczy tę wstawkę.

ConcurrentSkipListMap było fantastycznym odkryciem, gdy musiałem zaimplementować warstwę replikacji dla domowej pamięci podręcznej. Aspekty Map zaimplementowały pamięć podręczną, a podstawowe aspekty List pozwalają mi śledzić kolejność, w jakiej obiekty pojawiały się w pamięci podręcznej. Aspekt „pomijania” tej listy sprawił, że efektywne było usunięcie obiektu z jednego miejsca na liście i przesunięcie go do końca, gdy został zastąpiony w pamięci podręcznej.