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 implementComparable). - A
Comparatorpassed 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
HashMapallows onenullkey, andHashSetonenullelement.TreeMap/TreeSetwith natural ordering throwNullPointerExceptionon anullkey, because they have to callcompareTo. They acceptnullonly if the Comparator handles it, e.g.Comparator.nullsFirst(...).ConcurrentHashMapforbidsnullfor 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.Stringalphabetically,Integerby value,LocalDatechronologically.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.
Iteratorworks on everyCollection:hasNext,next,remove.ListIteratorexists only forList: 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:
ArrayList<Member>: add 5 members and print them.HashSet<Integer>: add the members’ IDs, try adding a duplicate ID, print the IDs.TreeSet<Member>: add the members to get a ranking by age and print it.HashMap<Integer, Integer>: bonus points by ID for 3 members, add 10 points to member 1 if present, print.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 customequals/hashCode. The task hints that you have to write them, butIntegeralready has both. You only care when you putMemberitself into aHashSet, and the record generates them.- “Age, then name” as stated loses data. IDs 1 and 4 are both “An”, aged 25, so
compareTo == 0and theTreeSetsilently keeps only one (last output line: size 4). The task never mentions this. The solution addsidas a final tie-breaker, which also makes the ordering consistent with the record’sequals. - “Add 10 points if present” is exactly what
computeIfPresentdoes: one lookup, nocontainsKey+get+put. For “create with 10 points if absent”, usemerge(1, 10, Integer::sum). - The
TreeMapalways prints in ascending ID order even though IDs were added as 3, 1, 5, 2, 4. AHashMapwith smallIntegerkeys may look ordered too, but that’s a coincidence (anInteger’s hash is its own value); don’t rely on it. - Declare
NavigableSet/NavigableMaprather thanSet/Mapwhen you needceilingEntry,headSetand friends.
What a senior would improve:
- Keep
Memberimmutable (a record, no setters). The task asks for setters, but changing theageof an element inside aTreeSetcorrupts the tree (the element sits in the wrong place andcontainsreturnsfalse), exactly like mutating aHashMapkey. - Don’t bake “by age” into
compareToif it’s just one screen’s ordering. A more sensible natural order is byid; the ranking uses its ownComparator(section 2). - If several threads add points concurrently,
HashMapisn’t safe: useConcurrentHashMap.merge, or better, let the database do it (UPDATE ... SET points = points + 10).
Remember
- Explain why a
TreeSetcan “swallow” an element that isn’tequals, and how a tie-breaker fixes it. - Know when to pick
TreeMapoverHashMap, and writefloorEntry/subMapfor a tier table or a time window. - Know when to use
Comparableand when to useComparator. - Explain
modCountand 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, soget/containscompute the new bucket and miss it.TreeSet/TreeMap: the element is in the wrong place in the tree, searches go down the wrong branch, andremovefails 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
computeIfPresenthere, 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
NavigableMaplets 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.