JAVA / COLLECTIONS
TreeSet, NavigableSet and sorted uniqueness
Keep elements unique and sorted with TreeSet, predict which adds get rejected from the comparison rule, and query neighbours and ranges via NavigableSet.
What you will learn
- Read a TreeSet as a sorted tree: O(log n) lookups, iteration always ascending
- Predict rejected adds from compare(a,b)==0, never from equals()
- Answer nearest-match queries with floor, ceiling, higher and lower in log time
- Slice with headSet, tailSet and subSet, and treat the result as a live view
Understanding TreeSet, NavigableSet and sorted uniqueness
A TreeSet is a red-black tree, literally a TreeMap whose values are one shared dummy object, and it keeps its elements in ascending order at all times. Nothing records insertion order and no hash is computed; iteration is an in-order walk of the tree, which is why the order you get out is the ordering rule itself and not the history of your adds. The price is comparisons: add, contains and remove each descend about log2(n) levels, so a TreeSet loses to a HashSet on pure membership and pays you back in order and range queries.
The rule that catches people out is that TreeSet ignores equals and hashCode when deciding membership. It asks compareTo, or the Comparator you passed to the constructor, and treats compare(a, b) == 0 as "a and b are the same element": add returns false, the tree is untouched, and the object that arrived first is the one you keep. That makes the comparator a data-modelling decision rather than a sorting detail, because a comparator that reads one field is a declaration that every object sharing that field is one element, and the extras disappear with no exception and no warning.
NavigableSet is the interface that turns sortedness into questions a HashSet cannot answer. floor, ceiling, higher and lower find the nearest element at or around a value in log time, first/last/pollFirst/pollLast work the two ends, headSet/tailSet/subSet expose ranges, and descendingSet reverses direction. Those range and descending results are views over the same tree, not copies, so writing through them mutates the parent, reading them sees later parent changes, and adding a value outside a view's bounds is rejected with IllegalArgumentException.
import java.util.NavigableSet;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
NavigableSet<Integer> ports = new TreeSet<>();
for (int p : new int[] {8080, 22, 443, 8080, 80, 3306}) {
System.out.println("add " + p + " -> " + ports.add(p));
}
System.out.println(ports);
System.out.println("first=" + ports.first() + " last=" + ports.last());
System.out.println("floor(1000)=" + ports.floor(1000));
System.out.println("ceiling(1000)=" + ports.ceiling(1000));
System.out.println("higher(443)=" + ports.higher(443));
System.out.println("lower(22)=" + ports.lower(22));
System.out.println("headSet(443)=" + ports.headSet(443));
System.out.println("tailSet(443)=" + ports.tailSet(443));
System.out.println("subSet(80,8080)=" + ports.subSet(80, 8080));
System.out.println("descending=" + ports.descendingSet());
System.out.println("pollFirst=" + ports.pollFirst() + " left=" + ports);
}
}In a TreeSet the comparison rule defines identity as well as order, so two elements that compare equal are one element regardless of what equals() says.
Worked examples
The comparator decides what counts as a duplicate
A case-insensitive TreeSet collapses three distinct strings into one element while a natural-ordering TreeSet keeps all three.
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
Set<String> tags = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
tags.add("Java");
System.out.println(tags.add("JAVA"));
System.out.println(tags.add("java"));
System.out.println(tags);
System.out.println(tags.contains("jAvA"));
Set<String> exact = new TreeSet<>();
exact.add("Java");
exact.add("JAVA");
exact.add("java");
System.out.println(exact);
System.out.println("Java".equals("JAVA"));
}
}Example explained
Line 1String.CASE_INSENSITIVE_ORDER returns 0 for "Java" versus "JAVA", so both later adds return false.
Line 2The set still prints [Java]: add never replaces an element it considers equal, so the first insertion wins.
Line 3contains("jAvA") is answered by the same comparator, so a spelling the set never stored is reported as present.
Line 4The second set uses String.compareTo, where 'A' (65) sorts before 'a' (97), so all three variants are distinct elements.
Range views share the tree
subSet returns a live window over the same red-black tree, so writes flow both ways and out-of-range adds are refused.
import java.util.NavigableSet;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
NavigableSet<Integer> temps = new TreeSet<>();
for (int t : new int[] {-5, 0, 7, 12, 19, 24, 31}) {
temps.add(t);
}
NavigableSet<Integer> mild = temps.subSet(7, true, 24, false);
System.out.println("view=" + mild);
temps.add(15);
temps.add(40);
System.out.println("view after parent adds=" + mild);
mild.remove(12);
System.out.println("parent after view remove=" + temps);
try {
mild.add(30);
} catch (IllegalArgumentException e) {
System.out.println("rejected: " + e.getMessage());
}
}
}Example explained
Line 1subSet(7, true, 24, false) stores nothing of its own; it is bounds plus a reference to the parent's tree.
Line 215 falls inside the bounds so it shows up in the view, while 40 is added to the parent and stays invisible there.
Line 3mild.remove(12) deletes the node from the shared tree, which is why the parent loses 12 too.
Line 4Adding 30 through the view would put an element outside its own range, so the backing submap throws IllegalArgumentException.
Important notes
Default endpoint inclusivity is asymmetric: headSet(x) excludes x, tailSet(x) includes it, and subSet(from, to) is [from, to). Use the boolean overloads when the boundary matters, and note subSet with from greater than to throws IllegalArgumentException.
A comparator inconsistent with equals is legal but makes the set violate the Set contract as documented, so equals between a TreeSet and a HashSet holding the same objects can disagree.
Common mistakes
Writing Comparator.comparing(Player::score) and then wondering where players went: two players with the same score compare to 0, so only one per score survives and the rest are silently dropped. Chain .thenComparing(Player::name) to keep them distinct.
Assuming a TreeSet accepts anything a HashSet accepts: add(null) throws NullPointerException even on an empty set because TreeMap type-checks by comparing the element with itself, and an element whose class has no natural order throws ClassCastException on that very first add.
Mutating a field the ordering reads after the element is in the set: the object now sits in the wrong subtree, so contains and remove follow the comparison path into an empty branch and report it absent, leaving it stuck in the set.
Try it yourself
Change, predict, then run
Build a TreeSet<String> from the words of a sentence you split on spaces, then print subSet("a", "n") and ceiling("m") to find the first word from the back half of the alphabet. Rebuild the same set with String.CASE_INSENSITIVE_ORDER and report how many words disappeared.
Open the Java workspaceCheck your understanding
A TreeSet<Person> is created with Comparator.comparing(Person::lastName). You add Person("Ada", "Lovelace"), then Person("Grace", "Lovelace"), and Person.equals compares both names. What does the set hold afterwards?
- Only Ada Lovelace, because the comparator returned 0 and the second add was rejected
- Both people, because equals() reports them as different objects
- Only Grace Lovelace, because the later add replaces the element it matches
- Both people, but their relative iteration order is unspecified
Show answer
Membership in a TreeSet is decided by the comparator, so compare(...) == 0 means "already present": add returns false and the first object stays in the tree. Option 2 is tempting because TreeMap.put does overwrite the stored value, but in a TreeSet the element is the key and keys are never replaced, so Grace is discarded rather than stored; option 1 fails because equals() is never consulted for membership here.