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<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。