TreeMap排序不能处理等值

Question

我编写了一个方法，根据TreeMap的值对其进行排序

public TreeMap<String, Integer> sortByValues(final TreeMap<String, Integer> map) {
        Comparator<String> valueComparator =  new Comparator<String>() {
            public int compare(String k1, String k2) {
                int compare = map.get(k1).compareTo(map.get(k2));
                return compare;
            }
        };
        Map<String, Integer> sortedByValues = new TreeMap<String, Integer>(valueComparator);
        sortedByValues.putAll(map);
        return sortedByValues;
    }

上述方法在正常情况下工作正常，但当TreeMap中存在重复值时失败。将从Map中删除任何重复的值条目。在谷歌了一下之后，我找到了解决方案

public Map<String, Integer> sortByValuesTree(final Map<String, Integer> map) {
        Comparator<String> valueComparator =  new Comparator<String>() {
            public int compare(String k1, String k2) {
                int compare = map.get(k1).compareTo(map.get(k2));
                if (compare == 0) return 1;
                else return compare;
            }
        };
        Map<String, Integer> sortedByValues = new TreeMap<String, Integer>(valueComparator);
        sortedByValues.putAll(map);
        return sortedByValues;
    }

上面的工作很好，但我不能理解为什么第一种方法不起作用。为什么要删除重复的值条目?谁能告诉我一声

Answer 1

为什么删除重复的值条目?

因为这就是Map的定义:对于给定的键，它存储一个值。如果为映射中已经存在的键添加另一个值，则新值将替换该键的旧值。因为你告诉映射，当一个键的关联值相等时，它就等于另一个键，所以当两个键的值相等时，映射就认为两个键是相等的。

请注意，您的解决方案是一个糟糕的解决方案，可能偶然有效。实际上，您的比较器并不尊重comparator接口的契约。实际上，当两个值相等时，您可以任意决定使第一个值大于第二个值。这意味着比较器同时使A> B和B> A为真，这是不正确的。

按值排序TreeMap对我来说看起来很荒谬。无论如何，您将无法向映射添加任何新值，因为它要求条目已经存在于旧映射中。难道不应该简单地拥有一个排序过的地图条目列表吗?

Answer 2

实际上，特别是在Java 7以后，甚至第二个方法也不起作用。(原因见下文。)无论如何，原因是映射必须有不同的键，当您使用您的值作为键时，两个相等的值将被视为相等的键。

顺便说一下，正确的解决方法是先按值排序，然后按键排序:

int compare = map.get(k1).compareTo(map.get(k2));
if (compare == 0) {
    compare = k1.compareTo(k2);
}
return compare;

---

合适的比较器必须遵循三个规则:

1. compare(a, a) == 0适用于a的所有值
2. a和b的所有值
3. signum(compare(a, b)) == -signum(compare(b, a))
4. 如果signum(compare(a, b)) == signum(compare(b, c))，那么signum(compare(a, c))也必须具有相同的值，对于a, b和c的所有值。