Dlaczego nie ma ConcurrentHashSet przeciwko ConcurrentHashMap

537

HashSet jest oparty na HashMap.

Jeśli spojrzymy na HashSet<E>implementację, wszystko jest zarządzane w ramach HashMap<E,Object>.

<E>jest używany jako klucz HashMap.

I wiemy, że HashMapnie jest to bezpieczne dla wątków. Właśnie dlatego mamy ConcurrentHashMapJavę.

Na tej podstawie jestem zdezorientowany, dlaczego nie mamy ConcurrentHashSet, który powinien być oparty na ConcurrentHashMap?

Czy coś jeszcze mi brakuje? Muszę używać Setw środowisku wielowątkowym.

Ponadto, jeśli chcę stworzyć własny, ConcurrentHashSetczy mogę to osiągnąć, po prostu zastępując HashMapgo ConcurrentHashMapi pozostawiając resztę bez zmian?

Talha Ahmed Khan
źródło
2
Po spojrzeniu na API, gdybym zgadywał, powiedziałbym, że sprowadza się to do 2 czynników, (1) unikając konieczności tworzenia klasy w Java API dla każdej odrobiny potrzebnej funkcjonalności (2) Zapewnienie klas wygody dla częściej używane obiekty. Osobiście wolę LinkedHashMap i LinkedHashSet, ponieważ gwarantują, że kolejność jest taka sama jak kolejność wstawiania, jedynym powodem korzystania z zestawu jest unikanie powielania, często nadal chcę zachować porządek wstawiania.
Ali
1
@Ali, ja osobiście wolę LinkedHashMap i LinkedHashSet ,
zajdziesz
9
Trochę stare pytanie, ale ponieważ jest to pierwszy wynik w Google, warto wiedzieć, że ConcurrentSkipListSet ma już implementację ConcurrentHashMap. Zobacz docs.oracle.com/javase/7/docs/api/java/util/concurrent/…
Igor Rodriguez
1
To, co zobaczyłem ze źródła Java, ConcurrentSkipListSetjest oparte na ConcurrentSkipListMapimplementacji ConcurrentNavigableMapi ConcurrentMap.
Talha Ahmed Khan

Odpowiedzi:

581

Nie ma wbudowanego typu, ConcurrentHashSetponieważ zawsze możesz uzyskać zestaw z mapy. Ponieważ istnieje wiele rodzajów map, używasz metody do utworzenia zestawu z danej mapy (lub klasy mapy).

Przed wersją Java 8 tworzysz współbieżny zestaw skrótów wsparty współbieżną mapą skrótu, używając Collections.newSetFromMap(map)

W Javie 8 (wskazanej przez @Matt) można uzyskać widok współbieżnego zestawu skrótów za pośrednictwem ConcurrentHashMap.newKeySet(). Jest to nieco prostsze niż stare, newSetFromMapktóre wymagało przejścia przez pusty obiekt mapy. Ale jest specyficzny dla ConcurrentHashMap.

W każdym razie projektanci Java mogli stworzyć nowy zestaw interfejsów za każdym razem, gdy tworzony był nowy interfejs mapy, ale wzorzec ten byłby niemożliwy do narzucenia, gdy osoby trzecie utworzyły własne mapy. Lepiej jest mieć metody statyczne, które wyprowadzają nowe zbiory; takie podejście zawsze działa, nawet gdy tworzysz własne implementacje map.

