Case-insensitive Comparator breaks my TreeMap

The accepted answer is technically correct, but misses the idiomatic solution to the problem.

You should be using the static String.CASE_INSENSITIVE_ORDER comparator provided or at least using String.compareToIgnoreCase() inside your own to consider what is .equal().

For locale sensitive comparisons, you should use something from java.text.Collator

You need to ensure that the equality of that map's elements is consistent with the comparator. Quoting from the class comment:

Note that the ordering maintained by a tree map, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the interface.

It happens because TreeMap considers elements equal if a.compareTo(b) == 0. It's documented in the JavaDoc for TreeMap (emphasis mine):

Note that the ordering maintained by a tree map, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

Your comparator isn't consistent with equals.

If you want to keep not-equal-but-equal-ignoring-case elements, put a second level of checking into your comparator, to use case-sensitive ordering:

    public int compare(String o1, String o2) {
        int cmp = o1.compareToIgnoreCase(o2);
        if (cmp != 0) return cmp;

        return o1.compareTo(o2);
    }

The Comparator you pass to a TreeMap determines not just the ordering of the keys inside the Map, it also determines whether two keys are considered identical (they are considered identical when compare() returns 0).

Therefore, in your TreeMap, "abc" and "ABC" are considered identical keys. Maps don't allow identical keys, so the second value Element2 overwrites the first value Element1.