在前面LZ具體介紹了HashMap、HashTable、TreeMap的實作方法，從資料結構、實作原理、源代碼分析三個方面進行闡述，對這個三個類應該有了比較清晰的了解,以下LZ就Map做一個簡單的總結。
一、Map概述
首先先看Map的結構示意圖
Map：“鍵值”對映射的抽象接口。該映射不包含反複的鍵，一個鍵相應一個值。
SortedMap：有序的鍵值對接口，繼承Map接口。
NavigableMap：繼承SortedMap，具有了針對給定搜尋目标傳回最接近比對項的導航方法的接口。
AbstractMap：實作了Map中的絕大部分函數接口。
它減少了“Map的實作類”的反複編碼。
Dictionary：不論什麼可将鍵映射到相應值的類的抽象父類。
眼下被Map接口代替。
TreeMap：有序散清單，實作SortedMap 接口，底層通過紅黑樹實作。
HashMap：是基于“拉鍊法”實作的散清單。
底層採用“數組+連結清單”實作。
WeakHashMap：基于“拉鍊法”實作的散清單。
HashTable：基于“拉鍊法”實作的散清單。
總結例如以下：
二、内部哈希： 哈希映射技術
差點兒全部通用Map都使用哈希映射技術。對于我們程式猿來說我們必須要對其有所了解。
哈希映射技術是一種就元素映射到數組的很easy的技術。
因為哈希映射採用的是數組結果，那麼必定存在一中用于确定随意鍵訪問數組的索引機制，該機制可以提供一個小于數組大小的整數。我們将該機制稱之為哈希函數。
在Java中我們不必為尋找這種整數而大傷腦筋，因為每一個對象都必定存在一個傳回整數值的hashCode方法，而我們須要做的就是将其轉換為整數，然後再将該值除以數組大小取餘就可以。
例如以下：
int hashValue = Maths.abs(obj.hashCode()) % size; 以下是HashMap、HashTable的：
----------HashMap------------
//計算hash值
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//計算key的索引位置
static int indexFor(int h, int length) {
return h & (length-1);
}
-----HashTable--------------
int index = (hash & 0x7FFFFFFF) % tab.length; //确認該key的索引位置 位置的索引就代表了該節點在數組中的位置。下圖是哈希映射的基本原理圖：
在該圖中1-4步驟是找到該元素在數組中位置，5-8步驟是将該元素插入數組中。在插入的過程中會遇到一點點小挫折。在衆多肯能存在多個元素他們的hash值是一樣的。這樣就會得到同樣的索引位置，也就說多個元素會映射到同樣的位置，這個過程我們稱之為“沖突”。
解決沖突的辦法就是在索引位置處插入一個連結清單。并簡單地将元素加入到此連結清單。當然也不是簡單的插入，在HashMap中的處理步驟例如以下：擷取索引位置的連結清單。假設該連結清單為null，則将該元素直接插入，否則通過比較是否存在與該key同樣的key，若存在則覆寫原來key的value并傳回舊值，否則将該元素儲存在鍊頭（最先儲存的元素放在鍊尾）。以下是HashMap的put方法，該方法具體展示了計算索引位置。将元素插入到适當的位置的全部過程：
public V put(K key, V value) {
//當key為null，調用putForNullKey方法，儲存null與table第一個位置中，這是HashMap同意為null的原因
if (key == null)
return putForNullKey(value);
//計算key的hash值
int hash = hash(key.hashCode());
//計算key hash 值在 table 數組中的位置
int i = indexFor(hash, table.length);
//從i出開始疊代 e,推斷是否存在同樣的key
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//推斷該條鍊上是否有hash值同樣的(key同樣)
//若存在同樣，則直接覆寫value。傳回舊value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //舊值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //傳回舊值
}
}
//改動次數添加1
modCount++;
//将key、value加入至i位置處
addEntry(hash, key, value, i);
return null;
} HashMap的put方法展示了哈希映射的基本思想，事實上假設我們檢視其他的Map。發現其原理都差點兒相同！
三、Map優化
首先我們這樣假設，假設哈希映射的内部數組的大小僅僅有1。全部的元素都将映射該位置（0），進而構成一條較長的連結清單。因為我們更新、訪問都要對這條連結清單進行線性搜尋。這樣勢必會減少效率。我們假設，假設存在一個很大數組，每一個位置連結清單處都僅僅有一個元素。在進行訪問時計算其 index 值就會獲得該對象，這樣做盡管會提高我們搜尋的效率，可是它浪費了控件。誠然，盡管這兩種方式都是極端的，可是它給我們提供了一種優化思路：使用一個較大的數組讓元素可以均勻分布。在Map有兩個會影響到其效率，一是容器的初始化大小、二是負載因子。
3.1、調整實作大小
在哈希映射表中。内部數組中的每一個位置稱作“存儲桶”(bucket)。而可用的存儲桶數（即内部數組的大小）稱作容量 (capacity)，我們為了使Map對象可以有效地處理随意數的元素，将Map設計成可以調整自身的大小。
我們知道當Map中的元素達到一定量的時候就會調整容器自身的大小，可是這個調整大小的過程其開銷是很大的。
調整大小須要将原來全部的元素插入到新數組中。我們知道index = hash(key) % length。
這樣可能會導緻原先沖突的鍵不在沖突。不沖突的鍵如今沖突的。又一次計算、調整、插入的過程開銷是很大的，效率也比較低下。
是以，假設我們開始知道Map的預期大小值，将Map調整的足夠大，則可以大大減少甚至不須要又一次調整大小，這很有可能會提快速度。
以下是HashMap調整容器大小的過程，通過以下的代碼我們可以看到其擴容過程的複雜性：
void resize(int newCapacity) {
Entry[] oldTable = table; //原始容器
int oldCapacity = oldTable.length; //原始容器大小
if (oldCapacity == MAXIMUM_CAPACITY) { //是否超過最大值：1073741824
threshold = Integer.MAX_VALUE;
return;
}
//新的數組：大小為 oldCapacity * 2
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
/*
* 又一次計算閥值 = newCapacity * loadFactor > MAXIMUM_CAPACITY + 1 ?
* newCapacity * loadFactor :MAXIMUM_CAPACITY + 1
*/
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//将元素插入到新數組中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
} 3.2、負載因子
為了确認何時須要調整Map容器，Map使用了一個額外的參數而且粗略計算存儲容器的密度。在Map調整大小之前，使用”負載因子”來訓示Map将會承擔的“負載量”，也就是它的負載程度，當容器中元素的數量達到了這個“負載量”，則Map将會進行擴容操作。負載因子、容量、Map大小之間的關系例如以下：負載因子 * 容量 > map大小 ----->調整Map大小。
比如：假設負載因子大小為0.75（HashMap的預設值），預設容量為11，則 11 * 0.75 = 8.25 = 8。是以當我們容器中插入第八個元素的時候，Map就會調整大小。
負載因子本身就是在控件和時間之間的折衷。當我使用較小的負載因子時。盡管減少了沖突的可能性。使得單個連結清單的長度減小了，加快了訪問和更新的速度。可是它占用了很多其他的控件。使得數組中的大部分控件沒有得到利用，元素分布比較稀疏，同一時候因為Map頻繁的調整大小。可能會減少性能。
可是假設負載因子過大，會使得元素分布比較緊湊，導緻産生沖突的可能性加大，進而訪問、更新速度較慢。是以我們一般推薦不更改負載因子的值，採用預設值0.75.
最後
-----原文出自:http://cmsblogs.com/?p=1212,請尊重作者辛勤勞動成果,轉載說明出處.
-----個人網站:http://cmsblogs.com