Skip to content

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 hash-based tree 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

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.
  • TreeSet when you need the elements sorted, a range of them, or the least and the greatest.
HashSet<String> tags = HashSet.of("java", "scala");
HashSet<String> more = tags.add("zio").remove("scala");
HashSet<String> common = tags.intersect(HashSet.of("scala", "kotlin"));
// more contains java and zio, common is HashSet(scala)

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

Costs

Operation Cost Note
contains effectively O(1) effectively O(1) (one hash lookup).
add effectively O(1) effectively O(1) (one hash lookup, then a path copy of the trie when the element is new).
remove effectively O(1) effectively O(1) (one hash lookup and a path copy of the trie).
union O(m) O(m) for a set of m elements, each an effectively O(1) insertion; this set or a HashSet argument is returned as is when the other side is empty.
intersect O(n + m) O(n + m) for a set of m elements (the smaller set is filtered against a hash set of the larger one).
diff O(n + m) O(n + m) for a set of m elements (a hash set of them, then one filter pass).
min O(n) O(n), every element compared once in natural order; on a TreeSet the least element in the comparator's order is head(), O(log n).
max O(n) O(n), every element compared once in natural order; on a TreeSet the greatest element in the comparator's order is last(), 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, then a hash insertion and an append to the insertion order when the element is new).
remove effectively O(1) effectively O(1) (one hash removal and one marker in the insertion order), amortised: when the markers outnumber the elements, the insertion order is rebuilt in O(n).
union O(m) O(m) for a set of m elements, each an effectively O(1) add(Object).
intersect O(n + m) O(n + m) for a set of m elements (a hash set of them, then the kept elements copied into a new set).
diff O(n + m) O(n + m) for a set of m elements (a hash set of them, then the kept elements copied into a new set).
min O(n) O(n), every element compared once in natural order; on a TreeSet the least element in the comparator's order is head(), O(log n).
max O(n) O(n), every element compared once in natural order; on a TreeSet the greatest element in the comparator's order is last(), O(log n).
head effectively O(1) effectively O(1) (the first element of the insertion order).
take effectively O(min(n, size - n)) effectively O(min(n, size - n)) (the smaller of the kept and the removed elements is inserted into or removed from the hash map; the insertion order is sliced). After removals, finding the cut also walks the insertion order from the nearer end past the removed elements' markers.
drop effectively O(min(n, size - n)) effectively O(min(n, size - n)), that of take(int).
Operation Cost Note
contains O(log n) O(log n) comparisons.
add O(log n) O(log n) (one lookup, then one insertion in the tree when the element is new).
remove O(log n) O(log n) (one deletion from the tree).
union O(m log(n + m)) O(m log(n + m)) for a set of m elements: a split and a join per node of elements when it is a TreeSet with the same comparator, otherwise one lookup and one insertion per element.
intersect O((n + m) log n) O((n + m) log n) for a set of m elements: a split and a join per node of elements when it is a TreeSet with the same comparator, otherwise a hash set of elements and the kept elements built into a new tree.
diff O((n + m) log n) O((n + m) log n) for a set of m elements: a split and a join per node of elements when it is a TreeSet with the same comparator, otherwise a hash set of elements and the kept elements built into a new tree.
min O(n) O(n), every element compared once in natural order; on a TreeSet the least element in the comparator's order is head(), O(log n).
max O(n) O(n), every element compared once in natural order; on a TreeSet the greatest element in the comparator's order is last(), O(log n).
head O(log n) O(log n) (the leftmost path of the tree).
take O(log n) O(log n) (one rank split of the tree).
drop O(log n) O(log n) (one rank split 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.

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.
  • 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.
  • union, intersect and diff are fast on two TreeSets with the same comparator. With different comparators, or another kind of set, they process the elements one by one.
  • TreeSet has no partitionMap.