Map
Map是一种用于快速查找的数据结构，它以键值对的形式存储数据，每一个键都是唯一的，且对应着一个值，如果想要查找Map中的数据，只需要传入一个键，Map会对键进行匹配并返回键所对应的值，可以说Map其实就是一个存放键值对的集合。Map被各种编程语言广泛使用，只不过在名称上可能会有些混淆，像Python中叫做字典（Dictionary），也有些语言称其为关联数组（Associative Array），但其实它们都是一样的，都是一个存放键值对的集合。至于Java中经常用到的HashMap也是Map的一种，它被称为散列表，关于散列表的细节我会在本文中解释HashMap的源码时提及。
Java还提供了一种与Map密切相关的数据结构：Set，它是数学意义上的集合，特性如下：
- 无序性：一个集合中，每个元素的地位都是相同的，元素之间也都是无序的。不过Java中也提供了有序的Set，这点倒是没有完全遵循。
- 互异性：一个集合中，任何两个元素都是不相同的。
- 确定性：给定一个集合以及其任一元素，该元素属于或者不属于该集合是必须可以确定的。
很明显，Map中的key就很符合这些特性，Set的实现其实就是在内部使用Map。例如，HashSet就定义了一个类型为HashMap的成员变量，向HashSet添加元素a，等同于向它内部的HashMap添加了一个key为a，value为一个Object对象的键值对，这个Object对象是HashSet的一个常量，它是一个虚拟值，没有什么实际含义，源码如下：
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
小插曲过后，让我们接着说Map，它是JDK的一个顶级接口，提供了三种集合视图（Collection Views）：包含所有key的集合、包含所有value的集合以及包含所有键值对的集合，Map中的元素顺序与它所返回的集合视图中的元素的迭代顺序相关，也就是说，Map本身是不保证有序性的，当然也有例外，比如TreeMap就对有序性做出了保证，这主要因为它是基于红黑树实现的。
所谓的集合视图就是由集合本身提供的一种访问数据的方式，同时对视图的任何修改也会影响到集合。好比Map.keySet()返回了它包含的key的集合，如果你调用了Map.remove(key)那么keySet.contains(key)也将返回false，再比如说Arrays.asList(T)可以把一个数组封装成一个List，这样你就可以通过List的API来访问和操作这些数据，如下列示例代码：
String[] strings = {"a", "b", "c"};
List<String> list = Arrays.asList(strings);
System.out.println(list.get(0)); // "a"
strings[0] = "d";
System.out.println(list.get(0)); // "d"
list.set(0, "e");
System.out.println(strings[0]); // "e"
是不是感觉很神奇，其实Arrays.asList()只是将传入的数组与Arrays中的一个内部类ArrayList（注意，它与java.util包下的ArrayList不是同一个）做了一个”绑定“，在调用get()时会直接根据下标返回数组中的元素，而调用set()时也会直接修改数组中对应下标的元素。相对于直接复制来说，集合视图的优点是内存利用率更高，假设你有一个数组，又很想使用List的API来操作它，那么你不用new一个ArrayList以拷贝数组中的元素，只需要一点额外的内存（通过Arrays.ArrayList对数组进行封装），原始数据依然是在数组中的，并不会复制成多份。
Map接口规范了Map数据结构的通用API（也含有几个用于简化操作的default方法，default是JDK8的新特性，它是接口中声明的方法的默认实现，即非抽象方法）并且还在内部定义了Entry接口（键值对的实体类），在JDK中提供的所有Map数据结构都实现了Map接口，下面为Map接口的源码（代码中的注释太长了，基本都是些实现的规范，为了篇幅我就尽量省略了）。
package java.util; import java.util.function.BiConsumer; import java.util.function.BiFunction; import java.util.function.Function; import java.io.Serializable; public interface Map<K,V> { // 查询操作 /** * 返回这个Map中所包含的键值对的数量，如果大于Integer.MAX_VALUE， * 则应该返回Integer.MAX_VALUE。 */ int size(); /** * Map是否为空。 */ boolean isEmpty(); /** * Map中是否包含key，如果是返回true，否则false。 */ boolean containsKey(Object key); /** * Map中是否包含value，如果是返回true，否则false。 */ boolean containsValue(Object value); /** * 根据key查找value，如果Map不包含该key，则返回null。 */ V get(Object key); // 修改操作 /** * 添加一对键值对，如果Map中已含有这个key，那么新value将覆盖掉旧value， * 并返回旧value，如果Map中之前没有这个key，那么返回null。 */ V put(K key, V value); /** * 删除指定key并返回之前的value，如果Map中没有该key，则返回null。 */ V remove(Object key); // 批量操作 /** * 将指定Map中的所有键值对批量添加到当前Map。 */ void putAll(Map<? extends K, ? extends V> m); /** * 删除Map中所有的键值对。 */ void clear(); // 集合视图 /** * 返回包含Map中所有key的Set，对该视图的所有修改操作会对Map产生同样的影响，反之亦然。 */ Set<K