If you've ever used a custom Comparator with Java's TreeMap, you might have encountered unexpected behavior where different keys overwrite each other. For example, if you sort strings by length, adding "Read" and "4ltr" might result in only one entry surviving in the map.

Why Does TreeMap Overwrite Different Keys?

Unlike HashMap, which relies on equals() and hashCode() to determine key uniqueness, TreeMap relies exclusively on its Comparator (or the natural Comparable implementation).

According to the official Java documentation for SortedMap:

"The ordering maintained by a sorted map... must be consistent with equals if the sorted map is to correctly implement the Map interface."

When your comparator evaluates two distinct keys and returns 0 (indicating equality), TreeMap concludes that the keys are identical and replaces the existing value with the new one.

// Problematic Example
TreeMap<String, Integer> test = new TreeMap<>(Comparator.comparingInt(String::length));
test.put("Hello", 2);
test.put("Read", 3);
test.put("4ltr", 4); // "4ltr" has length 4, same as "Read". "Read" gets overwritten!

System.out.println(test); // Output: {Read=4, Hello=2} or {4ltr=4, Hello=2}

Solution 1: Add a Secondary Tie-Breaker (Recommended)

The cleanest and most idiomatic fix is to supply a tie-breaking rule using .thenComparing(). By chaining the natural ordering of strings after comparing their lengths, keys with identical lengths will maintain their distinct identity while still sorting primarily by length.

import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        // Sort by length first, then alphabetically for ties
        Comparator<String> customComparator = Comparator
                .comparingInt(String::length)
                .thenComparing(Comparator.naturalOrder());

        TreeMap<String, Integer> test = new TreeMap<>(customComparator);
        test.put("Hello", 2);
        test.put("Read", 3);
        test.put("4ltr", 4);

        System.out.println(test);
        // Output: {4ltr=4, Read=3, Hello=2}
    }
}

Solution 2: Group by Key Length Using a Multimap

If you genuinely want to map the property (e.g., string length) to multiple values, you should invert your data structure and use a Map<Integer, List<String>> or a Multimap from libraries like Google Guava.

import java.util.*;

public class GroupingExample {
    public static void main(String[] args) {
        Map<Integer, List<String>> lengthMap = new TreeMap<>();

        // Helper method or computeIfAbsent
        lengthMap.computeIfAbsent(5, k -> new ArrayList<>()).add("Hello");
        lengthMap.computeIfAbsent(4, k -> new ArrayList<>()).add("Read");
        lengthMap.computeIfAbsent(4, k -> new ArrayList<>()).add("4ltr");

        System.out.println(lengthMap);
        // Output: {4=[Read, 4ltr], 5=[Hello]}
    }
}

Why You Should Never Use Random Numbers in a Comparator

You might be tempted to introduce random numbers (e.g., returning -1 or 1 randomly on ties) to force the map to store duplicate keys. Do not do this.

A Comparator must strictly satisfy mathematical ordering properties:

  • Transitivity: If compare(a, b) > 0 and compare(b, c) > 0, then compare(a, c) must be > 0.
  • Symmetry: compare(a, b) == -compare(b, a).

Violating these invariants will corrupt the internal Red-Black tree structure of TreeMap, resulting in erratic lookups, lost entries, or a runtime IllegalArgumentException: Comparison method violates its general contract.

Conclusion

When using custom comparators in a TreeMap, always ensure your comparator returns 0 only when keys are truly identical in the context of the map. Using thenComparing(Comparator.naturalOrder()) is the standard, safe, and efficient solution to preserve all unique keys.