Iterators, Comparators & Ordering Contracts — Interview Questions

How to use this lesson

Iterator and comparator bugs are silent correctness bugs: lost elements in a TreeSet, IllegalArgumentException: Comparison method violates its general contract! in production sorts, or ConcurrentModificationException in single-threaded code. Explain the contract each time, and how to satisfy it.

Q1. Can you use an Iterator to iterate over a Map? How?

Short answer: A Map isn't Iterable itself. Iterate one of its views:

• entrySet(): the best choice when you need both key and value (one lookup per entry);
• keySet();
• values().

Their iterators support remove(), which removes the mapping from the map.

for (Iterator<Map.Entry<String, Integer>> it = stock.entrySet().iterator(); it.hasNext(); ) {
    Map.Entry<String, Integer> e = it.next();
    if (e.getValue() == 0) it.remove();                // safe removal during iteration
}
stock.entrySet().removeIf(e -> e.getValue() == 0);      // the same thing, idiomatically
stock.forEach((sku, qty) -> log.info("{}={}", sku, qty));

Common trap: iterating keySet(), then calling map.get(key) for each key. That's a second lookup per entry, and on a TreeMap it's O(log n) each time.

Q2. What is a fail-safe iterator? Which classes use them?

Short answer: "Fail-safe" (not an official JDK term) describes iterators that never throw ConcurrentModificationException when the collection changes during iteration. There are two kinds:

• Snapshot iterators: they iterate a copy of the underlying array taken when the iterator was created. CopyOnWriteArrayList and CopyOnWriteArraySet. They never see later changes, and their remove() is unsupported.
• Weakly consistent iterators: they traverse live data, tolerate concurrent changes, and may or may not reflect updates made after they were created. They never return an element twice. Used by ConcurrentHashMap (and its views), ConcurrentSkipListMap/Set, ConcurrentLinkedQueue/Deque, and most BlockingQueue implementations.

Q3. What happens if you modify a collection inside an enhanced for loop?

Short answer: The enhanced for uses the collection's iterator behind the scenes. Calling list.remove(x) or list.add(x) changes the collection's modCount, so the next iterator.next() throws ConcurrentModificationException. Surprisingly, removing the second-to-last element doesn't throw: hasNext() returns false because the size shrank, so the loop silently skips the last element. That's a nasty inconsistency.

Fixes:

• removeIf(predicate);
• an explicit Iterator with it.remove();
• a ListIterator for add or set;
• collect the changes and apply them after the loop;
• or iterate a copy.

Modifying the fields of the elements (not the structure) is fine, unless they're hash keys.

Q4. What's the difference between Iterator.remove() and List.remove() during iteration?

Short answer:

• Iterator.remove() removes the element last returned by next(), and updates the iterator's expected modCount. It's the sanctioned way to remove while iterating. It can only be called once per next(), otherwise it throws IllegalStateException.
• List.remove(index)/remove(Object) change the list behind the iterator's back, and trigger ConcurrentModificationException on the next next().

Watch out for the overload trap on List<Integer>: remove(1) removes index 1, while remove(Integer.valueOf(1)) removes the value 1.

Q5. What happens if a HashSet is modified concurrently during iteration?

Short answer:

• In a single thread, a structural modification outside the iterator gives ConcurrentModificationException on the next next().
• With multiple threads, the behaviour is undefined. CME is thrown on a best-effort basis only, so you might instead get:
  • missed or repeated elements;
  • NullPointerException during a resize;
  • or silently corrupted state.

Never rely on CME for thread safety. Use ConcurrentHashMap.newKeySet(), CopyOnWriteArraySet, or external synchronisation covering the whole iteration.

Q6. Why are iterators fail-fast (rather than fail-safe) in most collections?

Short answer: It's a design trade-off:

• Fail-fast is cheap: a single modCount integer check per next(). It surfaces bugs early, instead of iterating over a half-modified structure, and producing wrong results later.
• Fail-safe costs more: snapshots copy the data (memory and time), and weak consistency needs concurrent data structures designed for it (with more complex algorithms and some overhead).

