Sets

Three sets with the same operations: add, remove, contains, union, intersect, diff, and the usual filter, map and fold. They differ in how they order their elements.

Type	Representation	Iteration order	Positional methods
HashSet	a compressed hash trie (CHAMP)	not defined	none
LinkedHashSet	a hash-based set that also records the insertion order	insertion order	yes
TreeSet	a sorted, balanced tree	the comparator's	yes

HashSet is the structure of the immutable HashSet of the Scala 2.13 collections library, which Scala 3 uses unchanged: a tree of nodes with up to 32 slots each, where five bits of a mix of the element's hash code pick the slot at each level. A node stores its elements inline, so an element costs no object of its own. Removing an element folds the tree back, so equal sets have the same shape whatever order their elements came in.

When to choose which

• HashSet by default.
• LinkedHashSet when the order the elements arrived in matters, for example to remove duplicates from a sequence and keep its order. A repeated element stays where it first appeared.
• TreeSet when you need the elements sorted, or the least and the greatest.

var tags   = HashSet.of("java", "scala");
var more   = tags.add("zio").remove("scala");                // HashSet<String>
var common = tags.intersect(HashSet.of("scala", "kotlin"));  // HashSet<String>
// more contains java and zio, common is HashSet(scala)

var seen     = LinkedHashSet.of("b", "a").add("c").add("a");  // LinkedHashSet<String>
var sorted   = TreeSet.of(5, 1, 4, 2);
var smallest = sorted.head();                                 // Integer
var firstTwo = sorted.take(2);                                // TreeSet<Integer>
// seen is LinkedHashSet(b, a, c), smallest is 1, firstTwo is TreeSet(1, 2)

Costs

HashSetLinkedHashSetTreeSet

Operation	Cost	Note
contains	effectively O(1)	effectively O(1): one hash lookup.
add	effectively O(1)	effectively O(1): one hash lookup; a new element also costs a copy of a few small arrays, the rest is shared with this set.
remove	effectively O(1)	effectively O(1): one hash lookup, then a copy of a few small arrays; the rest is shared with this set.
union	O(n + m)	O(n + m) for a set of m elements. A HashSet is merged with this set part by part, and a part only one of them holds is shared without being walked; another kind of set costs O(m), one effectively O(1) insertion per element. This set, or a HashSet argument, is returned as is when the other side is empty.
intersect	O(m)	O(m) for a set of m elements; O(min(n, m)) when it is a HashSet: the elements of the smaller set are checked against the larger one. Another kind of set is first copied into a hash set.
diff	O(m)	O(m) for a set of m elements, effectively O(1) each, as removeAll; O(n) when it is a HashSet, which is compared with this set part by part: a part of this set that the argument does not reach is kept whole, not walked. A LinkedHashSet larger than this set is not walked: each element of this set is looked up in it, O(n).
min	O(n)	O(n): every element is compared in its natural order. On a TreeSet, head() gives the least element in the set's own order in O(log n).
max	O(n)	O(n): every element is compared in its natural order. On a TreeSet, last() gives the greatest element in the set's own order in O(log n).

Operation	Cost	Note
contains	effectively O(1)	effectively O(1): one hash lookup.
add	effectively O(1)	effectively O(1): one hash lookup; a new element is also inserted and added at the end of the insertion order.
remove	effectively O(1)	effectively O(1): one hash removal, and the key taken out of the insertion order on the path from its root, on any version of the set.
union	O(m)	O(m) for a set of m elements, each an effectively O(1) add; this set, or a LinkedHashSet argument, is returned as is when the other side is empty.
intersect	O(n + m)	O(n + m) for a set of m elements; O(n) when it is a HashSet. The m elements are put in a hash set (unless they already are one), then every element of this set is checked against it and the kept ones are put in a new set.
diff	O(n + m)	O(n + m) for a set of m elements; O(n) when it is a HashSet. The m elements are put in a hash set (unless they already are one), then every element of this set is checked against it and the kept ones are put in a new set: the whole set is walked even to remove one element, which remove does in effectively O(1).
min	O(n)	O(n): every element is compared in its natural order. On a TreeSet, head() gives the least element in the set's own order in O(log n).
max	O(n)	O(n): every element is compared in its natural order. On a TreeSet, last() gives the greatest element in the set's own order in O(log n).
head	effectively O(1)	effectively O(1): the first element of the insertion order.
take	O(min(k, n - k))	O(min(k, n - k)) for k kept elements: the smaller side, kept or dropped, is added to or taken out of a hash map, and the rest is shared; the insertion order is cut along the paths from its root to the cut.
drop	O(min(k, n - k))	O(min(k, n - k)) for k dropped elements, as take.

