题解 | #合并表记录#

Treemap适用于遍历键

Map 接口的实现类有 HashMap 和 TreeeMap等
相同点：

    HashMap非线程安全，TreeMap非线程安全
    都继承了AbstractMap

不同点：

HashMap:基于哈希表实现。使用HashMap要求添加的键类明确定义了hashCode()和equals()(可以重写hashCode()和equals()),为了优化HashMap空间的使用，您可以调优初始容量和负载因子。
TreeMap:基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态。
HashMap :适用于在Map中插入、删除和定位元素。
Treemap:适用于按自然顺序或自定义顺序遍历键(key)
HashMap通常比TreeMap快一点（树和哈希表的数据结构使然），建议多使用HashMap,在需要排序的Map时候才用TreeMap。
HashMap的结果是没有排序的。TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。HashMap里面存入的键值对在取出的时候是随机的,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。在Map中插入、删除和定位元素，HashMap是最好的选择。TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。

Map 类中存储的键-值对通过键来标识，所以键值不能重复(仍然说的是equals，但挨个用equals方法比较太费力了，直接比较hashcode，所以重写了equlas方法就必须也重写hashcode)

常用方法

Object put (Object key, Object value);//向集合中加入元素
Object get (Object key);//通过指定key获取value。
Object remove (Object key);//删除指定key的键值对。
boolean containsKey (Object key);//判断集合中是否包含指定key。
boolean containsValue(Object value);//判断集合中是否包含指定value。
int size();// 获取集合中元素的个数。
boolean isEmpty();//判断集合元素个数是否为0。
void putAll (Map t);//将来自特定映像的所有元素添加给该映像
void clear();//清空集合，元素个数清0。

entry遍历

遍历Map对象的四种方法

方法一在for-each循环中使用entries来遍历

这是最常见的并且在大多数情况下也是最可取的遍历方式。在键值都需要时使用。

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

在for-each循环中遍历keys或values。
如果只需要map中的键或者值，你可以通过keySet或values来实现遍历，而不是用entrySet。该方法比entrySet遍历在性能上稍好（快了10%），而且代码更加干净

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//遍历map中的键
for (Integer key : map.keySet()) {
    System.out.println("Key = " + key);
}
//遍历map中的值
for (Integer value : map.values()) {
    System.out.println("Value = " + value);
}

使用Iterator遍历
该种方式看起来冗余却有其优点所在。首先，在老版本java中这是惟一遍历map的方式。另一个好处是，你可以在遍历时调用iterator.remove()来删除entries，另两个方法则不能。根据javadoc的说明，如果在for-each遍历中尝试使用此方法，结果是不可预测的。从性能方面看，该方法类同于for-each遍历（即方法二）的性能。

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
    Map.Entry<Integer, Integer> entry = entries.next();
    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

通过键找值遍历
作为方法一的替代，这个代码看上去更加干净；但实际上它相当慢且无效率。因为从键取值是耗时的操作（与方法一相比，在不同的Map实现中该方法慢了20%~200%）。如果你安装了FindBugs，它会做出检查并警告你关于哪些是低效率的遍历。所以尽量避免使用。

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer key : map.keySet()) {

    Integer value = map.get(key);

    System.out.println("Key = " + key + ", Value = " + value);

}

总结：如果仅需要键(keys)或值(values)使用方法二。如果你使用的语言版本低于java 5，或是打算在遍历时删除entries，必须使用方法三。否则使用方法一(键值都要)。

import java.util.*;
import java.lang.*;

public class Main {
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TreeMap<Integer, Integer> map = new TreeMap<>();

        while(n-- > 0) {
            int key = sc.nextInt();
            int value = sc.nextInt();
            if (map.containsKey(key)) {
                map.put(key, map.get(key) + value);
            }else {
                map.put(key, value);
            }
        }

        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
}