Map的基本实现，包括：HashMap、TreeMap、LinkedHashMap、WeekHashMap、ConcurrentHashMap、IdentityHashMap。它们都有同样的基本接口Map，但是行为特性各不相同，这表现在效率，键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程程序中工作和判定“键”等价的策略等方面。
java集合
java集合图.gif
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 header;
private static class Entry extends HashMap.Entry {
// These fields comprise the doubly linked list used for iteration.
Entry 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 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 old = table[bucketIndex];
Entry 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 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 nextEntry = header.after;
由于这些Entry本身是链表元素，也是table中元素，故直接找到其后继就可以得到所有元素。剩下的遍历过程就是对一个链表的遍历了，每遍历到一个Entry就可以获得它的key和value。
此外，LinkedHashMap还能维护一个最近最少访问的序列，其本质还是维护Entry指针，每次使用get访问元素时，都会将这个元素插入Map尾部，这样链表头部就是最近访问次数最少的元素了，整个链表就是从近期访问最少到近期访问最多的顺序。
其实现方式是，在get中找到要get的元素后调用元素的recordAccess方法，这个方法就把这个Entry的前后指针进行了调整。
//LinkedHashMap的get方法
public V get(Object key) {
Entry e = (Entry)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);//调整指针
return e.value;
}
//Entry的recordAccess方法，参数m就是一个LinkedHashMap
void recordAccess(HashMap m) {
LinkedHashMap lm = (LinkedHashMap)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。