Operation	Cost	Note
contains	O(log n)	O(log n): one walk down the tree, comparing with the comparator, not with equals.
add	O(log n)	O(log n): one lookup, then one insertion when the element is new.
remove	O(log n)	O(log n): one walk down the tree, then one deletion on the way back up when the element is present.
union	O(m log(n + m))	O(m log(n + m)) for a set of m elements. When it holds fewer than n elements, each is looked up, then inserted when new; otherwise they are sorted into a tree, which is cut and joined with this one. When elements is a TreeSet with an equal comparator (for a lambda, the same object), the cost is O(m log(n / m + 1)), m then being the smaller of the two sizes: the two trees are cut and joined, not rebuilt.
intersect	O(n + m log n)	O(n + m log n) for a set of m elements: each is looked up in this tree by the comparator, then one walk of this tree keeps the elements found and keeps whole every part that loses no element. When elements is a TreeSet with an equal comparator (for a lambda, the same object), the cost is O(m log(n / m + 1)), m then being the smaller of the two sizes: the two trees are cut and joined, not rebuilt.
diff	O(n + m log n)	O(n + m log n) for a set of m elements: each is looked up in this tree by the comparator. Up to eight elements found (fewer in a tree of fewer than 640 elements, and at least two) are deleted one by one, O(m log n): the tree off the deleted paths is shared. More are removed in one walk of this tree that keeps whole every part that loses no element. When elements is a TreeSet with an equal comparator (for a lambda, the same object), this tree is walked and each element it visits is looked up in the part of the other tree within its bounds, found by going down that tree: O(k log m) for the k nodes visited, at most n and at most about 2m log2 n. A part of this tree that loses no element is kept whole, and nothing of the other tree is copied.
min	O(n)	O(n): every element is compared in its natural order. On a TreeSet, head() gives the least element in the set's own order in O(log n).
max	O(n)	O(n): every element is compared in its natural order. On a TreeSet, last() gives the greatest element in the set's own order in O(log n).
head	O(log n)	O(log n): the smallest element is found by walking down the tree, with no comparison.
take	O(log n)	O(log n): the tree is cut at that position without visiting the elements, and the result shares the rest of the tree.
drop	O(log n)	O(log n): the tree is cut at that position without visiting the elements, and the result shares the rest of the tree.

Every method: complexity page.

Positional methods

LinkedHashSet and TreeSet have a defined order, so they have the methods that depend on it: head, last, tail, take, drop, zipWithIndex, sliding, grouped and their variants.

HashSet has none of them, because its order is not defined.

Ranges

A TreeSet cuts out the elements between two bounds in its comparator's order. The bounds need not be elements.

• rangeFrom(from) keeps the elements at or after from.
• rangeUntil(until) keeps those before until, and rangeTo(to) those at or before to.
• rangeFromUntil(from, until) keeps those at or after from and before until. It is empty when from is not before until; for from after until, java.util.TreeSet.subSet throws instead.

Each result is a TreeSet with the same comparator, built in O(log n): it shares the rest of the tree with the set it came from, and is that set itself when nothing is cut.

minAfter(element) is the least element at or after element, and maxBefore(element) the greatest strictly before it, both as an Option. iteratorFrom(start) walks the elements from start on, without building a range.

var scores = TreeSet.of(10, 20, 30, 40, 50);
var middle = scores.rangeFromUntil(20, 40);  // TreeSet<Integer>
var upTo30 = scores.rangeTo(30);             // TreeSet<Integer>
var next   = scores.minAfter(25);            // Option<Integer>
var before = scores.maxBefore(20);           // Option<Integer>
// middle is TreeSet(20, 30), upTo30 is TreeSet(10, 20, 30), next is Some(30), before is Some(10)

When nothing changes

An operation that changes nothing returns the set itself, not a copy: no allocation, and == tells you nothing changed.

• add of an element already there, remove of an absent one, and addAll, union, removeAll or diff that add or remove nothing.
• filter, reject, intersect and retainAll that keep every element; partition returns the set as the side that gets everything.
• replace of an absent element, or by the very object already there.
• take and drop of a LinkedHashSet or TreeSet, and the ranges of a TreeSet, that cut nothing.
• union or addAll on an empty set returns the argument when it is a set of the same kind.

An equal element is not the same object: replace(x, equalX) stores equalX, so the result is a new set.

Which of two equal elements stays

When the set and the argument hold equal elements that are different objects, add, addAll, union, intersect and retainAll keep the set's own. So a set united with, or intersected with, an equal set comes back unchanged.

When something changes, the parts of the tree or trie that do not are shared with the set, not copied: diff of a TreeSet copies only the paths to the elements it removes, and partition of a HashSet gives each side the parts whose elements all go to it.

Equality

Two sets are equal when they hold the same elements, compared with each element's equals. The kind does not matter: a HashSet, a LinkedHashSet and a TreeSet of the same elements are all equal, whatever the comparator of the TreeSet. a.equals(b) and b.equals(a) always agree, and equal sets have the same hashCode.

A TreeSet's comparator decides membership: contains, add, remove and the bulk operations. Equality is the one place where it does not. With a case-insensitive comparator, a TreeSet of "a" contains "A", and it equals a set of "a", not a set of "A".

Two TreeSets with the same comparator are compared in one walk, side by side. Against a HashSet or a LinkedHashSet, each of its elements is looked up in the tree.

A comparator can also tell apart two objects that are equal by equals; a TreeSet ordered by it can then hold both. Such a set is compared by counting: two sets are equal when they hold equal elements, each as many times.

Sharp edges

• Do not rely on the iteration order of a HashSet: it depends on the hashes and may change between versions. fold and reduce see the elements in that order, so give them an operation where the order does not matter.
• TreeSet.groupMap puts the values of each group in a HashSet: they need not be comparable, and the set's comparator orders elements, not values. groupBy keeps the comparator, since its groups hold elements.
• max() and min() use the natural order of the elements, which must be Comparable, and walk them all, even on a TreeSet. The least and greatest elements in a TreeSet's own order are head() and last(), in O(log n).
• TreeSet decides membership with its comparator, not equals, in contains, add, remove, union, intersect, diff, removeAll and retainAll, whatever the kind of the argument. intersect and retainAll keep each element of the set that the comparator equates with a given one, as the set's own object. equals compares the elements with their own equals (Equality).
• union, intersect and diff are fast on two TreeSets with the same comparator, and union, diff, containsAll and equals on two HashSets: they work on whole parts of the trees. With different comparators, or another kind of set, they process the elements one by one.
• HashSet.removeAll and diff remove the given elements one by one, effectively O(1) each, and compare a HashSet argument part by part. diff of a larger LinkedHashSet looks up each element of the set in it instead. intersect is cheap when the argument is a HashSet: the smaller set is checked against the larger.
• TreeSet has no partitionMap.