Using a comparator with Treemap causes duplicate keys

Question

I am using a treemap but created my own comparator so that the treemap is ordered by the values rather than the keys. This works fine but whenever I come to overwrite a <key, value> mapping, instead of being overwritten, a new mapping is added with the same key (which shouldn't happen because maps in Java are meant to have unique keys). I have even tried to remove the mapping first before adding another one but nothing gets deleted from the treemap. When I remove the comparator, there are no unique values and the treemap works as expected. Why does this happen?

Here is my code:

public Map<String, List<String>> mapQtToNonSampledCase(List<Entry> cases, Map<String, Integer> populationDistribution) {
  Map<String. Integer> distribution = new HashMap<>(populationDistribution);
  Map<String. List<String>> qtToCases = new HashMap<>();
  
  Comparator<String> valueComparator = new Comparator<String>() {
    public int compare(String k1, String k2) {
      int compare = distribution.get(k1).compareTo(distribution.get(k2));
      if (compare == 0)
        return 1;
      else
        return compare;
      }
    };
      TreeMap<String, Integer> sortedByValues = new TreeMap<>(valueComparator);
      sortedByValues.putAll(distribution);
      
      for(Entry entry: cases) {
        List<Map.Entry<String, Integer>> listEntries = sortedByValues.entrySet().stream().collect(Collectors.tolist());
        Map.Entry<String, Integer> qt = sortedByValues.firstEntry().getKey().equals(entry.get(UtilsClass.ID).toString()) ? (listEntries.get(1) != null ? listEntries.get(1) : null) : sortedByValues.firstEntry();
        if(qt != null) {
          if(!qtToCases.containsKey(qt.getKey()) {
              qtToCases.put(qt.getKey(), new ArrayList<>());
            );      
          }
          qtToCases.get(qt.getKey()).add(entry.get(UtilsClass.ID).toString());
          sortedByValues.put(qt.getKey(), qt.getValue() - 1);
          
        }
      }
      // Printing keys
      for(Map.Entry<String, Integer> entry : sortedByValues.entrySet()) {
        System.out.println(entry.getKey());
      }
}

And here is the console output (apologies for the quality, it's a picture from another device):

Answer 1

Your custom comparator is not consistent with equals: When you try to update a key with a different value, your comparator will return a value != 0, but the keys are the same.

See this comment in TreeMap API doc:

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.

The term 'consistent with equals' is defined here: [Comparable API doc]:2

The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C.