如何使用Map根据Value对键值对排序

在刷Java力扣题的过程中，我遇到了这样一个问题：使用HashMap存储数据之后，我需要获取其Key或Value最大(或最小)的几项，而HashMap的实现原理决定了内部的Key是无序的，在遍历HashMap的Key时，顺序不可预测，在取出数据后需要再进行数据的排序处理。

起初我在面临这类问题的时候，可能会考虑创建新的类实现comparable接口，重写compareTo方法，然后使用优先队列来维护数据从而达到使数据有序的效果。但是这样做降低了代码的可读性，并且增大了代码量。

而在Java的学习过程中我又了解到了TreeMap类，其在HashMap的功能基础上，遍历时会根据Key的值进行排序。

TreeMap根据Key排序

TreeMap实现了SortedMap接口，通过放入的Key实现Comparable接口，保证了遍历时以Key的大小来进行排序。而TreeMap是如何进行排序，在何时进行排序，其底层代码是如何维护该Map，令我感到好奇，随即阅读其Java源码。

public V put(K key, V value) {
    return put(key, value, true);
}

private V put(K key, V value, boolean replaceOld) {
    ...
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else {
                V oldValue = t.value;
                if (replaceOld || oldValue == null) {
                    t.value = value;
                }
                return oldValue;
            }
        } while (t != null);
    } 
    ...
    addEntry(key, value, parent, cmp < 0);
    return null;
}

我们在调用TreeMap的put方法时，其内部调用重载的私有put方法，方法内部通过使用比较器的compare方法比较两个Entry的Key的大小，更新其left和right结点，以此达到按顺序遍历的目的。

如何根据Value排序

解决了根据Key排序的问题，但根据Value排序的问题却还未解决，在实际运用中，我会希望取到映射表中Value最大的若干项，于是我进行了进一步的思考。

使用List进行排序

为了对Value排序，我会将Map的Entry取出都存入List<Entry>中，通过List的sort方法传入一个比较器，将所有Entry排序，如下代码所示：

public static void main(String[] args) {
    HashMap<String, Integer> hashMap = new HashMap<>();

    hashMap.put("A", 9);
    hashMap.put("B", 7);
    hashMap.put("C", 5);
    hashMap.put("D", 3);
    hashMap.put("E", 1);
    hashMap.put("F", 8);
    hashMap.put("G", 6);
    hashMap.put("H", 4);
    hashMap.put("I", 2);
    hashMap.put("J", 0);


    List<Map.Entry<String,Integer>> list = new ArrayList<>();
    list.addAll(hashMap.entrySet());
    list.sort(new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });

    System.out.println("未经过排序的map: " + hashMap);
    System.out.println("经过排序后的map: " + list);
}

输出结果为：

未经过排序的map: {A=9, B=7, C=5, D=3, E=1, F=8, G=6, H=4, I=2, J=0}
经过排序后的map: [J=0, E=1, I=2, D=3, H=4, C=5, G=6, B=7, F=8, A=9]

能否通过继承TreeMap重写其方法达到对Value排序的效果?

在阅读Java源码后，我以为只需要重写put方法，将对Key使用compare方法改为对Value使用，即可完成根据Value排序。

但结果显而易见，TreeMap源码中put方法是私有的，且比较器为Comparator<? super K>，类型是Key的类型，重写源码可能较为复杂，尝试几次后放弃了该方法。

使用TreeMap的比较器根据Value排序

想到其比较器为Comparator<? super K>，而Map又可以通过Key获取Value，于是我又思考，能否创建一个比较器，通过传入Key来直接比较Value，经过几次尝试我编写了一个新的比较器类

class ValueComparator<K,V extends Comparable<V>> implements Comparator<K> {
    Map<K, V> base;

    public ValueComparator(Map<K, V> base) {
        this.base = base;
    }

    /*
     NOTE:
     这里如果比较器返回了0会使得 k-v 无法插入，
     需要根据 V 重写compare方法
     */
    public int compare(K a, K b) {
        V valA = base.get(a);
        V valB = base.get(b);
        return valA.compareTo(valB);
    }
}

在构造该比较器时，传入Map，调用compare方法时，先使用Map的get方法，获取到其Value，再进行比较

public static void main(String[] args) {
    HashMap<String, Integer> hashMap = new HashMap<>();
    ValueComparator vc = new ValueComparator(hashMap);
    TreeMap<String, Integer> treeMap = new TreeMap<>(vc);

    hashMap.put("A", 9);
    hashMap.put("B", 7);
    hashMap.put("C", 5);
    hashMap.put("D", 3);
    hashMap.put("E", 1);
    hashMap.put("F", 8);
    hashMap.put("G", 6);
    hashMap.put("H", 4);
    hashMap.put("I", 2);
    hashMap.put("J", 0);

    // 全部加入到TreeMap中
    treeMap.putAll(hashMap);

    System.out.println("未经过排序的map: " + hashMap);
    System.out.println("经过排序后的map: " + treeMap);
}

运行后输出结果为

未经过排序的map: {A=9, B=7, C=5, D=3, E=1, F=8, G=6, H=4, I=2, J=0}
经过排序后的map: {J=0, E=1, I=2, D=3, H=4, C=5, G=6, B=7, F=8, A=9}

注意

在上述代码中，ValueComparator类中的compare直接调用了泛型V的compareTo方法，该例中会调用其包装类Integer的compareTo方法，当两个Value值相等时会返回0。而在TreeMap源码中，如果compare结果为0，会进入else代码块，即替换掉原有的Value值，这会使得无法存入Value重复的K-V键值对，而这很明显违反了TreeMap的原本的用法。该错误如下所示

 public static void main(String[] args) {
    HashMap<String, Integer> hashMap = new HashMap<>();
    ValueComparator vc = new ValueComparator(hashMap);
    TreeMap<String, Integer> treeMap = new TreeMap<>(vc);

    hashMap.put("A", 9);
    hashMap.put("B", 7);
    hashMap.put("C", 5);
    hashMap.put("D", 3);
    hashMap.put("E", 1);
    hashMap.put("F", 8);
    hashMap.put("G", 6);
    hashMap.put("H", 4);
    hashMap.put("I", 2);
    hashMap.put("J", 0);

    // 如果value相同无法插入
     hashMap.put("a", 9);

    // 全部加入到TreeMap中
    treeMap.putAll(hashMap);

    System.out.println("未经过排序的map: " + hashMap);
    System.out.println("经过排序后的map: " + treeMap);
}

运行结果为

未经过排序的map: {A=9, a=9, B=7, C=5, D=3, E=1, F=8, G=6, H=4, I=2, J=0}
经过排序后的map: {J=0, E=1, I=2, D=3, H=4, C=5, G=6, B=7, F=8, A=9}

若需要避免该情况，需要在ValueComparator类中，重写compare方法，处理Value相等的情况。