Map的基本實現(xiàn)跨琳，包括：HashMap自点、TreeMap、LinkedHashMap脉让、WeekHashMap桂敛、ConcurrentHashMap、IdentityHashMap溅潜。它們都有同樣的基本接口Map术唬，但是行為特性各不相同，這表現(xiàn)在效率滚澜，鍵值對的保存及呈現(xiàn)次序粗仓、對象的保存周期、映射表如何在多線程程序中工作和判定“鍵”等價的策略等方面设捐。
java集合
HashMap
Map基于散列表的實現(xiàn)（它取代了Hashtable）借浊。插入和查詢“鍵值對”的開銷是固定的÷苷校可以通過構造器設置容量和負載因子巴碗，以調整容器的性能。
LinkedHashMap
類似于HashMap即寒，但是迭代遍歷它時，取得“鍵值對”的順序是其插入次序召噩，或者是最近最少使用（LRU）的次序母赵。只比HashMap慢一點；而在迭代訪問時反而更快具滴，因為它使用鏈表維護內部次序凹嘲。
TreeMap
基于紅黑樹的實現(xiàn)。查看“鍵”或“鍵值對”時构韵，它們會被排序（次序由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)：將指定的值與此映射中的指定鍵關聯(lián)（可選操作）。
AbstractMap提供 Map 接口的骨干實現(xiàn)碍遍，以最大限度地減少實現(xiàn)Map接口所需的工作定铜。要實現(xiàn)不可修改的映射，編程人員只需擴展此類并提供 entrySet 方法的實現(xiàn)即可怕敬，該方法將返回映射的映射關系Set視圖揣炕。通常，返回的 set 將依次在AbstractSet上實現(xiàn)东跪。此 set 不支持add或remove方法畸陡，其迭代器也不支持 remove 方法。要實現(xiàn)可修改的映射虽填，編程人員必須另外重寫此類的 put 方法（否則將拋出 UnsupportedOperationException）丁恭，entrySet().iterator() 返回的迭代器也必須另外實現(xiàn)其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方法贡必，會創(chuàng)建結點，同時會維護新創(chuàng)建的結點到雙向鏈表中
// 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方法會檢查數(shù)據是否在Map中理逊，如果不在就會調用addEntry方法，由于LinkedHashMap覆蓋了父類的addEntry方法盒揉，所以會直接調用LinkedHashMap的addEntry方法晋被，這個方法中又調用了HashMap的addEntry方法，addEntry又調用了createEntry方法刚盈，這個方法也是LinkedHashMap覆蓋了HashMap的羡洛，它會創(chuàng)建結點到table中，同時會維護Entry（繼承自HashMap.Entry的LinkedHashMap.Entry）的前后元素藕漱。
//HashMap中的createEntry方法欲侮，對比以上LinkedHashMap中的createEntry方法發(fā)現(xiàn)，除了將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元素時橄仍，首先檢查數(shù)據是否已經在Map中韧涨，如果不在就創(chuàng)建這個Entry，同時還要把這個Entry記錄插入到之前元素構成的鏈表中（并沒有真的簡單的創(chuàng)建了個鏈表結點侮繁，而是這個鏈表本身就是這些Entry元素構成的）虑粥。這些Entry本身不但是Map中table的元素，還是鏈表元素宪哩。
在進行遍歷時娩贷，它使用的是KeyIterator，而KeyIterator繼承自LinkedHashIterator锁孟，在LinkedHashIterator內部有鏈表的頭指針指向的下一個元素：
Entry<K,V> nextEntry = header.after;
由于這些Entry本身是鏈表元素彬祖，也是table中元素，故直接找到其后繼就可以得到所有元素品抽。剩下的遍歷過程就是對一個鏈表的遍歷了涧至，每遍歷到一個Entry就可以獲得它的key和value。
此外桑包，LinkedHashMap還能維護一個最近最少訪問的序列，其本質還是維護Entry指針纺非，每次使用get訪問元素時哑了，都會將這個元素插入Map尾部赘方，這樣鏈表頭部就是最近訪問次數(shù)最少的元素了，整個鏈表就是從近期訪問最少到近期訪問最多的順序弱左。
其實現(xiàn)方式是窄陡，在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方法跳夭，參數(shù)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模狭，如果要實現(xiàn)類似隊列或者棧的功能或者首尾添加的功能較多颈抚，則應該選擇LinkedList；對于Set嚼鹉，HashSet是常用的Set贩汉，畢竟通常對Set操作都是插入和查詢，但是如果希望產生帶有排序的Set則可以使用TreeSet锚赤，希望記錄插入順序則要使用LinkedHashSet匹舞；而Map和Set類似，如果需要快速的查詢和添加线脚，則可以用HashMap赐稽，如果需要Map中的元素按照一定的規(guī)則排序，則可以用TreeMap酒贬，如果需要記錄數(shù)據加入Map的順序又憨，或者需要使用最近最少使用的規(guī)則，則可以用LinkedHashMap锭吨。