Ray Toal
źródło
4
Czy mam rację, mówiąc, że jeśli stworzysz zestaw w ten sposób ConcurrentHashMap, stracisz korzyści, które byś uzyskał ConcurrentHashMap?
Pacerier
19
Nie ma żadnych korzyści do stracenia. newSetFromMapImplementacja znajduje się od linii 3841 w docjar.com/html/api/java/util/Collections.java.html . To tylko opakowanie…
Ray Toal
4
@Andrew, myślę, że motywacja do użycia „ConcurrentSet” wynika nie z API, ale raczej z implementacji - bezpieczeństwa wątków, ale bez uniwersalnego zamka - na przykład wielu jednoczesnych odczytów.
Ustaman Sangat,
5
ConcurrentSkipList ma dużo (wielkości) narzutu, a wyszukiwania są wolniejsze.
eckes
3
zachowaj ostrożność podczas korzystania z tego podejścia, ponieważ niektóre metody nie są poprawnie wdrożone. Wystarczy skorzystać z linków: Collections.newSetFromMaptworzy SetFromMap. np. SetFromMap.removeAllmetoda przekazuje do KeySetView.removeAll, który dziedziczy ConcurrentHashMap$CollectionView.removeAll. Ta metoda jest wysoce nieefektywna przy usuwaniu elementów luzem. wyobraź sobie, że removeAll(Collections.emptySet())przemierza wszystkie elementy Mapbez robienia czegokolwiek. Posiadanie ConcurrentHashSettego, które jest poprawnie wdrażane, będzie lepsze w większości przypadków.
benez
104
Set<String> mySet = Collections.newSetFromMap(new ConcurrentHashMap<String, Boolean>());
Serge Mask
źródło
79

Z Guava 15 możesz także po prostu użyć:

Set s = Sets.newConcurrentHashSet();
kichik
źródło
12
To zawsze koszmar. Jeśli masz zestaw lub mapę, która nie wskazuje, czy coś jest bezpieczne, możesz znaleźć wszelkiego rodzaju zagrożenia i katastrofy. Zawsze chciałbym mieć typ, który wskazuje bezpieczeństwo wątków dla kolekcji (lub nie).
Martin Kersten
11
Opis metody jest dosłownie „Tworzy bezpieczny dla wątków zestaw wspierany przez mapę
hashową
16
Jak powiedziałem, brakuje ConcurrentSet <E>. ConcurrentHashMap jest dostarczany z interfejsem ConcurrentMap, aby to wskazać. Jest to ten sam powód, dla którego zawsze dodaję również ten interfejs ConcurrentSet.
Martin Kersten
35

Jak wspomniał Ray Toal, jest to tak proste, jak:

Set<String> myConcurrentSet = ConcurrentHashMap.newKeySet();
BullyWiiPlaza
źródło
1
Wydaje się, że wymaga to Java 8. Patrząc na implementację, wydaje się, że to tylko opakowanie ConcurrentHashMap.
Mygod
20

Wygląda na to, że Java zapewnia współbieżną implementację zestawu z jego ConcurrentSkipListSet . SkipList Set to tylko szczególny rodzaj zadanej realizacji. Nadal implementuje interfejsy Serializable, Cloneable, Iterable, Collection, NavigableSet, Set, SortedSet. Może to działać dla Ciebie, jeśli potrzebujesz tylko interfejsu Set.

Mike Pone
źródło
12
Zauważ, że ConcurrentSkipListSetelementami powinny byćComparable
user454322
Jeśli potrzebujesz rozszerzyć z zestawu, który jest równoczesny, jest to jedyne rozwiązanie, które będzie działać.
ndm13
ConcurrentSkipListMap dodaje niepotrzebną utratę wydajności w postaci posiadania drzewa jako podstawowej struktury danych zamiast korzystania z HashTable, nawet gdy nie potrzebujesz funkcji sortowania / nawigacji.
Ajeet Ganga
nie używaj, ConcurrentSkipListSetchyba że chcesz SortedSet. Zwykłą operacją, taką jak dodawanie lub usuwanie, powinno być O (1) dla a HashSet, ale O (log (n)) dla a SortedSet.
benez
16

Jak wskazano przez to najlepszy sposób uzyskania współbieżności-stanie HashSet jest za pomocąCollections.synchronizedSet()

Set s = Collections.synchronizedSet(new HashSet(...));

To działało dla mnie i nie widziałem nikogo, kto by na to naprawdę wskazywał.

