687

HashSet is based on HashMap.

If we look at HashSet<E> implementation, everything is been managed under HashMap<E,Object>.

<E> is used as a key of HashMap.

And we know that HashMap is not thread safe. That is why we have ConcurrentHashMap in Java.

Based on this, I am confused that why we don't have a ConcurrentHashSet which should be based on the ConcurrentHashMap?

Is there anything else that I am missing? I need to use Set in a multi-threaded environment.

Also, If I want to create my own ConcurrentHashSet can I achieve it by just replacing the HashMap to ConcurrentHashMap and leaving the rest as is?

7
  • 2
    After looking at the API, if I were to guess I would say that it seems to come down to 2 factors, (1) avoiding having to create a class in Java API for every little bit of functionality needed (2) Providing convenience classes for more frequently used objects. I personally prefer LinkedHashMap and LinkedHashSet since they guarantee order is the same as insertion order, the only reason for using a set is to avoid duplication, often I still want to maintain insertion order.
    – Ali
    Aug 9, 2011 at 7:31
  • 1
    @Ali, I personally prefer LinkedHashMap and LinkedHashSet you will go far :)
    – bestsss
    Aug 9, 2011 at 20:54
  • 9
    A bit old question, but as it is the first result in Google, may be useful to know that ConcurrentSkipListSet already has the implementation of ConcurrentHashMap. See docs.oracle.com/javase/7/docs/api/java/util/concurrent/… Jun 13, 2013 at 16:18
  • 1
    What I saw from Java source ConcurrentSkipListSet is built on ConcurrentSkipListMap, which implements ConcurrentNavigableMap and ConcurrentMap. Jun 14, 2013 at 12:18
  • possible duplicate of is Java HashSet thread-safe for read only?
    – Nirro
    Nov 5, 2014 at 18:52

10 Answers 10

733

There's no built in type for ConcurrentHashSet because you can always derive a set from a map. Since there are many types of maps, you use a method to produce a set from a given map (or map class).

Prior to Java 8, you produce a concurrent hash set backed by a concurrent hash map, by using Collections.newSetFromMap(map)

In Java 8 (pointed out by @Matt), you can get a concurrent hash set view via ConcurrentHashMap.newKeySet(). This is a bit simpler than the old newSetFromMap which required you to pass in an empty map object. But it is specific to ConcurrentHashMap.

Anyway, the Java designers could have created a new set interface every time a new map interface was created, but that pattern would be impossible to enforce when third parties create their own maps. It is better to have the static methods that derive new sets; that approach always works, even when you create your own map implementations.

19
  • 5
    Am I right to say that if you create the set this way from ConcurrentHashMap, you lose the benefits you'd get from ConcurrentHashMap ?
    – Pacerier
    Nov 1, 2011 at 20:47
  • 21
    There are no benefits to lose. newSetFromMap's implementation is found starting on line 3841 in docjar.com/html/api/java/util/Collections.java.html. It's just a wrapper....
    – Ray Toal
    Nov 1, 2011 at 23:36
  • 6
    @Andrew, I think the motivation behind using a "ConcurrentSet" stems from not the API but rather the implementation - thread safety but without a universal lock - multiple concurrent reads for instance. Sep 13, 2012 at 16:07
  • 5
    ConcurrentSkipList has lots of (size) overhead and the lookups are slower.
    – eckes
    Jun 10, 2015 at 15:44
  • 8
    take care when using this approach, since some methods are not implemented correctly. Just follow the links: Collections.newSetFromMap creates a SetFromMap. e.g. the SetFromMap.removeAll method delegates to the KeySetView.removeAll, that inherits from ConcurrentHashMap$CollectionView.removeAll. This method is highly inefficient in bulk removing elements. imagine removeAll(Collections.emptySet()) traverses all elements in the Map without doing anything. Having a ConcurrentHashSet that is corretly implemented will be better in most cases.
    – benez
    Mar 1, 2018 at 9:50
126

Prior to Java 8:

Set<String> mySet = Collections.newSetFromMap(new ConcurrentHashMap<String, Boolean>());

Java 8 or greater:

ConcurrentHashMap.KeySetView<String, Boolean> mySet = ConcurrentHashMap.newKeySet();
3
  • 5
    As Ray Toal points out in his answer, the preferred way to this in 2021 is definitely ConcurrentHashMap.newKeySet() (which does a similar thing behind the scenes), as it's more succinct. Jan 26, 2021 at 6:14
  • this is thread-safe right? Dec 10, 2021 at 7:03
  • yes, it is thread safe
    – Serge Mask
    Oct 17 at 8:32
102

With Guava 15 you can also simply use:

Set s = Sets.newConcurrentHashSet();
3
  • 16
    This is always a nightmare. If you have a set or a map that does not indicate whether or not something is thread safe you find all kind of hazards and desasters happen in maintaince. I always would want a type that indicates thread safety for collections (or not). Dec 14, 2015 at 9:01
  • 13
    The method description is literally "Creates a thread-safe set backed by a hash map"
    – kichik
    Dec 14, 2015 at 16:33
  • 18
    As I said, there is a ConcurrentSet<E> missing. ConcurrentHashMap comes along with a ConcurrentMap interface to indicate this. This is the very same reason I always add this ConcurrentSet interface as well. Dec 15, 2015 at 9:59
84

Like Ray Toal mentioned it is as easy as:

Set<String> myConcurrentSet = ConcurrentHashMap.newKeySet();
1
  • 1
    This seems to require Java 8. Looking at implementation, this also seems to be just a wrapper of ConcurrentHashMap.
    – Mygod
    Oct 8, 2018 at 5:10
23

It looks like Java provides a concurrent Set implementation with its ConcurrentSkipListSet. A SkipList Set is just a special kind of set implementation. It still implements the Serializable, Cloneable, Iterable, Collection, NavigableSet, Set, SortedSet interfaces. This might work for you if you only need the Set interface.

4
  • 12
    Note that ConcurrentSkipListSet's elements should be Comparable
    – user454322
    Oct 2, 2014 at 10:14
  • If you need to extend from a Set that is concurrent, this is the only solution here that will work.
    – ndm13
    Dec 28, 2016 at 6:17
  • ConcurrentSkipListMap adds unnecessary performance penalty of having tree as base data structure, instead of using HashTable, even when you do not need sorting/navigation functionality. Sep 9, 2017 at 18:31
  • 6
    don't use ConcurrentSkipListSet unless you want a SortedSet. A usual operation like add or remove should be O(1) for a HashSet, but O(log(n)) for a SortedSet.
    – benez
    Mar 1, 2018 at 9:38
20

As pointed by this the best way to obtain a concurrency-able HashSet is by means of Collections.synchronizedSet()

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

This worked for me and I haven't seen anybody really pointing to it.

EDIT This is less efficient than the currently aproved solution, as Eugene points out, since it just wraps your set into a synchronized decorator, while a ConcurrentHashMap actually implements low-level concurrency and it can back your Set just as fine. So thanks to Mr. Stepanenkov for making that clear.

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

1
  • 26
    the synchronizedSet method just creates the decorator under Collection to wrap methods that could be thread-safe by synchronization the whole collection. But ConcurrentHashMap is implemented using non-blocking algorithms and "low-level" synchronisations without any locks of the whole collection. So wrapers from Collections.synchronized... is worse in multi-threads environments for performance reasons. Jan 1, 2015 at 19:53
14

You can use guava's Sets.newSetFromMap(map) to get one. Java 6 also has that method in java.util.Collections

6
  • it's available in java.utll.Collections and set of CHM is usually a bad thing anyways.
    – bestsss
    Aug 9, 2011 at 7:18
  • yeah, I noticed it is added in Java 6, so added it to the answer
    – Bozho
    Aug 9, 2011 at 7:19
  • The main this is that if it is ThreadSafe, and I really doubt that. Aug 9, 2011 at 7:22
  • @Talha, it's thread safe, however thread safety alone means nothing
    – bestsss
    Aug 9, 2011 at 7:25
  • Sometimes it means everything. Its shaldom a performance problem unless it is part of an algorithm which are usually implemented in a way that the need for concurrent mapping is minimized. Dec 14, 2015 at 9:03
8
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;
   }
}
2
  • 3
    I like the idea to use Boolean.TRUE instead of an dummy object. It is a little bit more elegant. Also using NULL is also possible since it would be available in the key set even if mapped to null. Dec 14, 2015 at 9:05
  • 3
    @MartinKersten fyi, ConcurrentHashMap doesn't allow null values Jan 13, 2016 at 19:19
2

Why not use: CopyOnWriteArraySet from java.util.concurrent?

3
  • 15
    Because CopyOnWriteArraySet copies the entire collection on any state mutation, which is not always wanted due to the performance impact. It's designed to work only in special cases.
    – boneash
    Jan 16, 2017 at 14:59
  • Additionally CopyOnWriteArraySet.contains() has a run-time of O(n) (has to check ever entry) where as HashSet/HashMap has O(1).
    – Robert
    Dec 1, 2020 at 12:02
  • because this works only one way: if you're reading data owned/managed by another thread. if you need to pass data to that thread, you'd have to additionally update its atomic ref to updated array - but that makes little sense
    – mantrid
    Feb 23, 2021 at 18:10
0

We have ConcurrentHashSet in io.vertx which can be used against java.util ConcurrentHashMap. https://www.javadoc.io/static/io.vertx/vertx-core/3.0.0/io/vertx/core/impl/ConcurrentHashSet.html

1
  • 1
    Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
    – jv-k
    Jan 18 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.