Skip to content
notes.vinhnq.com

Search

Data Structures & AlgorithmsMid15 min read

Java Collections: TreeSet, TreeMap, Comparator and iterators

Review 10 cards
On this page

Data structures series: 1. Arrays, linked lists, stacks, queues · 2. List, Set, Map · 3. TreeMap, Comparator, iterators · 4. Inside ArrayList and HashMap

Part 2 stopped at HashSet and HashMap: fast, but unordered. This part covers ordered data (TreeSet, TreeMap, NavigableMap), defining an order with Comparable/Comparator, and iterating safely with Iterator. It ends with Lab 09 (managing club members with five kinds of collection) and a solution I actually ran; read part 2 first (List, Set, Map, equals/hashCode).

At a glance:

flowchart TD
  A{"What do you need?"} -->|"Fast key lookup"| B["HashMap O(1)"]
  A -->|"Order, nearest, range"| C["TreeMap O(log n)"]
  C --> D["floorEntry, ceilingKey, subMap"]
  C --> E["Duplicates by compareTo"]
  E --> F{"Which order?"}
  F -->|"Natural"| G["Comparable"]
  F -->|"Business"| H["Comparator"]
  I["Modify while iterating"] -->|"Via iterator"| J["iterator.remove, removeIf"]
  I -->|"Other path"| K["ConcurrentModificationException"]

1. TreeSet, TreeMap and NavigableMap

Key idea: TreeMap keeps its keys sorted at all times, at the cost of O(log n) per operation instead of O(1). Pick it when you need key order or “nearest key / keys in a range” questions.

TreeMap is a red-black tree (a self-balancing binary search tree, so it never degrades into a straight line). TreeSet is really a TreeMap that only uses the keys.

The order comes from one of two places:

  • The elements’ compareTo (natural ordering, so the elements must implement Comparable).
  • A Comparator passed to the constructor.

TreeMap implements NavigableMap, and that is the real reason to choose it: queries a HashMap simply can’t answer.

// Membership tier by total spend: each key is the threshold where a tier starts
NavigableMap<BigDecimal, String> tiers = new TreeMap<>();
tiers.put(BigDecimal.ZERO, "STANDARD");
tiers.put(new BigDecimal("5000000"), "SILVER");
tiers.put(new BigDecimal("20000000"), "GOLD");

tiers.floorEntry(new BigDecimal("7500000")).getValue();   // "SILVER": the largest key <= 7,500,000

// Events keyed by timestamp: fetch the ones inside a time window
NavigableMap<Long, String> events = new TreeMap<>();
events.subMap(from, true, to, false);   // [from, to)
events.headMap(t);                      // every key < t
events.tailMap(t, true);                // every key >= t
Method Returns
floorKey(k) / ceilingKey(k) the largest key ≤ k / the smallest key ≥ k (null if none)
lowerKey(k) / higherKey(k) the largest key < k / the smallest key > k
firstEntry() / lastEntry() the smallest / largest entry
pollFirstEntry() / pollLastEntry() removes and returns the smallest / largest entry
headMap, tailMap, subMap range views; changing a view changes the backing map
descendingMap() a reverse-order view

TreeSet has the matching set: floor, ceiling, lower, higher, headSet, tailSet, subSet, pollFirst.

null keys in HashMap, TreeMap and ConcurrentHashMap
  • HashMap allows one null key, and HashSet one null element.
  • TreeMap/TreeSet with natural ordering throw NullPointerException on a null key, because they have to call compareTo. They accept null only if the Comparator handles it, e.g. Comparator.nullsFirst(...).
  • ConcurrentHashMap forbids null for both keys and values.

2. Comparable and Comparator

Key idea: Comparable is the natural ordering written inside the class, one per class. Comparator is an ordering written outside it, for business-specific orders or classes you can’t modify.

  • Comparable<T> (compareTo): e.g. String alphabetically, Integer by value, LocalDate chronologically.
  • Comparator<T> (compare): write as many as you like, including for library classes.
// Natural ordering: lives inside the class
record Version(int major, int minor) implements Comparable<Version> {
    public int compareTo(Version o) {
        return Comparator.comparingInt(Version::major).thenComparingInt(Version::minor).compare(this, o);
    }
}

