Map的基本实现，包括：HashMap、TreeMap、LinkedHashMap、WeekHashMap、ConcurrentHashMap、IdentityHashMap。它们都有同样的基本接口Map，但是行为特性各不相同，这表现在效率，键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程程序中工作和判定“键”等价的策略等方面。
java集合
HashMap
Map基于散列表的实现（它取代了Hashtable）。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量和负载因子，以调整容器的性能。
LinkedHashMap
类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用（LRU）的次序。只比HashMap慢一点；而在迭代访问时反而更快，因为它使用链表维护内部次序。
TreeMap
基于红黑树的实现。查看“键”或“键值对”时，它们会被排序（次序由Comparable或Comparator决定）。TreeMap的特点在于，所得到的结果是经过排序的，TreeMap是唯一带有subMap方法的Map，它可以返回一个子树。
WeekHashMap
弱键（week key）映射，允许释放映射所指向的对象；这是为解决某些类特殊问题而设计的。如果映射之外没有引用指向某个“键”，则此“键”可以被垃圾收集器回收。
ConcurrentHashMap
一种线程安全的Map，它不涉及同步加锁。
IdentityHashMap
使用==代替equals对“键”进行比较的散列映射，专为解决特殊问题而设计。
Map接口中主要的方法
containsKey(Object key)：如果此映射包含指定键的映射关系，则返回 true；
containsValue(Object value)：如果此映射将一个或多个键映射到指定值，则返回 true；
entrySet()：返回此映射中包含的映射关系的 Set 视图；
get(Object key)：返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null；
keySet()：返回此映射中包含的键的 Set 视图；
put(K key, V value)：将指定的值与此映射中的指定键关联（可选操作）。
AbstractMap提供 Map 接口的骨干实现，以最大限度地减少实现Map接口所需的工作。要实现不可修改的映射，编程人员只需扩展此类并提供 entrySet 方法的实现即可，该方法将返回映射的映射关系Set视图。通常，返回的 set 将依次在AbstractSet上实现。此 set 不支持add或remove方法，其迭代器也不支持 remove 方法。要实现可修改的映射，编程人员必须另外重写此类的 put 方法（否则将抛出 UnsupportedOperationException），entrySet().iterator() 返回的迭代器也必须另外实现其remove方法。
LinkedHashMap返回的结果是其插入次序
LinkedHashMap继承自HashMap，所以它比HashMap的性能略差，但是可以维护元素间的插入顺序（使用一个双向链表来保存顺序）：
private transient Entry<K,V> header;
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;
…….//省略
}
当要调用put方法插入元素时，会调用HashMap的put方法，这个方法会调用addEntry()方法，这个方法在LinkedHashMap中被重定义了：
//LinkedHashMap的addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);//调用HashMap中的addEntry方法，会创建结点，同时会维护新创建的结点到双向链表中
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
//HashMap中的addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//LinkedHashMap中的createEntry，覆盖HashMap中的createEntry
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
从以上代码中我们可以看到LinkedHashMap的put方法的过程，首先LinkedHashMap中没有put方法，所以会调用HashMap中的put方法，这个put方法会检查数据是否在Map中，如果不在就会调用addEntry方法，由于LinkedHashMap覆盖了父类的addEntry方法，所以会直接调用LinkedHashMap的addEntry方法，这个方法中又调用了HashMap的addEntry方法，addEntry又调用了createEntry方法，这个方法也是LinkedHashMap覆盖了HashMap的，它会创建结点到table中，同时会维护Entry（继承自HashMap.Entry的LinkedHashMap.Entry）的前后元素。
//HashMap中的createEntry方法，对比以上LinkedHashMap中的createEntry方法发现，除了将Entry放入桶中之外，LinkedHashMap还维护了Entry指向之前元素和之后元素的指针
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
简单来讲，LinkedHashMap中的Entry是带有指向在它自己插入Map之前和之后的元素引用的对象，在put元素时，首先检查数据是否已经在Map中，如果不在就创建这个Entry，同时还要把这个Entry记录插入到之前元素构成的链表中（并没有真的简单的创建了个链表结点，而是这个链表本身就是这些Entry元素构成的）。这些Entry本身不但是Map中table的元素，还是链表元素。
在进行遍历时，它使用的是KeyIterator，而KeyIterator继承自LinkedHashIterator，在LinkedHashIterator内部有链表的头指针指向的下一个元素：
Entry<K,V> nextEntry = header.after;
由于这些Entry本身是链表元素，也是table中元素，故直接找到其后继就可以得到所有元素。剩下的遍历过程就是对一个链表的遍历了，每遍历到一个Entry就可以获得它的key和value。
此外，LinkedHashMap还能维护一个最近最少访问的序列，其本质还是维护Entry指针，每次使用get访问元素时，都会将这个元素插入Map尾部，这样链表头部就是最近访问次数最少的元素了，整个链表就是从近期访问最少到近期访问最多的顺序。
其实现方式是，在get中找到要get的元素后调用元素的recordAccess方法，这个方法就把这个Entry的前后指针进行了调整。
//LinkedHashMap的get方法
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);//调整指针
return e.value;
}
//Entry的recordAccess方法，参数m就是一个LinkedHashMap
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {//是否按照最近最少访问排列
lm.modCount++;
remove();//从当前链中删除自己
addBefore(lm.header);//加入到链表尾部
}
}
总的来说，对于所有的集合类来说，对于List，如果随机存取多于修改首尾元素的可能，则应该选择ArrayList，如果要实现类似队列或者栈的功能或者首尾添加的功能较多，则应该选择LinkedList；对于Set，HashSet是常用的Set，毕竟通常对Set操作都是插入和查询，但是如果希望产生带有排序的Set则可以使用TreeSet，希望记录插入顺序则要使用LinkedHashSet；而Map和Set类似，如果需要快速的查询和添加，则可以用HashMap，如果需要Map中的元素按照一定的规则排序，则可以用TreeMap，如果需要记录数据加入Map的顺序，或者需要使用最近最少使用的规则，则可以用LinkedHashMap。
