Sets, TreeMap and ordering

A Set promises uniqueness and nothing else. Three implementations keep that promise three different ways, and the choice between them is a choice about ordering — and about which equality the structure uses, which is where the surprising bugs live. This lesson is the three sets, the red-black tree under two of the JDK's most useful structures, the comparator contract and the exception you get for breaking it, and a comparator that quietly deleted half a dataset.

#Three sets

HashSet is a HashMap with the values ignored — literally: it holds a HashMap<E, Object> and stores a shared dummy PRESENT object as every value, so a HashSet entry costs the same 32-byte node as a map entry. O(1) add, remove, contains; no ordering; uses hashCode and equals. Everything in the HashMap lesson applies.

LinkedHashSet is a HashSet over a LinkedHashMap, which threads a doubly linked list through its entries, so iteration follows insertion order. Same complexity, 8 more bytes per entry. Use it whenever a set will be displayed, serialised or compared by order — a deterministic order costs almost nothing and saves a flaky test.

TreeSet is a TreeMap with dummy values, and TreeMap is a red-black tree. O(log n) add, remove, contains; iteration is sorted; uses compareTo or a Comparator — and never hashCode or equals. It is a NavigableSet, which is the reason to use it: first(), last(), floor(x), ceiling(x), headSet(x), tailSet(x), subSet(a, b). "All timestamps between t1 and t2" in a TreeSet<Instant> is one call.

#Under the hood: the red-black tree

A TreeMap.Entry holds a key, a value, left, right and parent references, and a colour bit: 40 bytes with compressed references. The tree is a binary search tree kept approximately balanced by the red-black rules (no two red nodes in a row; every path from the root has the same number of black nodes), which bound its height at 2 × log₂(n + 1). A lookup in a million-entry TreeMap is at most about 40 comparisons, each a compareTo call and a pointer chase, which is why a TreeMap lookup is typically ten to fifty times slower than a HashMap's and why you choose it for floorKey and subMap, not for get.

Insertion walks down to a leaf position, links the new red node, then rotates and recolours up the path to restore the rules: at most two rotations. The Entry.parent pointer is what makes successor() O(1) amortised, which is what makes in-order iteration cheap and higher(x) a walk rather than a search. Range views (subMap, headSet) are live views that hold two bounds and walk the same tree; they cost nothing to create and reflect later changes.

The comparator is called on every step of every operation, so a Comparator that allocates, boxes, or calls toLowerCase() runs a million times to build a million-entry set. Comparator.comparing(key) extracts the key on each comparison; if extraction is expensive, precompute it into the element.

#Comparable and Comparator

A type's natural order is its compareTo. String, numbers, LocalDate and enums have one. A Comparator is an external order — you can have as many as you want:

record Employee(String name, String dept, int salary) {}
 
Comparator<Employee> bySalaryDesc = Comparator.comparingInt(Employee::salary).reversed();
Comparator<Employee> byDeptThenName = Comparator.comparing(Employee::dept)
                                                .thenComparing(Employee::name);
Comparator<Employee> nullsLast = Comparator.comparing(Employee::dept, Comparator.nullsLast(Comparator.naturalOrder()));
 
employees.sort(byDeptThenName);
Set<Employee> ranked = new TreeSet<>(bySalaryDesc);

The Comparator.comparing family replaced hand-written comparators. Write one only for logic the combinators cannot express.

Rules for compareTo (JLS calls it a total order): antisymmetric (sgn(a.compareTo(b)) == -sgn(b.compareTo(a))), transitive, consistent across calls, and it must not throw on any two non-null instances. Compare fields with Integer.compare(a, b), not a - b (overflow: Integer.MIN_VALUE - 1 is positive), and Double.compare, not < (NaN compares false both ways, breaking antisymmetry). Break a rule and TimSort, which List.sort and Arrays.sort use, detects the inconsistency and throws IllegalArgumentException: Comparison method violates its general contract! — but only on inputs large and disordered enough to reach the merge step that checks, so the bug sleeps in tests and wakes on production data.

#The consistency rule

TreeSet decides "already present" by compareTo() == 0. HashSet decides it by hashCode and equals. If those disagree for some pair of objects, the two sets hold different contents for the same input:

Set<BigDecimal> hash = new HashSet<>(List.of(new BigDecimal("2.0"), new BigDecimal("2.00")));
Set<BigDecimal> tree = new TreeSet<>(List.of(new BigDecimal("2.0"), new BigDecimal("2.00")));
hash.size();   // 2 — equals compares scale
tree.size();   // 1 — compareTo ignores scale

