Only create a HashTrieSet if necessary.

If allow HashTrieSets with one element, you can get a degenerate tree that is six levels deep yet contains only one element by first building a large tree and then removing elements

1 files changed, 6 insertions, 1 deletions

diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala
index c60fdc3bf1..13e1269d46 100644
--- a/src/library/scala/collection/immutable/HashSet.scala
+++ b/src/library/scala/collection/immutable/HashSet.scala
@@ -236,7 +236,12 @@ object HashSet extends ImmutableSetFactory[HashSet] {
             Array.copy(elems, 0, elemsNew, 0, offset)
             Array.copy(elems, offset + 1, elemsNew, offset, elems.length - offset - 1)
             val sizeNew = size - sub.size
-            new HashTrieSet(bitmapNew, elemsNew, sizeNew)
+            // if we have only one child, which is not a HashTrieSet but a self-contained set like
+            // HashSet1 or HashSetCollision1, return the child instead
+            if (elemsNew.length == 1 && !elemsNew(0).isInstanceOf[HashTrieSet[_]])
+              elemsNew(0)
+            else
+              new HashTrieSet(bitmapNew, elemsNew, sizeNew)
           } else
             HashSet.empty[A]
         } else {