Case-insensitive Comparator breaks my TreeMap

Question

A Comparator I used in my TreeMap broke the behavior I intended for that TreeMap. Look at the following code:

TreeMap<String, String> treeMap = new TreeMap<>(new Comparator<String>() {     public int compare(String o1, String o2) {         return o1.toLowerCase().compareTo(o2.toLowerCase());     } }); treeMap.put("abc", "Element1"); treeMap.put("ABC", "Element2"); 

What I think I have done is that I have created a map that is sorted by its keys, case-insensitive. The two distinct elements have non-equal keys (abc and ABC) whose comparison will return 0. I expected just a random ordering of the two elements. Yet, the command:

System.out.println("treeMap: " + treeMap); 

resulted in:

treeMap: {abc=Element2} 

The key abc has been re-assigned the value Element2!

Can anyone explain how could this happen and if it's a valid, documented behavior of TreeMap?

Answer 1

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);     }