// External orderings: one per screen or use case
Comparator<Member> byAgeThenName = Comparator.comparingInt(Member::age)
        .thenComparing(Member::name)
        .thenComparingInt(Member::id);                      // final tie-breaker
Comparator<Product> byPriceDescNullsLast =
        Comparator.comparing(Product::price, Comparator.nullsLast(Comparator.reverseOrder()));
members.sort(byAgeThenName);

How to choose: one “obvious” order everyone agrees on (numbers, dates, versions) means Comparable. An order that depends on the business rule or the screen (price, name, score) means a Comparator; keep it out of compareTo.

The Javadoc recommends that the natural ordering be consistent with equals: a.compareTo(b) == 0 exactly when a.equals(b). Break that and TreeSet and HashSet give different answers for the same data (like the Member example in section 1). The traps of writing comparators (subtraction overflow, contract violations, null) are in Merge sort, quicksort and how Java sorts.

3. Iterator, ListIterator and fail-fast

Key idea: to change a collection while iterating, go through the iterator itself (iterator.remove(), ListIterator.add/set) or use removeIf. Change it any other way and a fail-fast iterator throws ConcurrentModificationException (CME), though not every time.

  • Iterator works on every Collection: hasNext, next, remove.
  • ListIterator exists only for List: it moves both ways, knows its position, and can add or replace elements right where it stands.
List<Integer> nums = new ArrayList<>(List.of(10, 20, 30));
ListIterator<Integer> it = nums.listIterator();
while (it.hasNext()) {
    int v = it.next();
    if (v == 20) it.add(25);      // inserts right after 20 without breaking the loop
    if (v == 30) it.set(31);      // replaces the element just returned by next()
}
// nums = [10, 20, 25, 31]
while (it.hasPrevious()) {        // walk back: 31, 25, 20, 10
    System.out.println(it.previousIndex() + ": " + it.previous());
}

Fail-fast works like this: the collection keeps a modCount counter (how many structural changes it has had). The iterator remembers its value at creation and compares on every next(); a mismatch throws CME. It is a best-effort bug detector, not a synchronization mechanism. Think of a door chime: if it rings, someone came in; if it doesn’t, that proves nothing.

Why fail-fast is only best effort: removing the second-to-last element

Exercises

Exercise 1: Lab 09: managing club members

Task (paraphrased): a Member class with id, name, age, whose natural order is age ascending, then name for equal ages. Then:

  1. ArrayList<Member>: add 5 members and print them.
  2. HashSet<Integer>: add the members’ IDs, try adding a duplicate ID, print the IDs.
  3. TreeSet<Member>: add the members to get a ranking by age and print it.
  4. HashMap<Integer, Integer>: bonus points by ID for 3 members, add 10 points to member 1 if present, print.
  5. TreeMap<Integer, String>: ID → name for every member, print it and look at the key order.

Hint: the task hides a trap in step 3. Try two members with the same name and age.

Solution to Exercise 1: code, JDK 21 output and notes
import java.util.*;

public class MemberLab {

    // record: immutable, equals/hashCode/toString generated from all three fields
    record Member(int id, String name, int age) implements Comparable<Member> {
        private static final Comparator<Member> ORDER = Comparator
                .comparingInt(Member::age)
                .thenComparing(Member::name)
                .thenComparingInt(Member::id);          // final tie-breaker

        Member {
            if (id <= 0) throw new IllegalArgumentException("id must be > 0");
            Objects.requireNonNull(name, "name");
            if (age < 0) throw new IllegalArgumentException("age must be >= 0");
        }

        @Override
        public int compareTo(Member other) {
            return ORDER.compare(this, other);
        }
    }

