0

I have to iterate on a Set which is shared among multiple threads. Something like this code:

class MyObj{}
final static Set<MyObj> instances = Collections.synchronizedSet(new LinkedHashSet<MyObj>());
// returns the same object from the set if any, or add it if not found
public MyObj test2(MyObj a){

    if(instances.add(a))
            return a;

    for(MyObj o : instances){
        if(o.equals(a))
             return o;
    }

    throw new IllegalStateException("Impossible to reach this line");
}

I have read the javadoc for synchronizedSet, it states that:

It is imperative that the user manually synchronize on the returned set when iterating over it: 

Set s = Collections.synchronizedSet(new HashSet());
  ...   synchronized (s) {
  Iterator i = s.iterator(); // Must be in the synchronized block
  while (i.hasNext())
      foo(i.next());  
  }

Failure to follow this advice may result in non-deterministic behavior.

But, I also read on this answer that LinkedHashSet provides insertion-ordered iteration. And all a thread will do with my Set is

  • trying to add one new object
  • in case the add operation returns false, iterate over it to test the objects
  • never perform a clear or remove, the set can only grow.

With all these hypothesis, my guess is that I don't need to perform synchronization on the Set since even if another thread adds a new object while I am iterating over it, it will be at the end of the set and I will find the object I am looking for before reaching the insertion point.

Is this correct?

Community
  • 1
  • 1
Aldian
  • 2,592
  • 2
  • 27
  • 39
  • 1
    "my guess is that I don't need to perform synchronization on the Set since ..." I'll stop you there. You do. If you are making modifications to the set (e.g. adding elements), you *always* need to synchronize. – Andy Turner Sep 05 '16 at 16:06
  • 1
    Here's a [good example](http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html) of why you shouldn't make such assumptions. The moral of the story is that you can't reason about the implementation's inner workings just by what you can observe through its public API. If you want a lock-free collection, use a lock-free collection, not one that should be synchronized but isn't. – biziclop Sep 05 '16 at 16:16
  • I did not think about using a lock-free collection, thanks for the hint – Aldian Sep 05 '16 at 16:25
  • I am considering using ConcurrentSkipListSet. Looks promising – Aldian Sep 05 '16 at 16:52

1 Answers1

2

No, you must synchronize, as stated in the Javadoc:

Note that this implementation is not synchronized. If multiple threads access a linked hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.

If you have one thread iterating the set when another adds an element to it, you will get a ConcurrentModificationException.

The iterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException.

Andy Turner
  • 137,514
  • 11
  • 162
  • 243
  • I wish they did not enforce that fail fast behaviour. what is wrong with iterating over an array when nothing can happen but new objects at the end? – Aldian Sep 05 '16 at 16:18
  • @Aldian it's not a common-enough case to make it worth handling. – Andy Turner Sep 05 '16 at 16:21
  • 1
    @Aldian: Who’s to say “nothing can happen”? You created a synchronized wrapper around a `LinkedHashSet` whose `Iterator` doesn’t even know that it has been wrapped and thus, continues to protect itself against inconsistent state. As a side note, the current implementation of that iterator is actually a subtype of `LinkedHashMap$LinkedHashIterator` which has to deal with `LinkedHashMap`’s support of on-access reordering and even shares code with the ordinary `HashMap` which does not support insertion order traversal and hence, will invalidate the iterator on insertion. – Holger Sep 05 '16 at 18:29