RFR [8005953] Speedup construction of CopyOnWriteArraySet in special cases

Ivan Gerasimov ivan.gerasimov at oracle.com
Tue Apr 30 13:29:48 UTC 2013

Thanks, Jason!

>> The addAllAbsent() function has O(c.length^2) complexity, so
>> construction time quickly grows with the input size.
>> However, if we knew that c is a Set, we could construct the COWAS in
>> linear time.
> You have to be able to prove that the given Set uses the same equivalence relation as the COWAS.  Otherwise, it will fall apart you pass a SortedSet with a Comparator or an identity set.

I relied on what the documentation [1] says: "sets contain no pair of 
elements e1 and e2 such that e1.equals(e2)".
Further, [2] states: "the ordering maintained by a sorted set (whether 
or not an explicit comparator is provided) must be consistent with 
equals if the sorted set is to correctly implement the Set interface"

However you're right that if a class derived from Set is implemented 
inconsistently with equals (even though the documentation says it should 
not), the behavior of the constructor will change.

[1] http://docs.oracle.com/javase/7/docs/api/java/util/Set.html
[2] http://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html

>> And if the c was known to be another COWAS, we could simply clone the
>> underlying CopyOnWriteArrayList.
> That would be safe.
> Jason 		 	   		

More information about the core-libs-dev mailing list