    public static void main(String[] args) {
        // 1. Sign-up list: keeps insertion order, allows duplicates
        List<Member> members = new ArrayList<>(List.of(
                new Member(3, "Chi", 22),
                new Member(1, "An", 25),
                new Member(5, "Binh", 22),
                new Member(2, "Dung", 30),
                new Member(4, "An", 25)));               // same name and age as id 1
        System.out.println("Registered: " + members);

        // 2. Unique IDs: Integer already has equals/hashCode
        Set<Integer> memberIds = new HashSet<>();
        for (Member m : members) memberIds.add(m.id());
        boolean added = memberIds.add(1);                // duplicate ID
        System.out.println("Add duplicate id 1 -> " + added + ", ids = " + memberIds);

        // 3. Ranking by age, then name, then id
        NavigableSet<Member> ranked = new TreeSet<>(members);
        System.out.println("Ranked:");
        ranked.forEach(m -> System.out.println("  " + m));
        System.out.println("Ranked size = " + ranked.size() + " (list size = " + members.size() + ")");

        // 4a. Bonus points: id -> points
        Map<Integer, Integer> pointMap = new HashMap<>();
        pointMap.put(1, 50);
        pointMap.put(3, 20);
        pointMap.put(5, 70);
        pointMap.computeIfPresent(1, (id, p) -> p + 10);   // only adds if id 1 exists
        pointMap.computeIfPresent(9, (id, p) -> p + 10);   // id 9 is absent: no-op
        System.out.println("Points: " + pointMap);

        // 4b. id -> name, always iterated by ascending id
        NavigableMap<Integer, String> idNameMap = new TreeMap<>();
        for (Member m : members) idNameMap.put(m.id(), m.name());
        System.out.println("Id -> name: " + idNameMap);
        System.out.println("First id >= 3: " + idNameMap.ceilingEntry(3));

        // Experiment: drop the id tie-breaker and the TreeSet swallows a member
        Comparator<Member> byAgeThenName = Comparator.comparingInt(Member::age).thenComparing(Member::name);
        Set<Member> lossy = new TreeSet<>(byAgeThenName);
        lossy.addAll(members);
        System.out.println("Without id tie-breaker: size = " + lossy.size());
    }
}

Output on JDK 21:

Registered: [Member[id=3, name=Chi, age=22], Member[id=1, name=An, age=25], Member[id=5, name=Binh, age=22], Member[id=2, name=Dung, age=30], Member[id=4, name=An, age=25]]
Add duplicate id 1 -> false, ids = [1, 2, 3, 4, 5]
Ranked:
  Member[id=5, name=Binh, age=22]
  Member[id=3, name=Chi, age=22]
  Member[id=1, name=An, age=25]
  Member[id=4, name=An, age=25]
  Member[id=2, name=Dung, age=30]
Ranked size = 5 (list size = 5)
Points: {1=60, 3=20, 5=70}
Id -> name: {1=An, 2=Dung, 3=Chi, 4=An, 5=Binh}
First id >= 3: 3=Chi
Without id tie-breaker: size = 4

Notes:

  • HashSet<Integer> needs no custom equals/hashCode. The task hints that you have to write them, but Integer already has both. You only care when you put Member itself into a HashSet, and the record generates them.
  • “Age, then name” as stated loses data. IDs 1 and 4 are both “An”, aged 25, so compareTo == 0 and the TreeSet silently keeps only one (last output line: size 4). The task never mentions this. The solution adds id as a final tie-breaker, which also makes the ordering consistent with the record’s equals.
  • “Add 10 points if present” is exactly what computeIfPresent does: one lookup, no containsKey + get + put. For “create with 10 points if absent”, use merge(1, 10, Integer::sum).
  • The TreeMap always prints in ascending ID order even though IDs were added as 3, 1, 5, 2, 4. A HashMap with small Integer keys may look ordered too, but that’s a coincidence (an Integer’s hash is its own value); don’t rely on it.
  • Declare NavigableSet/NavigableMap rather than Set/Map when you need ceilingEntry, headSet and friends.

What a senior would improve:

  • Keep Member immutable (a record, no setters). The task asks for setters, but changing the age of an element inside a TreeSet corrupts the tree (the element sits in the wrong place and contains returns false), exactly like mutating a HashMap key.
  • Don’t bake “by age” into compareTo if it’s just one screen’s ordering. A more sensible natural order is by id; the ranking uses its own Comparator (section 2).
  • If several threads add points concurrently, HashMap isn’t safe: use ConcurrentHashMap.merge, or better, let the database do it (UPDATE ... SET points = points + 10).

