Map的基本實(shí)現(xiàn)，包括：HashMap、TreeMap、LinkedHashMap、WeekHashMap、ConcurrentHashMap、IdentityHashMap。它們都有同樣的基本接口Map，但是行為特性各不相同，這表現(xiàn)在效率，鍵值對(duì)的保存及呈現(xiàn)次序、對(duì)象的保存周期、映射表如何在多線程程序中工作和判定“鍵”等價(jià)的策略等方面。

java集合

java集合圖.gif

HashMap
Map基于散列表的實(shí)現(xiàn)（它取代了Hashtable）。插入和查詢“鍵值對(duì)”的開銷是固定的?？梢酝ㄟ^構(gòu)造器設(shè)置容量和負(fù)載因子，以調(diào)整容器的性能。

LinkedHashMap
類似于HashMap，但是迭代遍歷它時(shí)，取得“鍵值對(duì)”的順序是其插入次序，或者是最近最少使用（LRU）的次序。只比HashMap慢一點(diǎn)；而在迭代訪問時(shí)反而更快，因?yàn)樗褂面湵砭S護(hù)內(nèi)部次序。

TreeMap
基于紅黑樹的實(shí)現(xiàn)。查看“鍵”或“鍵值對(duì)”時(shí)，它們會(huì)被排序（次序由Comparable或Comparator決定）。TreeMap的特點(diǎn)在于，所得到的結(jié)果是經(jīng)過排序的，TreeMap是唯一帶有subMap方法的Map，它可以返回一個(gè)子樹。

WeekHashMap
弱鍵（week key）映射，允許釋放映射所指向的對(duì)象；這是為解決某些類特殊問題而設(shè)計(jì)的。如果映射之外沒有引用指向某個(gè)“鍵”，則此“鍵”可以被垃圾收集器回收。

ConcurrentHashMap
一種線程安全的Map，它不涉及同步加鎖。

IdentityHashMap
使用==代替equals對(duì)“鍵”進(jìn)行比較的散列映射，專為解決特殊問題而設(shè)計(jì)。

Map接口中主要的方法

containsKey(Object key)：如果此映射包含指定鍵的映射關(guān)系，則返回 true；
containsValue(Object value)：如果此映射將一個(gè)或多個(gè)鍵映射到指定值，則返回 true；
entrySet()：返回此映射中包含的映射關(guān)系的 Set 視圖；
get(Object key)：返回指定鍵所映射的值；如果此映射不包含該鍵的映射關(guān)系，則返回 null；
keySet()：返回此映射中包含的鍵的 Set 視圖；
put(K key, V value)：將指定的值與此映射中的指定鍵關(guān)聯(lián)（可選操作）。

AbstractMap提供 Map 接口的骨干實(shí)現(xiàn)，以最大限度地減少實(shí)現(xiàn)Map接口所需的工作。要實(shí)現(xiàn)不可修改的映射，編程人員只需擴(kuò)展此類并提供 entrySet 方法的實(shí)現(xiàn)即可，該方法將返回映射的映射關(guān)系Set視圖。通常，返回的 set 將依次在AbstractSet上實(shí)現(xiàn)。此 set 不支持add或remove方法，其迭代器也不支持 remove 方法。要實(shí)現(xiàn)可修改的映射，編程人員必須另外重寫此類的 put 方法（否則將拋出 UnsupportedOperationException），entrySet().iterator() 返回的迭代器也必須另外實(shí)現(xiàn)其remove方法。

LinkedHashMap返回的結(jié)果是其插入次序

LinkedHashMap繼承自HashMap，所以它比HashMap的性能略差，但是可以維護(hù)元素間的插入順序（使用一個(gè)雙向鏈表來(lái)保存順序）：

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;  
        …….//省略  
}  

當(dāng)要調(diào)用put方法插入元素時(shí)，會(huì)調(diào)用HashMap的put方法，這個(gè)方法會(huì)調(diào)用addEntry()方法，這個(gè)方法在LinkedHashMap中被重定義了：

