Correctness contracts

A sort or ordering is **stable** if elements that compare equal keep their original relative order. List.sort and Collections.sort are stable (they use TimSort for objects); PriorityQueue is not. Sort four people by age, a30 b25 c30 d25, with a stable sort and you get b d a c: the 25-year-olds in their original order, then the 30-year-olds in theirs. Offering the same four to a PriorityQueue with the same comparator and polling gives b d c a: a and c swapped.

Stability matters when you sort by several keys in turn (sort by name, then stably by age) or when equal priorities must be served first come, first served. For a priority queue add a sequence number as a tie-breaker.

1record P(String name, int age) {}
2
3static void stability() {
4    List<P> ps = new ArrayList<>(List.of(new P("a", 30), new P("b", 25), new P("c", 30), new P("d", 25)));
5    ps.sort(Comparator.comparingInt(P::age));                      // stable: b, d, a, c
6    PriorityQueue<P> pq = new PriorityQueue<>(Comparator.comparingInt(P::age));
7    pq.addAll(List.of(new P("a", 30), new P("b", 25), new P("c", 30), new P("d", 25)));
8    StringBuilder order = new StringBuilder();
9    while (!pq.isEmpty()) order.append(pq.poll().name());          // "bdca": not stable
10    System.out.println(ps.stream().map(P::name).toList() + " " + order);
11}

Sets and map keys are unique **by the container's own definition of equal**: HashSet and HashMap use equals (and hashCode); TreeSet and TreeMap use the comparator (equal means compare returns 0). Adding an element that is “equal” in that sense leaves the collection unchanged (Set.add returns false; Map.put replaces the value).

So uniqueness is only as good as your equals/hashCode or your comparator. A TreeSet that compares strings by length keeps one string per length, and a record automatically gets field-wise equals and hashCode, which usually is what a set of value objects needs.

1record Point(int x, int y) {}
2
3static void uniqueness() {
4    Set<Point> set = new HashSet<>();
5    System.out.println(set.add(new Point(1, 2)) + " " + set.add(new Point(1, 2)));   // true false: records have value equality
6}

A key's hashCode decides its bucket when it is inserted. If a field used by hashCode changes afterwards, the entry stays in the old bucket while lookups go to the new one: the entry is lost. With a mutable Key whose id changes from 1 to 2 after put, map.get(key) returns null, map.get(new Key(1)) also returns null (the stored key no longer equals it), containsKey(key) is false — and size() still reports 1.

The same applies to elements of a HashSet and to anything inside a TreeSet whose ordering fields change. Use immutable keys: String, boxed numbers, records with final fields, or copy mutable state before using it as a key.

1static final class Key {
2    int id;
3    Key(int id) { this.id = id; }
4    @Override public boolean equals(Object o) { return o instanceof Key k && k.id == id; }
5    @Override public int hashCode() { return id; }
6}
7
8static void lostEntry() {
9    Map<Key, String> m = new HashMap<>();
10    Key k = new Key(1);
11    m.put(k, "value");
12    k.id = 2;                                                        // mutates a field used by hashCode
13    System.out.println(m.get(k) + " " + m.get(new Key(1)) + " " + m.size());   // null null 1
14}

A comparator is **consistent with equals** if compare(a, b) == 0 exactly when a.equals(b). When it is not, a TreeSet and a HashSet disagree about the same data. BigDecimal("1.0") and BigDecimal("1.00") are not equals (different scale) but compareTo returns 0: a HashSet keeps both (size 2), a TreeSet keeps one (size 1).

Also keep comparators **transitive and antisymmetric**: never write a - b (it overflows), compare with Integer.compare, and break ties on a unique field so that no two distinct elements compare equal unless you mean them to.

1static void disagreement() {
2    BigDecimal a = new BigDecimal("1.0"), b = new BigDecimal("1.00");
3    System.out.println(a.equals(b) + " " + a.compareTo(b));                                  // false 0
4    System.out.println(new HashSet<>(List.of(a, b)).size() + " " + new TreeSet<>(List.of(a, b)).size());   // 2 1
5}

ArrayList, HashMap, HashSet, ArrayDeque and the other everyday collections are **not thread-safe**: two threads modifying one without coordination can lose updates or corrupt it. Safe options: confine a collection to one thread, wrap it (Collections.synchronizedList), or use a purpose-built concurrent class (ConcurrentHashMap, CopyOnWriteArrayList, ArrayBlockingQueue). Immutable collections (List.of, Map.of) are safe to share and throw UnsupportedOperationException on modification.

Even on a single thread, modifying a collection while iterating it breaks the iterator. Iterators are **fail-fast**: removing element 2 from [1, 2, 3, 4] inside a for-each loop throws ConcurrentModificationException. The check happens in next(), so removing the second-to-last element (3) ends the loop early with no exception, silently skipping 4. Use Iterator.remove() or removeIf instead.

1static void safeRemoval() {
2    List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4));
3    list.removeIf(x -> x % 2 == 0);                  // removes 2 and 4 without a ConcurrentModificationException
4    System.out.println(list);                         // [1, 3]
5}