Map按Key或者Value排序

今天做了一道算法题，简单总结一下思路

题目如下：

题目描述

数据表记录包含表索引和数值，请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。

输入描述:

先输入键值对的个数 然后输入成对的index和value值，以空格隔开

输出描述:

输出合并后的键值对（多行）

输入例子:

4
0 1
0 2
1 2
3 4
      

输出例子:

0 3
1 2
3 4      

题目的思路大概是这样的：

1、首先获取每一行的数据，新建一个map，将每行的第一个值作为key，第二个值作为value存入map中，因为题目要求的是将索引相同的值进行合并，因此在每次向map中添加（key，value）的时候应当先判断一下这个map中对应的key是否已经添加过了，如果添加过了，则应当将这个value和map中已经存在的value进行相加。

2,、第一步完成后得到的map是无序的，应当进行排序，TreeMap是一种二叉搜索树，因此每次向TreeMap中添加时，都会进行排序，我们可以借用TreeMap的这个特性进行排序，排序还需要一个比较器（Comparator）对象，比较器的具体作用就是，根据TreeMap中插入的对象的某个属性进行比较，从而决定插入对象在TreeMap中的位置，这个比较器可以是我们自己定义，这样我们就可以通过改变比较器使map按key或value进行排序。

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;


public class Solution {
	public static void main(String[] args) {
	   //oj中进行数据输入
	   Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        Map<String, Integer> map = new HashMap<>();
        for(int i=0;i<n;i++) {
            String s = sc.nextLine();
            String[] ss = s.split(" ");
            Integer integer = map.get(ss[0]);
		 //判断map中之前是否已经添加过相同key的数据
            if(integer!=null) {
			//如果添加过，那么将数据进行合并
            	map.put(ss[0], integer+Integer.parseInt(ss[1]));
            } else {
			//否则就直接添加
            	map.put(ss[0], Integer.parseInt(ss[1]));
            }
        }
	   //关闭资源
        sc.close();
	   //sortByKey通过key对map进行排序
        map = sortByKey(map);
	   //排好序的map进行输出
        Iterator<String> iterator = map.keySet().iterator();
        while(iterator.hasNext()) {
        	String key = iterator.next();
        	System.out.println(key+" "+map.get(key));
        }
	}
	
	public static Map<String, Integer> sortByKey(Map<String, Integer> map) {
		if(map==null||map.isEmpty()) {
			return null;
		}
		//创建一个TreeMap，传入一个自定义的比较器
		Map<String,Integer> sortMap = new TreeMap<String, Integer>(new MapKeyComparator());
		//把未排序的map全部添加到TreeMap中，产生有序的结构
		sortMap.putAll(map);
		return sortMap;
	}


}

//自定义的比较器
class MapKeyComparator implements Comparator<String> {
	
	
	@Override
	public int compare(String s1, String s2) {
		//比较的是key，转换成整型后比较大小，
		Integer a1 = Integer.parseInt(s1);
		Integer a2 = Integer.parseInt(s2);
		//返回结果0表示相等，负数表示a1小于a2，正数表示a1大于a2，这样排序的结果是升序的
		return a1.compareTo(a2);
	}
	
}
           

这是根据key进行的排序，如果要通过value排序呢？似乎要麻烦一些，TreeMap中是通过key排序的，因此就不能再使用TreeMap对value排序了。

我们可以通过Collections.sort(List list, Comparator c)方法来进行排序。

步骤如下：

1、首先要将未排序的map转换成List集合

List<Entry<String,Integer>> list = new ArrayList<Entry<String,Integer>>(map.entrySet());

List集合中存放的是（key，value）对，

class MapValueComparator implements Comparator<String> {
	@Override
	public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
        return (o2.getValue() - o1.getValue());
	}
	
}
           

然后将这个自定义的比较器传入就能对list进行排序了。

用Collections.sort进行排序似乎不论是key或者value都可以，暂时还没有比较和TreeMap的效率