General-purpose collections optimise for single-threaded speed, and use fail-fast checks as a debugging aid. Concurrent collections pay the extra cost where it's needed.

Q7. How does CopyOnWriteArrayList iteration differ from ArrayList iteration?

Short answer:

• CopyOnWriteArrayList: every write (add, set, remove) copies the entire internal array, under a lock, and publishes the new array through a volatile reference. Iterators work over the array that existed when they were created. So they never throw CME, see a consistent snapshot, don't see later updates, and don't support iterator.remove().
• ArrayList: a fail-fast iterator over the live array.

Q8. What are the performance implications of modifying a CopyOnWriteArrayList?

Short answer: Each modification is O(n) in time and allocation (a full array copy), and writes are serialised by a lock. So:

• it's excellent for read-mostly data (listener lists, configuration snapshots, routing tables), where reads are lock-free and very fast;
• it's terrible for write-heavy or large lists: 10,000 elements × frequent writes means massive garbage and CPU;
• batch your writes (addAll) to copy once.

For write-heavy concurrent lists, use a ConcurrentLinkedQueue/Deque, or a lock around an ArrayList, or rethink the data structure.

Q9. What happens if you insert non-comparable elements into a TreeSet or TreeMap?

Short answer: With natural ordering, the TreeMap casts the key to Comparable. An element that doesn't implement Comparable throws ClassCastException. Even the first insertion checks this (it compares the key with itself), since Java 7. The fix is to supply a Comparator at construction. The same exception appears for mixed incomparable types (a String and an Integer).

Q10. Can a class implement Comparable and still be sorted with a Comparator?

Short answer: Yes, and it's common. Comparable defines the natural ordering (for example Employee by ID), and Comparators provide alternative orderings for specific uses (by salary, by name). When a comparator is supplied, it takes precedence. You can also reuse the natural ordering inside comparators: Comparator.naturalOrder(), or .thenComparing(Comparator.naturalOrder()).

Q11. What does returning 0 from compareTo() or compare() mean?

Short answer: It means the two objects are equal in ordering. The consequences:

• Sorting: they're equivalent. Java's sorts are stable for objects (TimSort), so equal elements keep their relative order.
• TreeSet/TreeMap: they're treated as the same element or key. The second isn't added (a set), or it overwrites the value (a map). This is the source of the classic bug: a TreeSet<Employee> compared only by salary silently drops employees with equal salaries.

Fix: add tie-breakers (thenComparing(Employee::id)), so distinct objects never compare as 0.

Q12. Can two objects be "equal" by compareTo but not by equals()?

Short answer: Yes. The ordering is then inconsistent with equals. The classic example is BigDecimal: new BigDecimal("2.0").compareTo(new BigDecimal("2.00")) == 0, but equals is false (it compares the scale). The consequences:

• new HashSet<>(List.of(a, b)) has 2 elements;
• new TreeSet<>(List.of(a, b)) has 1.

Sorted collections follow compareTo, and hash collections follow equals. The Comparable docs strongly recommend consistency, and require you to document it if you break it.

Q13. How is the compareTo() contract linked to equals and hashCode?

Short answer:

• The compareTo contract:
  • anti-symmetry: sgn(a.compareTo(b)) == -sgn(b.compareTo(a));
  • transitivity;
  • consistency: if a equals b in ordering, then a and c compare the same way as b and c.
• Recommended: (a.compareTo(b) == 0) == a.equals(b). If you honour that, and equals is consistent with hashCode, then all three agree, and the object behaves identically in HashSet, TreeSet, HashMap and TreeMap.

Key points to cover:

• Build all three from the same fields.
• Records give equals/hashCode. Make the comparator match the record's components (or use a clearly documented alternative ordering).

Q14. How do you sort a List<Employee> by several fields?

Short answer: Compose comparators with Comparator.comparing(...).thenComparing(...), and control the direction and null handling explicitly:

employees.sort(
    Comparator.comparing(Employee::department)
              .thenComparing(Employee::salary, Comparator.reverseOrder())   // highest paid first within a department
              .thenComparing(Employee::lastName, Comparator.nullsLast(String.CASE_INSENSITIVE_ORDER))
              .thenComparingLong(Employee::id));                            // deterministic tie-breaker

