[concurrency-interest] Race conditions in concurrent collections

Martin Buchholz Martin.Buchholz at Sun.COM
Sat Sep 24 17:03:14 EDT 2005

Doug Lea wrote:
> Martin Buchholz wrote:
>>One possible strategy for implementing Set.equals would be
>>new HashSet(this).equals(new HashSet(other));
>>which at one stroke eliminates concurrency issues 
> Although this places the burden on the HashSet(Collection c)
> constructor, which is not specified to do anything special
> in the face of concurrent modifications of "c" (and in fact
> is likely to fail).

Hmmmm.  In the current implementation, this eventually reduces
to a standard iterator loop over "c"

	Iterator<? extends E> e = c.iterator();
	while (e.hasNext()) {

If "c" is not a concurrent collection, then concurrent modification
is simply not supposed to work, and users should expect
ConcurrentModificationException (or worse).

If "c" *is* a concurrent collection, then our implementations in
j.u.c. try to not have next() fail when hasNext() has just
succeeded, but I don't think we promise that.  Supposing we *did*
promise that, then
new HashSet(c)
would always give a "reasonable" result when c is a concurrent
collection, and cannot be expected to give a reasonable result
when c is not.

We could of course add a
try {...} catch (NoSuchElementException) {...}
to handle concurrently modified collections where next() might fail.

Unfortunately, if we implemented equals(Object) using this strategy,
we could still have equals return true when the two collections
never contained the same elements.  Indeed, there is no way to
get all the elements in a concurrent collection in such a way that
the returned elements represent a snapshot of a particular point in
time, and so there is in general no way to implement an intuitive
equals() method.  At least, if both collections are quiescent, then
c.equals(other) should give the expected result.  That is hard
to specify in the javadoc, because it depends on cooperation between two
unknown collection class implementations.


More information about the Concurrency-interest mailing list