//LinkedHashMap的addEntry方法  
void addEntry(int hash, K key, V value, int bucketIndex) {  
        super.addEntry(hash, key, value, bucketIndex);//調(diào)用HashMap中的addEntry方法，會(huì)創(chuàng)建結(jié)點(diǎn)，同時(shí)會(huì)維護(hù)新創(chuàng)建的結(jié)點(diǎn)到雙向鏈表中  
        // 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方法，所以會(huì)調(diào)用HashMap中的put方法，這個(gè)put方法會(huì)檢查數(shù)據(jù)是否在Map中，如果不在就會(huì)調(diào)用addEntry方法，由于LinkedHashMap覆蓋了父類的addEntry方法，所以會(huì)直接調(diào)用LinkedHashMap的addEntry方法，這個(gè)方法中又調(diào)用了HashMap的addEntry方法，addEntry又調(diào)用了createEntry方法，這個(gè)方法也是LinkedHashMap覆蓋了HashMap的，它會(huì)創(chuàng)建結(jié)點(diǎn)到table中，同時(shí)會(huì)維護(hù)Entry（繼承自HashMap.Entry的LinkedHashMap.Entry）的前后元素。

//HashMap中的createEntry方法，對(duì)比以上LinkedHashMap中的createEntry方法發(fā)現(xiàn)，除了將Entry放入桶中之外，LinkedHashMap還維護(hù)了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++;  
}  

簡(jiǎn)單來(lái)講，LinkedHashMap中的Entry是帶有指向在它自己插入Map之前和之后的元素引用的對(duì)象，在put元素時(shí)，首先檢查數(shù)據(jù)是否已經(jīng)在Map中，如果不在就創(chuàng)建這個(gè)Entry，同時(shí)還要把這個(gè)Entry記錄插入到之前元素構(gòu)成的鏈表中（并沒有真的簡(jiǎn)單的創(chuàng)建了個(gè)鏈表結(jié)點(diǎn)，而是這個(gè)鏈表本身就是這些Entry元素構(gòu)成的）。這些Entry本身不但是Map中table的元素，還是鏈表元素。
在進(jìn)行遍歷時(shí)，它使用的是KeyIterator，而KeyIterator繼承自LinkedHashIterator，在LinkedHashIterator內(nèi)部有鏈表的頭指針指向的下一個(gè)元素：

Entry<K,V> nextEntry = header.after;

由于這些Entry本身是鏈表元素，也是table中元素，故直接找到其后繼就可以得到所有元素。剩下的遍歷過程就是對(duì)一個(gè)鏈表的遍歷了，每遍歷到一個(gè)Entry就可以獲得它的key和value。

此外，LinkedHashMap還能維護(hù)一個(gè)最近最少訪問的序列，其本質(zhì)還是維護(hù)Entry指針，每次使用get訪問元素時(shí)，都會(huì)將這個(gè)元素插入Map尾部，這樣鏈表頭部就是最近訪問次數(shù)最少的元素了，整個(gè)鏈表就是從近期訪問最少到近期訪問最多的順序。

其實(shí)現(xiàn)方式是，在get中找到要get的元素后調(diào)用元素的recordAccess方法，這個(gè)方法就把這個(gè)Entry的前后指針進(jìn)行了調(diào)整。

//LinkedHashMap的get方法  
public V get(Object key) {  
        Entry<K,V> e = (Entry<K,V>)getEntry(key);  
        if (e == null)  
            return null;  
        e.recordAccess(this);//調(diào)整指針  
        return e.value;  
}  
//Entry的recordAccess方法，參數(shù)m就是一個(gè)LinkedHashMap  
void recordAccess(HashMap<K,V> m) {  
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
        if (lm.accessOrder) {//是否按照最近最少訪問排列  
            lm.modCount++;  
            remove();//從當(dāng)前鏈中刪除自己  
            addBefore(lm.header);//加入到鏈表尾部  
        }  
}  

總的來(lái)說，對(duì)于所有的集合類來(lái)說，對(duì)于List，如果隨機(jī)存取多于修改首尾元素的可能，則應(yīng)該選擇ArrayList，如果要實(shí)現(xiàn)類似隊(duì)列或者棧的功能或者首尾添加的功能較多，則應(yīng)該選擇LinkedList；對(duì)于Set，HashSet是常用的Set，畢竟通常對(duì)Set操作都是插入和查詢，但是如果希望產(chǎn)生帶有排序的Set則可以使用TreeSet，希望記錄插入順序則要使用LinkedHashSet；而Map和Set類似，如果需要快速的查詢和添加，則可以用HashMap，如果需要Map中的元素按照一定的規(guī)則排序，則可以用TreeMap，如果需要記錄數(shù)據(jù)加入Map的順序，或者需要使用最近最少使用的規(guī)則，則可以用LinkedHashMap。