如何对各种Map进行排序

在通常的排序场景中，我们都是使用List或者是Set来承载各个元素，然后使用Collections工具类来进行排序，这块排序主要就是通过实现Comparable接口或者是新建一个Comparator比较器来实现的，比较简单，可以参考Java中的Comparable和Comparator

然而有的时候，我们承载元素的集合类是Map，这种情况下怎么实现对Map中元素的排序呢？或者是否有更好的数据结构可以解决这个问题呢？

一、Map的分类

• HashMap，数据结构主要是由数组、链表或者红黑树组成，根据key的hashcode()和equals()来决定存储value的位置，所以其中所有value的存储是无序的，其具有很快的访问速度，但是在大量迭代访问时表现不佳；只允许一个key为null，但是允许多个key的value为null；它是非线程安全的，多线程场景下推荐使用Collections的synchronizedMap或者是ConcurrentHashMap；

    public static void main(String[] args) {
        HashMap<String,Integer> myHashMap = new HashMap();
        myHashMap.put("zIndex",12);
        myHashMap.put("mIndex",12);
        myHashMap.put("qIndex",12);
        myHashMap.put("fIndex",12);
        myHashMap.put("bIndex",12);

        // 遍历输出，判断是否是按照key升序保存的
        Set<String> mySet = myHashMap.keySet();
        for(String currentKey : mySet){
            log.info("key:{}-value:{}", currentKey, myHashMap.get(currentKey));
        }
    }

输出结果如下，可以看到确实是无序的：

key:bIndex-value:12
key:qIndex-value:12
key:fIndex-value:12
key:mIndex-value:12
key:zIndex-value:12

• HashTable，原理与HashMap类似，但最大的不同是其不允许key和value为空，它是线程安全的，多线程场景下，写入效率比较低；而且，hash计算过程不同，所以同样的put顺序，存储的顺序确是不同的。可以参考hashMap和hashTable的区别以及HashMap的底层原理？，一般都没有人使用这个类了，性能比较低下，如果要使用线程安全的特性，可以考虑使用ConcurrentHashMap。
• LinkedHashMap，是HashMap的子类，保存了元素插入的顺序，所以其在遍历元素时是有序的，在大量迭代访问时表现比HashMap更好；可以参考LinkedHashMap 源码详细分析JDK1.8

public static void main(String[] args) {
        LinkedHashMap<String,Integer> myLinkedHashMap = new LinkedHashMap();
        myLinkedHashMap.put("zIndex",12);
        myLinkedHashMap.put("mIndex",12);
        myLinkedHashMap.put("qIndex",12);
        myLinkedHashMap.put("fIndex",12);
        myLinkedHashMap.put("bIndex",12);

        // 遍历输出，判断是否是按照key升序保存的
        Set<String> mySet = myLinkedHashMap.keySet();
        for(String currentKey : mySet){
            log.info("key:{}-value:{}", currentKey, myLinkedHashMap.get(currentKey));
        }
    }

输出结果如下，发现和存储的顺序是一致的：

key:zIndex-value:12
key:mIndex-value:12
key:qIndex-value:12
key:fIndex-value:12
key:bIndex-value:12

• TreeMap，数据结构主要就是红黑树，要求存储的键必须是Comparable的，会把保存的元素默认根据键升序排列，所以其在遍历元素时是有序的，当然也可以自己指定比较器定义排序规则；

public static void main(String[] args) {
        TreeMap<String,Integer> myTreeMap = new TreeMap();
        myTreeMap.put("zIndex",12);
        myTreeMap.put("mIndex",12);
        myTreeMap.put("qIndex",12);
        myTreeMap.put("fIndex",12);
        myTreeMap.put("bIndex",12);

        // 遍历输出，判断是否是按照key升序保存的
        Set<String> mySet = myTreeMap.keySet();
        for(String currentKey : mySet){
            log.info("key:{}-value:{}", currentKey, myTreeMap.get(currentKey));
        }
    }

输出结果如下，默认是按照key升序存储的：

key:bIndex-value:12
key:fIndex-value:12
key:mIndex-value:12
key:qIndex-value:12
key:zIndex-value:12

二、各种Map实现排序

2.1 HashMap的排序

因为HashMap中存放元素是无序的，所以肯定不能在HashMap数据结构中进行排序，我们只能将元素放到List中，利用List进行排序。

    public static void main(String[] args) {
        Map<String, String> fruitMap = new HashMap<>();
        fruitMap.put("orange", "china");
        fruitMap.put("banana", "usa");
        fruitMap.put("apple", "canada");
        fruitMap.put("grape", "england");

        List<Map.Entry<String, String>> fruitList = new ArrayList<>(fruitMap.entrySet());
        Collections.sort(fruitList, new Comparator<Map.Entry<String, String>>() {
            @Override
            public int compare(Map.Entry<String, String> o1, Map.Entry<String, String> o2) {
                // 按照水果产地的字母升序排列
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for (Map.Entry<String, String> fruit : fruitList) {
            log.info("{} from {}", fruit.getKey(), fruit.getValue());
        }
    }

可以看到，想要对HashMap进行排序，还是比较麻烦的，不但要借助额外的存储空间List，排序的方法看上去也不简洁。

这时，可以推荐使用commons-lang3中pair数据结构进行元素的承载和排序。

    public static void main(String[] args) {
        // MutablePair是Pair的实现类，一个Pair只能存放一个键值对
        Pair<String,String> orangePair = new MutablePair("orange", "china");
        Pair<String,String> bananaPair = new MutablePair("banana", "usa");
        Pair<String,String> applePair = new MutablePair("apple", "canada");
        Pair<String,String> grapePair = new MutablePair("grape", "england");

        List<Pair<String,String>> fruitList = new ArrayList<>();
        fruitList.add(orangePair);
        fruitList.add(bananaPair);
        fruitList.add(applePair);
        fruitList.add(grapePair);

        fruitList.sort(new Comparator<Pair<String, String>>() {
            // 按照水果产地的字母升序排列
            @Override
            public int compare(Pair<String, String> o1, Pair<String, String> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for (Map.Entry<String, String> fruit : fruitList) {
            log.info("{} from {}", fruit.getKey(), fruit.getValue());
        }
    }

Map一次性可以存储多个键值对，Pair只能存放一个键值对，由于Map在初始化空间的时候默认是16，所以当我们只需要保存一个键值对的时候，Pair更加省空间，速度也更加快。

2.2 TreeMap的排序

TreeMap在存储元素的时候，默认会按照key进行升序排列后存储，所以在默认情况下就是有序的。

    public static void main(String[] args) {
        Map<String, String> fruitMap = new TreeMap<>();
        // 按照水果名称的字母升序排列
        fruitMap.put("orange", "china");
        fruitMap.put("banana", "usa");
        fruitMap.put("apple", "canada");
        fruitMap.put("grape", "england");

        // TreeMap默认已经按照key升序排列了
        Iterator<String> iterator = fruitMap.keySet().iterator();
        while(iterator.hasNext()){
            String currentFruit = iterator.next();
            log.info("{} from {}", currentFruit, fruitMap.get(currentFruit));
        }
    }

如果我们想实现自定义的按照键的排序方式，可以在创建TreeMap的时候就实例化比较器。

        Map<String, String> fruitMap = new TreeMap<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                // 自定义如何按照键进行排序——按照水果名称的字母升序排列
                return o2.compareTo(o1);
            }
        });

如上只是按照键进行排序，如果我们想按照value进行排序呢？我们还是得回到HashMap的排序方式路子上去。