Why might a TreeMap fail to find a key it actually contains, and how does this trace back to compareTo?

## How TreeMap finds a key `TreeMap` is a **red-black tree** — a self-balancing **binary search tree (BST)**. In a BST, every node has a left subtree (smaller keys) and a right subtree (larger keys). To look up a key, the map starts at the root and repeatedly compares the target key with the current node: - comparison **< 0** -> go **left**; - comparison **> 0** -> go **right**; - comparison **== 0** -> **found** (return this node's value). Crucially, **the comparison is `compareTo`** (for natural ordering) or the **supplied `Comparator`**. `TreeMap` **never** uses `equals` or `hashCode` for lookup — unlike `HashMap`. So the entire correctness of `get`, `containsKey`, `put`, and `remove` rests on the ordering being a well-behaved, stable total order. ## Failure mode 1: a broken (non-total-order) comparison If `compareTo`/`Comparator` is not transitive or not antisymmetric, the tree can be built in an inconsistent shape, and a search can branch the *wrong way* at some node — walking past the subtree that actually holds the key. Result: `get` returns `null` for a key that is physically present in the tree. There is no exception; the data is just unreachable by lookup. (This is the same root cause that makes TimSort throw "violates its general contract" during sorting — here it manifests silently in tree navigation instead.) ## Failure mode 2: mutable keys (the most common real bug) This is the one that bites in production. Suppose: ```java TreeMap<Account, Balance> map = new TreeMap<>(); // ordered by Account.id Account a = new Account(5); map.put(a, balance); a.setId(99); // mutate a field that compareTo uses map.get(a); // null! and map.get(new Account(99)) -- also null ``` The tree placed `a` at the position for id **5**. After mutation, `a` *claims* to be id **99**, so the lookup navigates toward where 99 should be — a different branch — and never reaches the node, which is still sitting where 5 belongs. The key is in the map, but **unreachable**, and the tree's ordering invariant is now corrupt for every future operation. (`HashMap` has the analogous bug if a `hashCode`/`equals` field mutates; for `TreeMap` it's any field used by the ordering.) **Rule:** keys in a `TreeMap` (and `TreeSet`) must be **immutable in their ordering-relevant fields** for as long as they are in the map. Prefer genuinely immutable key types. ## Failure mode 3: ordering inconsistent with equals Because lookup is by ordering, two keys that are `equals`-equal but `compareTo`-different are treated as **distinct** keys, and two keys that are `compareTo`-equal but not `equals`-equal are treated as the **same** key (the second `put` overwrites the first). With `BigDecimal` keys, `new BigDecimal("1.0")` and `new BigDecimal("1.00")` collide into one entry in a `TreeMap` though they'd be two entries in a `HashMap`. So "find a key it contains" is defined entirely by the ordering, which may not match your intuition built on `equals`. ## Diagnosis and fixes When `treeMap.containsKey(k)` is `false` but you're sure you inserted `k`: 1. **Check for mutation.** Did any field used by the ordering change after insertion? This is the usual culprit. Fix: immutable keys, or remove-before-mutate-then-reinsert. 2. **Validate the total order.** Is the `compareTo`/`Comparator` transitive and antisymmetric? Try sorting a list of keys with it; a TimSort exception confirms it's broken. Fix: rebuild with `Comparator.comparing(...).thenComparing(...)` and `Integer.compare`/`Double.compare`. 3. **Check consistency with equals.** Are you relying on `equals`-equality but the ordering disagrees (BigDecimal-style)? Fix: align them, or accept ordering semantics deliberately. ## One-line takeaway `TreeMap`/`TreeSet` lookups are governed by **comparison, not `equals`/`hashCode`**, so a broken or mutated ordering makes present keys invisible — the cure is a correct total order over **immutable** keys.