Warum gibt es kein ConcurrentHashSet gegen ConcurrentHashMap?

537

HashSet basiert auf HashMap.

Wenn wir uns die HashSet<E>Implementierung ansehen , wird alles unter verwaltet HashMap<E,Object>.

<E>wird als Schlüssel von verwendet HashMap.

Und wir wissen, dass HashMapdas nicht threadsicher ist. Deshalb haben wir ConcurrentHashMapin Java.

Aufgrund dessen bin ich verwirrt, warum wir kein ConcurrentHashSet haben, das auf dem basieren sollte ConcurrentHashMap.

Fehlt mir noch etwas? Ich muss Setin einer Multithread-Umgebung verwenden.

Wenn ich meine eigenen erstellen möchte, ConcurrentHashSetkann ich dies erreichen, indem ich einfach das HashMapto ersetze ConcurrentHashMapund den Rest unverändert lasse?

Talha Ahmed Khan
quelle
2
Wenn ich mir die API anschaue, würde ich sagen, dass es sich anscheinend um zwei Faktoren handelt: (1) Vermeiden, dass eine Klasse in der Java-API für jede erforderliche Funktionalität erstellt werden muss. (2) Bereitstellen von Convenience-Klassen für häufiger verwendete Objekte. Ich persönlich bevorzuge LinkedHashMap und LinkedHashSet, da sie garantieren, dass die Reihenfolge mit der Einfügereihenfolge identisch ist. Der einzige Grund für die Verwendung eines Satzes besteht darin, Doppelarbeit zu vermeiden. Oft möchte ich die Einfügereihenfolge beibehalten.
Ali
1
@Ali, ich persönlich bevorzuge LinkedHashMap und LinkedHashSet, du wirst weit gehen :)
Bests
9
Eine etwas alte Frage, aber da es das erste Ergebnis in Google ist, kann es hilfreich sein zu wissen, dass ConcurrentSkipListSet bereits die Implementierung von ConcurrentHashMap hat. Siehe docs.oracle.com/javase/7/docs/api/java/util/concurrent/…
Igor Rodriguez
1
Was ich aus der Java-Quelle gesehen habe, ConcurrentSkipListSetbaut darauf auf ConcurrentSkipListMap, was ConcurrentNavigableMapund implementiert ConcurrentMap.
Talha Ahmed Khan

Antworten:

581

Es gibt keinen eingebauten Typ für, ConcurrentHashSetda Sie einen Satz immer von einer Karte ableiten können . Da es viele Arten von Karten gibt, verwenden Sie eine Methode, um einen Satz aus einer bestimmten Karte (oder Kartenklasse) zu erstellen.

Vor Java 8 erstellen Sie mithilfe von einen gleichzeitigen Hash-Satz, der von einer gleichzeitigen Hash-Map unterstützt wird Collections.newSetFromMap(map)

In Java 8 (von @Matt hervorgehoben) können Sie eine gleichzeitige Hash-Set- Ansicht über erhalten ConcurrentHashMap.newKeySet(). Dies ist etwas einfacher als das alte, bei newSetFromMapdem Sie ein leeres Kartenobjekt übergeben mussten. Aber es ist spezifisch für ConcurrentHashMap.

Wie auch immer, die Java-Designer hätten jedes Mal, wenn eine neue Kartenschnittstelle erstellt wurde, eine neue Set-Schnittstelle erstellen können, aber dieses Muster wäre unmöglich durchzusetzen, wenn Dritte ihre eigenen Karten erstellen. Es ist besser, die statischen Methoden zu haben, die neue Mengen ableiten. Dieser Ansatz funktioniert immer, auch wenn Sie Ihre eigenen Kartenimplementierungen erstellen.

Ray Toal
quelle
4
Kann ich zu Recht sagen, dass Sie ConcurrentHashMapdie Vorteile verlieren, die Sie erhalten , wenn Sie das Set auf diese Weise erstellen ConcurrentHashMap?
Pacerier
19
Es gibt keine Vorteile zu verlieren. newSetFromMapDie Implementierung finden Sie ab Zeile 3841 in docjar.com/html/api/java/util/Collections.java.html . Es ist nur eine Verpackung ...
Ray Toal
4
@ Andrew, ich denke, die Motivation für die Verwendung eines "ConcurrentSet" beruht nicht auf der API, sondern auf der Implementierung - Thread-Sicherheit, aber ohne universelle Sperre - beispielsweise mehreren gleichzeitigen Lesevorgängen.
Ustaman Sangat
5
ConcurrentSkipList hat viel (Größen-) Overhead und die Suchvorgänge sind langsamer.
eckes
3
Seien Sie vorsichtig, wenn Sie diesen Ansatz verwenden, da einige Methoden nicht korrekt implementiert sind. Folgen Sie einfach den Links: Collections.newSetFromMaperstellt eine SetFromMap. zB SetFromMap.removeAlldelegiert die Methode an die KeySetView.removeAll, die von erbt ConcurrentHashMap$CollectionView.removeAll. Diese Methode ist beim Entfernen von Massenelementen äußerst ineffizient. Stellen Sie sich vor, Sie removeAll(Collections.emptySet())durchqueren alle Elemente im, Mapohne etwas zu tun. Mit ein , ConcurrentHashSetdie corretly umgesetzt wird , wird in den meisten Fällen besser sein.
Benez
104
Set<String> mySet = Collections.newSetFromMap(new ConcurrentHashMap<String, Boolean>());
Serge Maske
quelle
79

Mit Guava 15 können Sie auch einfach verwenden:

Set s = Sets.newConcurrentHashSet();
kichik
quelle
12
Das ist immer ein Albtraum. Wenn Sie ein Set oder eine Karte haben, die nicht angibt, ob etwas threadsicher ist oder nicht, finden Sie alle Arten von Gefahren und Katastrophen in der Wartung. Ich würde immer einen Typ wollen, der die Thread-Sicherheit für Sammlungen anzeigt (oder nicht).
Martin Kersten
11
Die Methodenbeschreibung lautet wörtlich "Erstellt einen thread-sicheren Satz, der von einer Hash-Map unterstützt wird"
kichik
16
Wie gesagt, es fehlt ein ConcurrentSet <E>. ConcurrentHashMap wird mit einer ConcurrentMap-Schnittstelle geliefert, um dies anzuzeigen. Dies ist der gleiche Grund, warum ich immer auch diese ConcurrentSet-Schnittstelle hinzufüge.
Martin Kersten
35

Wie Ray Toal erwähnt hat, ist es so einfach wie:

Set<String> myConcurrentSet = ConcurrentHashMap.newKeySet();
BullyWiiPlaza
quelle
1
Dies scheint Java 8 zu erfordern. In Bezug auf die Implementierung scheint dies auch nur ein Wrapper von zu sein ConcurrentHashMap.
Mygod
20

Es sieht so aus, als würde Java mit seinem ConcurrentSkipListSet eine gleichzeitige Set-Implementierung bereitstellen . Ein SkipList-Set ist nur eine spezielle Art der Set-Implementierung. Es implementiert weiterhin die Schnittstellen Serializable, Cloneable, Iterable, Collection, NavigableSet, Set und SortedSet. Dies funktioniert möglicherweise für Sie, wenn Sie nur die Set-Schnittstelle benötigen.

Mike Pone
quelle
12
Beachten Sie, dass ConcurrentSkipListSetdie Elemente sein solltenComparable
user454322
Wenn Sie von einem gleichzeitigen Set aus erweitern müssen, ist dies die einzige Lösung, die hier funktioniert.
ndm13
ConcurrentSkipListMap fügt unnötige Leistungseinbußen hinzu, wenn Baum als Basisdatenstruktur verwendet wird, anstatt HashTable zu verwenden, selbst wenn Sie keine Sortier- / Navigationsfunktion benötigen.
Ajeet Ganga
Verwenden ConcurrentSkipListSetSie es nur, wenn Sie eine möchten SortedSet. Eine übliche Operation wie Hinzufügen oder Entfernen sollte O (1) für a sein HashSet, aber O (log (n)) für a SortedSet.
Benez
16

Wie hier gezeigt, ist der beste Weg, um ein paralleles HashSet zu erhalten, der überCollections.synchronizedSet()

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

Das hat bei mir funktioniert und ich habe niemanden gesehen, der wirklich darauf hingewiesen hat.

BEARBEITEN Dies ist weniger effizient als die derzeit empfohlene Lösung, wie Eugene betont, da es Ihr Set nur in einen synchronisierten Dekorator einwickelt, während ein ConcurrentHashMapSet tatsächlich eine Parallelität auf niedriger Ebene implementiert und Ihr Set genauso gut unterstützen kann. Vielen Dank an Herrn Stepanenkov, der das klargestellt hat.

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

Nirro
quelle
16
Die synchronizedSetMethode erstellt lediglich den Dekorator unter Collection, um Methoden zu verpacken, die durch Synchronisieren der gesamten Sammlung threadsicher sein können. Wird ConcurrentHashMapjedoch unter Verwendung nicht blockierender Algorithmen und "Low-Level" -Synchronisationen ohne Sperren der gesamten Sammlung implementiert . Wrapper von Collections.synchronized... sind in Multi-Thread-Umgebungen aus Leistungsgründen schlechter.
Eugene Stepanenkov
12

Sie können Guaven verwenden Sets.newSetFromMap(map), um eine zu bekommen. Java 6 hat diese Methode auch injava.util.Collections

Bozho
quelle
Es ist in java.utll verfügbar. Sammlungen und CHM-Sätze sind normalerweise sowieso eine schlechte Sache.
Bests
Ja, ich habe bemerkt, dass es in Java 6 hinzugefügt wurde, also fügte es der Antwort hinzu
Bozho
Das Wichtigste ist, dass es ThreadSafe ist, und das bezweifle ich wirklich.
Talha Ahmed Khan
@ Talha, es ist Thread-sicher, aber Thread-Sicherheit allein bedeutet nichts
Bests
Manchmal bedeutet es alles. Es ist ein Leistungsproblem, es sei denn, es ist Teil eines Algorithmus, der normalerweise so implementiert wird, dass die Notwendigkeit einer gleichzeitigen Zuordnung minimiert wird.
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
quelle
2
Ich mag die Idee, Boolean.TRUE anstelle eines Dummy-Objekts zu verwenden. Es ist etwas eleganter. Die Verwendung von NULL ist ebenfalls möglich, da es im Schlüsselsatz verfügbar wäre, selbst wenn es null zugeordnet wäre.
Martin Kersten
2
@ MartinKersten fyi, ConcurrentHashMap erlaubt keine Nullwerte
Lauri Lehtinen
2

Warum nicht: CopyOnWriteArraySet aus java.util.concurrent verwenden?

Shendor
quelle
6
Weil CopyOnWriteArraySet die gesamte Sammlung bei jeder Zustandsmutation kopiert, was aufgrund der Auswirkungen auf die Leistung nicht immer erwünscht ist. Es wurde entwickelt, um nur in besonderen Fällen zu funktionieren.
Boneash