Neither is wrong; they use different definitions. The Comparable Javadoc recommends consistency with equals and warns of exactly this. When you write a comparator for a TreeSet, ask: does it consider distinct objects equal? If yes, the set will drop them. Comparator.comparing(Employee::dept) in a TreeSet<Employee> keeps one employee per department.

#Walkthrough: the export that lost 4,000 customers

A reporting job wanted customers sorted by signup date, deduplicated by id. Someone wrote Set<Customer> sorted = new TreeSet<>(Comparator.comparing(Customer::signedUp)); sorted.addAll(customers); and exported sorted. The export had 6,000 rows; the source had 10,000.

1. TreeSet.add calls the comparator to find the position. Two customers who signed up on the same day compare equal, compareTo() == 0, and the tree treats the second as already present: add returns false and drops it.
2. Bulk signups from a marketing campaign put hundreds of customers on the same day. Each day kept exactly one. Nothing threw; the set did what a set does.
3. The unit test used four customers on four different days and passed. The integration test used production-like data and nobody read its row count.
4. The fix is two steps, not one: deduplicate by the identity you mean (LinkedHashSet on a Customer with equals by id, or toMap(Customer::id, c -> c, (a, b) -> a)), then sort the result with List.sort. Or make the comparator total: comparing(Customer::signedUp).thenComparing(Customer::id), so no two distinct customers tie.

A TreeSet with a comparator that ties is a deduplicator by that comparator. Sometimes that is the intent; here it silently was not.

#Set operations

Set<String> a = new HashSet<>(List.of("x", "y", "z"));
Set<String> b = Set.of("y", "z", "w");
 
Set<String> union = new HashSet<>(a); union.addAll(b);
Set<String> intersection = new HashSet<>(a); intersection.retainAll(b);
Set<String> difference = new HashSet<>(a); difference.removeAll(b);
boolean subset = b.containsAll(a);

retainAll/removeAll mutate the receiver; copy first. AbstractSet.removeAll has a documented quirk: if the argument is larger than the receiver it iterates the receiver and calls contains on the argument, otherwise it iterates the argument and calls remove on the receiver — which means passing a List as the argument can turn an O(n) operation into O(n × m), because List.contains is a scan. Pass sets to set operations.

#EnumSet

For enum elements, EnumSet is a bit vector: EnumSet.of(MONDAY, FRIDAY), EnumSet.allOf(Day.class), EnumSet.range(MONDAY, FRIDAY). With up to 64 constants it is a single long (RegularEnumSet); beyond that a long[] (JumboEnumSet). contains is a shift and a mask, addAll is an OR, iteration is in declaration order, and memory is a word. There is no reason to use HashSet<Day>. EnumMap is the matching map — an array indexed by ordinal.

#Choosing

#Try it yourself

record P(String name, int age) {}
List<P> ps = List.of(new P("a", 30), new P("b", 30), new P("a", 30), new P("c", 25));
Set<P> hs = new HashSet<>(ps);
Set<P> ts = new TreeSet<>(Comparator.comparingInt(P::age));
ts.addAll(ps);
System.out.println(hs.size() + " " + ts.size());

#Misconceptions

• "TreeSet is a sorted HashSet." It is a red-black tree that never calls hashCode or equals; membership is compareTo() == 0. Two different structures with two different definitions of "same".
• "A comparator that never returns 0 is safe because nothing ties." Two equal elements then compare as each greater than the other, which breaks antisymmetry and eventually throws from TimSort.
• "removeAll is always fast on a HashSet." With a List argument larger than the set, it becomes O(n × m) through List.contains. Pass a set.
• "Sorting is what TreeSet is for." Sorting once at the end is cheaper. TreeSet is for maintaining order under inserts and for range queries.
• "EnumSet is a convenience." It is a bit vector: a word of memory and single-instruction operations. HashSet<Day> is 32 bytes per entry and a hash per lookup for the same job.

#Going deeper

• TreeMap source: put, fixAfterInsertion and successor, forty lines each, and the class comment citing Cormen et al. for the algorithm.
• Comparable and Comparator Javadoc, the paragraphs on consistency with equals.
• java.util.TimSort, and the mergeLo/mergeHi methods where the contract check lives.
• AbstractSet.removeAll Javadoc, the note on argument size, and JDK bug 6394757 which it documents.
• RegularEnumSet and JumboEnumSet source: the whole class is a long and some bit operations.