Java TreeSet
›Short versionOpen if you only have a minute.
- TreeSet keeps elements sorted. add, remove, and contains are O(log n).
- Ordering is natural Comparable order, or the Comparator passed to the constructor.
- Comparison returning 0 means the element is already present. equals is not consulted first.
- The comparator should be consistent with equals: compare(a, b) == 0 exactly when a.equals(b).
- An inconsistent comparator still runs. The set then breaks the Set contract and silently drops elements.
- first, last, floor, ceiling, and range views are the reason to pay the log n cost. Natural order rejects null.
A is the set you choose when iteration must be sorted, or when you ask for the neighbor of a value. Each update pays . A hash set is cheaper when those ordered questions never come up.
The ordering is a , including the natural order a class provides through Comparable. Inside the tree, that ordering decides membership.
When comparison and equals disagree
is the contract that keeps TreeSet honest as a Set. The sorted-set specification says the ordering must be consistent with equals if the set is to implement Set correctly. The tree will still insert and search if you ignore that. It will treat compare == 0 as identity.
People hit this with a comparator on one field of a larger object. Two employees with the same badge number, compared only by badge, collapse into one entry. equals, if it includes the name, would have kept both. The bug is quiet: add returns false, and no exception names the mismatch.
and range views read the same order. A range view is backed by the set, so removing from the view removes from the set. A does not belong in a naturally ordered tree.
Age is a poor identity
record Person(String name, int age) {}
Set<Person> byAge = new TreeSet<>(Comparator.comparingInt(Person::age));
byAge.add(new Person("Ada", 30));
byAge.add(new Person("Grace", 30)); // compare == 0, rejected
byAge.size(); // 1
NavigableSet<Integer> scores = new TreeSet<>();
scores.add(85);
scores.add(92);
scores.ceiling(90); // 92, O(log n)You need one entry per person, still ordered by age, and two people can share an age. How should the comparator finish the comparison?
Break ties with a unique field. comparingInt(Person::age).thenComparing(Person::name) returns 0 only when both age and name match. Then compare == 0 lines up with a record’s equals, and both 30-year-olds stay in the set, in age order.