Remember

  • Explain why a TreeSet can “swallow” an element that isn’t equals, and how a tie-breaker fixes it.
  • Know when to pick TreeMap over HashMap, and write floorEntry/subMap for a tier table or a time window.
  • Know when to use Comparable and when to use Comparator.
  • Explain modCount and why fail-fast is only best effort.
  • Tell fail-fast, weakly consistent and snapshot iterators apart, and choose by read/write ratio.

Interview questions

Junior

What’s the difference between Comparable and Comparator, and when do you use each?

Comparable is the natural ordering inside the class (one per class); Comparator is an external ordering, and you can have many.

Comparable (compareTo) is what String, Integer and LocalDate use. Comparator (compare) works for classes you can’t modify. Implement Comparable for an obvious order; use Comparator.comparing(...).thenComparing(...) for orders that depend on the business rule or the screen.

How is TreeMap different from HashMap, and when do you pick TreeMap?

HashMap is an O(1) hash table with no order; TreeMap is an O(log n) red-black tree that keeps keys sorted and answers nearest-key and range queries.

HashMap allows one null key. TreeMap compares keys with compareTo/a comparator (natural ordering rejects a null key) and offers NavigableMap queries such as floorEntry, ceilingKey, subMap and headMap. Pick TreeMap when you need sorted keys or “nearest key / keys in a range”, for example tiers by spending or events in a time window; otherwise use HashMap.

Mid

You add two different objects to a TreeSet, yet size() is 1. Why?

Because a TreeSet detects duplicates with compareTo/the Comparator and never calls equals/hashCode.

If the ordering compares only some fields (say age, then name), two objects with different ids but the same age and name compare as 0, and the second is silently dropped. Fix it with a final tie-breaker (thenComparingInt(Member::id)) so the ordering is consistent with equals.

What’s the difference between fail-fast and fail-safe iterators?

Fail-fast iterators throw ConcurrentModificationException when the collection is changed outside the iterator; “fail-safe” ones don’t throw, but that’s an informal name for two different kinds.

Fail-fast (ArrayList, HashMap) checks modCount, best effort only. Weakly consistent (ConcurrentHashMap) never throws and may or may not see newer changes. Snapshot (CopyOnWriteArrayList) iterates over a copy, and every write copies the whole array. Choose by read/write ratio and whether multiple threads are involved.

Senior

Removing the second-to-last element of an ArrayList inside a for-each doesn’t throw ConcurrentModificationException. Why?

Because hasNext() returns false before next() gets to check modCount, so the loop stops early and the last element is skipped.

The ArrayList iterator’s hasNext() is just cursor != size. Removing the second-to-last element shrinks size to exactly cursor. No exception, but the code is wrong. The lesson: fail-fast is best effort; use iterator.remove() or removeIf.

What happens if you mutate an element that’s inside a TreeSet, or a HashMap key?

The structure doesn’t know the field changed, so the element “disappears”: lookups miss it, removal fails, and no exception is thrown.

  • HashMap/HashSet: the element still sits in the bucket from the old hash, so get/contains compute the new bucket and miss it.
  • TreeSet/TreeMap: the element is in the wrong place in the tree, searches go down the wrong branch, and remove fails too.
  • Result: lost data and a memory leak. The fix is to use only immutable objects (records, String) as keys and set elements; if you must change one, remove it, change it, and add it back.

Useful phrases for interviews

  • “A TreeSet decides uniqueness with compareTo, so my comparator needs a final tie-breaker.”
  • “I’d use a TreeMap here because I need range queries, like the largest key below a threshold.”
  • “ConcurrentHashMap iterators are weakly consistent: they never throw, but they may not see the latest writes.”
  • “I’d use computeIfPresent here, because it only touches the entry if it’s already there.”
  • “Two different members compared as equal, so the TreeSet silently dropped one of them.”
  • “The natural order is one per class; anything screen-specific goes into a separate comparator.”
  • “Fail-fast is best effort, so not seeing an exception doesn’t prove the loop is correct.”
  • “A NavigableMap lets me ask for the largest key at or below a value, which a HashMap simply can’t do.”

Notes based on the Fundamentals of Backend course (Ronin Engineer) and the Hỏi Dân IT Java Core material, plus my own research, rewritten in my own words.