Key points to cover:

• Use comparingInt/comparingLong/comparingDouble for primitive keys, to avoid boxing.
• Never compare with subtraction (a.age - b.age): it overflows with extreme values, and breaks the contract.
• In streams: .sorted(comparator).

Learn it in depth → Collectors and groupingBy

Q15. Can a Comparator be stateful, or use lambdas? What's the caveat?

Short answer: Comparators are usually lambdas or method-reference compositions, and should be stateless and pure: the same inputs always give the same result.

• State that changes during a sort (counters, time-dependent values, mutable lookups, random numbers) makes the comparison inconsistent. TimSort may then throw IllegalArgumentException: Comparison method violates its general contract!, or produce a wrong order.
• Read-only captured state (a precomputed ranking map, a Collator for a locale) is fine.
• Comparators used by sorted collections must stay consistent for the collection's whole lifetime. Changing a captured map afterwards corrupts the TreeMap.
• If comparators are shared across threads, their captured objects must be thread-safe or immutable (Collator isn't thread-safe; clone it per thread).

Q16. What's the difference between natural ordering and custom ordering?

Short answer:

• Natural ordering: the single, default ordering defined by the class itself, through Comparable (numbers ascending, strings lexicographic, dates chronological). It's used implicitly by Collections.sort(list), TreeSet and Arrays.sort(Object[]).
• Custom ordering: any ordering supplied externally through a Comparator. You can have many (by name, by price descending, locale-aware), including orderings for classes you can't modify.

Pick natural ordering only when there's one obvious ordering, consistent with equals.

Q17. How do you sort a map by its keys or values with a custom comparator?

Short answer: Maps aren't sorted in place, so you build a sorted view or copy:

// By key: a TreeMap with a comparator
SortedMap<String, Integer> byKey = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
byKey.putAll(scores);

// By value (descending), preserving that order in a LinkedHashMap
Map<String, Integer> byValue = scores.entrySet().stream()
        .sorted(Map.Entry.<String, Integer>comparingByValue().reversed()
                .thenComparing(Map.Entry.comparingByKey()))
        .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
                (a, b) -> a, LinkedHashMap::new));

Common trap: trying to build a TreeMap ordered by value, with a comparator that looks up values. It breaks as soon as values change, or two keys share a value (compare = 0 means a lost key).

Q18. What happens if a comparator returns inconsistent values during sorting?

Short answer: The sort's assumptions are violated:

• TimSort (used by List.sort, Arrays.sort for objects, and Collections.sort) may detect it, and throw IllegalArgumentException: Comparison method violates its general contract!, typically only for larger inputs, intermittently, depending on the data;
• or it may silently produce a wrongly ordered result;
• in TreeMap/TreeSet, you get lost elements, and failed lookups.

The common causes are:

• subtraction overflow;
• non-transitive logic (comparing by different fields in different cases);
• floating-point comparison with NaN (use Double.compare);
• time- or random-dependent comparisons;
• mutable fields changing mid-sort.

Test comparators with property-based tests (antisymmetry and transitivity over random samples).

Follow-up questions this topic invites — and their answers

Q: What does a ListIterator add over an Iterator? A: Bidirectional traversal (hasPrevious/previous), index queries (nextIndex/previousIndex), and set(e) and add(e) at the current position, all without triggering ConcurrentModificationException.

Q: Is Arrays.sort(int[]) stable? And for objects? A: Primitive arrays use a dual-pivot quicksort, which isn't stable, but stability is meaningless for identical primitives. Object sorts (TimSort) are stable, which is why multi-pass sorting works, and why thenComparing is often cleaner.

Q: How do you get a reversed view of an ordered collection since Java 21? A: list.reversed(), deque.reversed(), linkedHashMap.reversed(), treeSet.reversed(). These are sequenced-collection views, with no copying.

Q: Why might Collections.sort on a LinkedList still be fast? A: List.sort copies the elements into an array, sorts the array with TimSort, and writes them back through a ListIterator. So it's O(n log n), and doesn't sort linked nodes in place.