在前面LZ詳細介紹了HashMap、HashTable、TreeMap的實現方法，從數據結構、實現原理、源碼分析三個方面進行闡述，對這個三個類應該有了比較清晰的了解,下面LZ就Map做一個簡單的總結。
推薦閱讀：
java提高篇（二三）—–HashMap
java提高篇（二五）—–HashTable
Java提高篇（二六）-----hashCode
Java提高篇（二七）—–TreeMap
首先先看Map的結構示意圖
Map：“鍵值”對映射的抽象接口。該映射不包括重復的鍵，一個鍵對應一個值。
SortedMap：有序的鍵值對接口，繼承Map接口。
NavigableMap：繼承SortedMap，具有了針對給定搜索目標返回最接近匹配項的導航方法的接口。
AbstractMap：實現了Map中的絕大部分函數接口。它減少了“Map的實現類”的重復編碼。
Dictionary：任何可將鍵映射到相應值的類的抽象父類。目前被Map接口取代。
TreeMap：有序散列表，實現SortedMap 接口，底層通過紅黑樹實現。
HashMap：是基于“拉鏈法”實現的散列表。底層采用“數組+鏈表”實現。
WeakHashMap：基于“拉鏈法”實現的散列表。
HashTable：基于“拉鏈法”實現的散列表。
總結如下：
他們之間的區別：
幾乎所有通用Map都使用哈希映射技術。對于我們程序員來說我們必須要對其有所了解。
哈希映射技術是一種就元素映射到數組的非常簡單的技術。由于哈希映射采用的是數組結果，那么必然存在一中用于確定任意鍵訪問數組的索引機制，該機制能夠提供一個小于數組大小的整數，我們將該機制稱之為哈希函數。在Java中我們不必為尋找這樣的整數而大傷腦筋，因為每個對象都必定存在一個返回整數值的hashCode方法，而我們需要做的就是將其轉換為整數，然后再將該值除以數組大小取余即可。如下：
[java] view plain copyint hashValue = Maths.abs(obj.hashCode()) % size; 下面是HashMap、HashTable的：[java] view plain copy----------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方法，該方法詳細展示了計算索引位置，將元素插入到適當的位置的全部過程：
HashMap的put方法展示了哈希映射的基本思想，其實如果我們查看其它的Map，發現其原理都差不多！
首先我們這樣假設，假設哈希映射的內部數組的大小只有1，所有的元素都將映射該位置（0），從而構成一條較長的鏈表。由于我們更新、訪問都要對這條鏈表進行線性搜索，這樣勢必會降低效率。我們假設，如果存在一個非常大數組，每個位置鏈表處都只有一個元素，在進行訪問時計算其 index 值就會獲得該對象，這樣做雖然會提高我們搜索的效率，但是它浪費了控件。誠然，雖然這兩種方式都是極端的，但是它給我們提供了一種優化思路：使用一個較大的數組讓元素能夠均勻分布。在Map有兩個會影響到其效率，一是容器的初始化大小、二是負載因子。
在哈希映射表中，內部數組中的每個位置稱作“存儲桶”(bucket)，而可用的存儲桶數（即內部數組的大小）稱作容量 (capacity)，我們為了使Map對象能夠有效地處理任意數的元素，將Map設計成可以調整自身的大小。我們知道當Map中的元素達到一定量的時候就會調整容器自身的大小，但是這個調整大小的過程其開銷是非常大的。調整大小需要將原來所有的元素插入到新數組中。我們知道index = hash(key) % length。這樣可能會導致原先沖突的鍵不在沖突，不沖突的鍵現在沖突的，重新計算、調整、插入的過程開銷是非常大的，效率也比較低下。所以，如果我們開始知道Map的預期大小值，將Map調整的足夠大，則可以大大減少甚至不需要重新調整大小，這很有可能會提高速度。下面是HashMap調整容器大小的過程，通過下面的代碼我們可以看到其擴容過程的復雜性：
[java] view plain copyvoid 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; } } }為了確認何時需要調整Map容器，Map使用了一個額外的參數并且粗略計算存儲容器的密度。在Map調整大小之前，使用”負載因子”來指示Map將會承擔的“負載量”，也就是它的負載程度，當容器中元素的數量達到了這個“負載量”，則Map將會進行擴容操作。負載因子、容量、Map大小之間的關系如下：負載因子 * 容量 > map大小 ----->調整Map大小。
例如：如果負載因子大小為0.75（HashMap的默認值），默認容量為11，則 11 * 0.75 = 8.25 = 8，所以當我們容器中插入第八個元素的時候，Map就會調整大小。
負載因子本身就是在控件和時間之間的折衷。當我使用較小的負載因子時，雖然降低了沖突的可能性，使得單個鏈表的長度減小了，加快了訪問和更新的速度，但是它占用了更多的控件，使得數組中的大部分控件沒有得到利用，元素分布比較稀疏，同時由于Map頻繁的調整大小，可能會降低性能。但是如果負載因子過大，會使得元素分布比較緊湊，導致產生沖突的可能性加大，從而訪問、更新速度較慢。所以我們一般推薦不更改負載因子的值，采用默認值0.75.
推薦閱讀：
java提高篇（二三）—–HashMap
java提高篇（二五）—–HashTable
Java提高篇（二六）-----hashCode
Java提高篇（二七）—–TreeMap
新聞熱點
疑難解答
