I remember looking at this bug back in 2005 and being afraid to touch it. The size-based algorithm does feel kludgy but it *is* specified, and changing that is too incompatible - it would have been rejected at that time.
I have a lot of sympathy for Alan's insistence on keeping the optimization for e.g. hashMap.removeAll(otherHashMap). Java has achieved success via judicious cheating. The collection framework was so appealing that any class that came "close enough" to implementing a spec was given that type in the type system. (I'm the author of a collection class that pragmatically cheats a little - no one has ever complained). It is when you operate on two collection classes (via removeAll, containsAll, equals) that have differing semantics that the cheating becomes most apparent and you get into trouble the most. We could lower user expectations in the spec. Other programming environments allow parameterization of membership semantics, e.g. C++ std::unordered_map. Java understandably chose not to do that, and it resulted in some shoe-horning that we have to live with. it would be interesting to see if an alternative set of collection classes was written that focused on flexibility and correctness. In the real world, most such alternatives focused on performance, I think.