EDYCJA Jest to mniej wydajne niż obecnie zatwierdzone rozwiązanie, jak zauważa Eugene, ponieważ po prostu owija Twój zestaw w zsynchronizowany dekorator, podczas gdy w ConcurrentHashMaprzeczywistości implementuje współbieżność niskiego poziomu i może wesprzeć Twój zestaw równie dobrze. Dziękuję panu Stepanenkovowi za wyjaśnienie.

http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#synchronizedSet-java.util.Set-

Nirro
źródło
16
synchronizedSetmetoda właśnie tworzy dekorator zgodnie Collectionz metodami owinięcia, które mogłyby być bezpieczny wątku przez synchronizacji cała kolekcja. Ale ConcurrentHashMapjest implementowany przy użyciu algorytmów nieblokujących i synchronizacji „niskiego poziomu” bez żadnych blokad całej kolekcji. Tak więc opakowania z Collections.synchronized... są gorsze w środowiskach wielowątkowych ze względu na wydajność.
Eugene Stepanenkov
12

Możesz użyć guawy, Sets.newSetFromMap(map)aby go zdobyć. Java 6 ma również tę metodę wjava.util.Collections

Bozho
źródło
jest dostępny w java.utll.Colections i zestaw CHM i tak jest zwykle złą rzeczą.
bestsss,
tak, zauważyłem, że jest dodany w Javie 6, więc dodałem go do odpowiedzi
Bozho
Najważniejsze jest to, że jeśli jest to ThreadSafe, i naprawdę w to wątpię.
Talha Ahmed Khan,
@Talha, to wątek jest bezpieczny, ale samo bezpieczeństwo wątku nic nie znaczy
bestsss
Czasami to wszystko znaczy. Ma problemy z wydajnością, chyba że jest to część algorytmu, który zwykle jest implementowany w sposób minimalizujący potrzebę równoczesnego mapowania.
Martin Kersten
5
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;


public class ConcurrentHashSet<E> extends AbstractSet<E> implements Set<E>{
   private final ConcurrentMap<E, Object> theMap;

   private static final Object dummy = new Object();

   public ConcurrentHashSet(){
      theMap = new ConcurrentHashMap<E, Object>();
   }

   @Override
   public int size() {
      return theMap.size();
   }

   @Override
   public Iterator<E> iterator(){
      return theMap.keySet().iterator();
   }

   @Override
   public boolean isEmpty(){
      return theMap.isEmpty();
   }

   @Override
   public boolean add(final E o){
      return theMap.put(o, ConcurrentHashSet.dummy) == null;
   }

   @Override
   public boolean contains(final Object o){
      return theMap.containsKey(o);
   }

   @Override
   public void clear(){
      theMap.clear();
   }

   @Override
   public boolean remove(final Object o){
      return theMap.remove(o) == ConcurrentHashSet.dummy;
   }

   public boolean addIfAbsent(final E o){
      Object obj = theMap.putIfAbsent(o, ConcurrentHashSet.dummy);
      return obj == null;
   }
}
MD Mohiuddin Ahmed
źródło
2
Podoba mi się pomysł użycia Boolean.TRUE zamiast obojętnego obiektu. Jest trochę bardziej elegancki. Możliwe jest również użycie wartości NULL, ponieważ byłoby ono dostępne w zestawie kluczy, nawet jeśli jest mapowane na wartość null.
Martin Kersten
2
@MartinKersten fyi, ConcurrentHashMap nie zezwala na wartości zerowe
Lauri Lehtinen,
2

Dlaczego nie użyć: CopyOnWriteArraySet z java.util.concurrent?

Shendor
źródło
6
Ponieważ CopyOnWriteArraySet kopiuje całą kolekcję w dowolnej mutacji stanu, co nie zawsze jest pożądane ze względu na wpływ na wydajność. Jest przeznaczony do pracy tylko w szczególnych przypadkach.
boneash