The issue with the performance heuristic for AbstractSet.removeAll() is described in JDK-6394757. We now believe this heuristic is incorrect and should be removed. The CollectionView nested class of ConcurrentHashMap has a similar heuristic in its removeAll() implementation. It should be removed too. See JDK-8218945 for a related case in ConcurrentSkipListSet.

This heuristic sometimes causes the "wrong" collection to be iterated. A consequence of this is that removeAll() might not provide a result that's the complement to retainAll().

See linked bugs for examples.