If we have to distinguish between elements that are identical according to equals and hashCode, basically all optimizations in the union method are impossible. For example: when a union b has the same size as b, you nevertheless have to merge all elements of b into a since they might be different elements that just happen to be the same according to equals and hashCode, and you have to keep the original elements of a.

If that is the case, the current implementation of union that adds all elements sequentially is probably the best you can do. 

But using sets to store objects without meaningful equality not just relies on undocumented behavior, but is also pretty strange. If you define a class where some fields do not contribute to equality, you should expect that you can't use such a class as a key in a set. Note that classes with reference equality are not a problem. You will only ever get a problem when you define equality and then exclude some fields on purpose.

By the way: If we have to preserve undocumented behavior, we can not really optimize anything at all since somebody might rely on the fact that the result of empty union largeHashSet is ne largeHashSet, or x.filter(_ => true) ne x. You might as well freeze the entire collections library and only allow bugfixes then.

Regarding performance: I think you should not have to fall back to mutable data structures for good performance. Even outside purely functional programming there are lots of use cases where you want performance _and_ immutability: for example an actor that keeps some set of ids as its internal state and wants to be able to hand it out without performance penalty of making a copy.

And with the improvements for bulk operations scala.collections.immutable.HashSet should be very competitive with the mutable version in many scenarios. In many situations it will be *faster* than the mutable version because of structural sharing. 

Regarding the code duplication of HashSet and HashMap: the obvious way to get rid of that would be to have the Hash-Trie data structure as a separate class, and then wrap it in two different ways, once as a Set and once as a Map. Of course it has the overhead of the wrapper object, but that only matters for very small sets/maps. If we could make the whole thing more efficient in another place, maybe we could justify the additional indirection.

To my surprise this is already being done in the scala collections with TreeSet, where the RedBlackTree is a separate class that is wrapped in two ways in TreeSet and TreeMap. I think this would be a good way forward for the HashTrie as well, but obviously not for 2.11.