前兩篇寫了Collection體系的List下的ArrayList與LinkedList，另外一部分是Set集合下的集合類，但是Set集合的實作類基本是由Map集合的實作類實作的，是以先分析一下重要的HashMap。
數組存儲區間是連續的，占用記憶體嚴重，故空間複雜的很大。但數組的二分查找時間複雜度小，為O(1)；數組的特點是：尋址容易，插入和删除困難；連結清單存儲區間離散，占用記憶體比較寬松，故空間複雜度很小，但時間複雜度很大，達O（N）。連結清單的特點是：尋址困難，插入和删除容易。綜合兩者的特性，做出一種尋址容易，插入删除也容易的資料結構。
由第一篇綜述JDK源碼解析集合篇–綜述 可以看到HashMap實作了Map接口。
類定義為：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
在上邊的定義，我們可能會很奇怪，為什麼HashMap繼承了AbstractMap還要去實作Map接口呢，而且在HashSet，LinkedHashSet，LinkedHashMap都出現了這種定義，對于這個問題有很多解釋，但集合類的作者Josh Bloch 承認這是個錯誤，具體可以看StackOverFlower上的解釋Why does LinkedHashSet extend HashSet and implement Set 。
對于Map集合，我們常見的也就：HashMap，LinkedHashMap，Hashtable與TreeMap。由于HashMap中知識點很多，是以在面試中經常會考HashMap的實作原理。
HashMap是一種非常常見、友善和有用的集合，是一種鍵值對（K-V）形式（哈希表）的存儲結構，下面将還是用圖示的方式解讀HashMap的實作原理，
下邊關于HashMap的特點可做個總結：
HashMap是否允許空 ———– Key和Value都允許為空
HashMap是否允許重複資料——— Key重複會覆寫、Value允許重複（但hash可能會重複。沖突）
HashMap是否有序 ———無序，特别說明這個無序指的是周遊HashMap的時候，得到的元素的順序基本不可能是put的順序
HashMap是否線程安全———非線程安全（可能會出現死循環）
HashMap源碼
閱讀其實作，我們首先要看它的底層存儲結構是什麼，從結構實作來講，HashMap是數組+連結清單+紅黑樹（JDK1.8增加了紅黑樹部分）實作的，如下如所示。
其實也就是利用哈希表（散清單）這種資料結構來實作的。關于哈希表：散清單（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行通路的資料結構。也就是說，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散清單。這也就是我們的table數組（包括用來解決沖突的連結清單結構）。
下圖給出HashMap的字段：
從HashMap的屬性值，我們可以很好了解上邊的說法。我們可以看一下Node的定義：
//但連結清單結構
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
要注意：在JDK1.8後，加入了紅黑樹進行優化，存儲紅黑樹的是TreeNode：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
我們從代碼中可以看到，TreeNode加入相應的紅黑樹的定義屬性，TreeNode是Node的子類，是以table數組就定義的是Node[]，這并不會影響後邊轉紅黑樹的操作。
字段分析
HashMap就是使用哈希表來存儲的。哈希表為解決沖突，可以采用開放位址法和鍊位址法等來解決問題，Java中HashMap采用了鍊位址法。鍊位址法，簡單來說，就是數組加連結清單的結合。在每個數組元素上都一個連結清單結構，當資料被Hash後，得到數組下标，把資料放在對應下标元素的連結清單上。
注意：如果哈希桶數組很大，即使較差的Hash算法也會比較分散，如果哈希桶數組數組很小，即使好的Hash算法也會出現較多碰撞，是以就需要在空間成本和時間成本之間權衡，其實就是在根據實際情況确定哈希桶數組的大小，并在此基礎上設計好的hash算法減少Hash碰撞。那麼通過什麼方式來控制map使得Hash碰撞的機率又小，哈希桶數組（Node[] table）占用空間又少呢？答案就是好的Hash算法和擴容機制。
//初始化node數組大小為16
//The default initial capacity - MUST be a power of two. 這跟hash算法有關
static final int DEFAULT_INITIAL_CAPACITY = << ; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = << ;
//預設負載因子
static final float DEFAULT_LOAD_FACTOR = f;//填充比
//當add一個元素到某個位桶，其連結清單長度達到8時将連結清單轉換為紅黑樹
static final int TREEIFY_THRESHOLD = ;
//由樹轉換成連結清單的門檻值UNTREEIFY_THRESHOLD 當進行删除操作時，轉成連結清單的的門檻值
static final int UNTREEIFY_THRESHOLD = ;
//在轉變成樹之前，還會有一次判斷，隻有鍵值對數量（size）大于 64 才會發生轉換。這是為了避免在哈希表建立初期，
//多個鍵值對恰好被放入了同一個連結清單中而導緻不必要的轉化。這個至少是TREEIFY_THRESHOLD 的4倍
static final int MIN_TREEIFY_CAPACITY = ;
transient Node<k,v>[] table;//存儲元素的數組
transient Set<map.entry<k,v>> entrySet;
//存放元素node的個數
transient int size;
//被修改的次數fast-fail機制 記錄結構變化的次數（主要是删除添加）
transient int modCount;
//臨界值 當實際大小(容量*填充比)超過臨界值時，會進行擴容 也就是。
//threshold = length * Load factor 當size>threshold 時，進行擴容
int threshold;
final float loadFactor; //負載因子
結合負載因子的定義公式可知，threshold就是在此Load factor和length(數組長度)對應下允許的最大元素數目，超過這個數目就重新resize(擴容)，擴容後的HashMap容量是之前容量的兩倍。預設的負載因子0.75是對空間和時間效率的一個平衡選擇，建議大家不要修改，除非在時間和空間比較特殊的情況下，如果記憶體空間很多而又對時間效率要求很高，可以降低負載因子Load factor的值；相反，如果記憶體空間緊張而對時間效率要求不高，可以增加負載因子loadFactor的值，這個值可以大于1。
當在建立HashMap時，可以指定數組的初始化大小和負載因子。其構造器源碼為：
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
看上邊的代碼時，不知道大家有沒有想，到底table數組和threshold都在哪初始化的，我在看的時候也是找了好久，由構造器我們可以看到，這時候還沒有進行數組初始化工作，當我們添加元素時：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//當table還沒初始化時，就進行擴容操作，也就是在這裡進行的初始化
if ((tab = table) == null || (n = tab.length) == )
n = (tab = resize()).length;
}
在resize()函數中，你可以看到起初始化工作，在這裡我不詳細解釋其代碼，在後邊擴容講解時，在詳細介紹。其實就是下邊的代碼：
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
hash原理
為了減少沖突，設計好的哈希函數是非常必要的。如果完全沒沖突，則HashMap增删該查的時間複雜度将為O(1)。這裡還要強調一下：當使用某個位置的連結清單長度大于8時，轉化為紅黑樹，使查找/删除/添加的時間複雜度是O(logn)，而不會是O(n)。 在沖突的那個bin上插入的時間複雜度是O(n)，源碼是插入到連結清單最後，因為它要先尋址，因為它先要查找是否有重複的key，再執行插入。
為了減少沖突：在HashMap中，哈希桶數組table的長度length大小必須為2的n次方(一定是合數)，這是一種非正常的設計，正常的設計是把桶的大小設計為素數。相對來說素數導緻沖突的機率要小于合數，具體證明可以參考http://blog.csdn.net/liuqiyao_01/article/details/14475159，Hashtable初始化桶大小為11，就是桶大小設計為素數的應用（Hashtable擴容後不能保證還是素數）。HashMap采用這種非正常設計，主要是為了在取模和擴容時做優化，同時為了減少沖突，HashMap定位哈希桶索引位置時，也加入了高位參與運算的過程。
為什麼要把length設定為2的n次方，這在後邊的雜湊演算法中有應用：JDK1.8的哈希函數為：
static final int hash(Object key) {
int h;
return (key == null) ? : (h = key.hashCode()) ^ (h >>> );
}
這裡的哈希函數就是3步：1 取key的hashcode值 2 将高位與低位進行運算（通過hashCode()的高16位異或低16位實作的，主要是從速度、功效、品質來考慮的，這麼做可以在數組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷。） 3 取模定位到數組位置
我們會思考，為什麼這裡沒有定位取模這一步呢，這是因為這一步運算又被融合到了put操作中，我們可以單獨取出這一個操作：
tab[i = (n - ) & hash]
我們這裡的取模運算非常巧妙地運用了數組長度也就是n隻能是2的n次幂的特點，利用&操作代替mod操作，提高了效率。具體的解釋可以看下圖：
put方法解析
添加元素的流程圖為：
下邊結合代碼來解釋一下此過程：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//table為null，則說明table數組還沒有進行初始化，在resize中初始化
if ((tab = table) == null || (n = tab.length) == )
n = (tab = resize()).length;
//如果定位到table[i]沒元素，則直接放入到該位置，并符p指派
if ((p = tab[i = (n - ) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果已經有元素，則進行沖突解決
else {
Node<K,V> e; K k;
//p是table[i]的Node值，如果插入的Node的key與此Node值相等（hash和equals相等）
//則将e指派為p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷是否是TreeNode，是的話執行紅黑樹插入，不是的話執行連結清單插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//連結清單插入
else {
for (int binCount = ; ; ++binCount) {
//找到連結清單尾部
if ((e = p.next) == null) {
//插入到連結清單尾部
p.next = newNode(hash, key, value, null);
//如果達到8，則進行樹化
if (binCount >= TREEIFY_THRESHOLD - ) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//若key相等，則e是不為null的
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//e不為null，說明有key重複，則直接覆寫e指向的node的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//size+1，看是否需要擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上邊的源碼中，邏輯非常清楚，實作也非常巧妙，看完很有感覺。從源碼中，可以看到，新put的node，如果有沖突，會放到連結清單尾部。
上邊的紅黑樹插入，以及樹化操作時紅黑樹的内容，較為複雜，這裡先不進行解釋。關于紅黑樹可參看：
紅黑樹概念、紅黑樹的插入及旋轉操作詳細解讀 和紅黑樹的移除節點操作 。
下邊我們重點看一下HashMap的擴容過程。
擴容機制
下邊是JDK1.8 hashMap的擴容代碼：在代碼中進行注釋解釋。
在開始之前，因為涉及rehash過程，在解釋代碼之前，必須要搞明白jdk1.8的一個優化點：在進行rehash時，1.7是重新計算hash然後進行&(n-1)定位的，但是jdk1.8進行了優化，解決了重新計算hash進行定位的計算。經過觀測可以發現，我們使用的是2次幂的擴充(指長度擴為原來2倍)，是以，元素的位置要麼是在原位置，要麼是在原位置再移動2次幂的位置。看下圖可以明白這句話的意思，相當于多了一個高位1。
是以，我們在擴充HashMap的時候，不需要像JDK1.7的實作那樣重新計算hash，隻需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”。這個設計确實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認為是随機的，是以resize的過程，均勻的把之前的沖突的節點分散到新的bucket了。
其實我覺得這樣也并沒有進行多少優化，因為1.7進行定位時：hash也是知道的，隻是進行hash&(n-1)進行定位的，與hash&n == 1{i+n} 都是位運算，也差不多。
但這也是為什麼長度取2的幂的另一個應用。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
//完成擴容（容量變為原來的2倍），且完成rehash
final Node<K,V>[] resize() {
//獲得原來的table數組
Node<K,V>[] oldTab = table;
//原table數組的容量
int oldCap = (oldTab == null) ? : oldTab.length;
//原擴容門檻值
int oldThr = threshold;
//定義新容量與門檻值
int newCap, newThr = ;
//如果原容量>0
if (oldCap > ) {
//如果原容量已經達到最大了1<<30，則不進行擴容，隻調整門檻值為最大，随其碰撞了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果沒達到最大，則變為原來容量的2倍
//其實這句可分解
//newCap = oldCap << 1
//如果擴容後的容量小于最大容量才會将門檻值變為原來的2倍
//else if (newCap < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
// newThr = oldThr << 1; // double threshold
else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << ; // double threshold
}
//如果newCap = 0，oldThr > 0 這是适用于不同的構造函數的
else if (oldThr > ) // initial capacity was placed in threshold
newCap = oldThr;
//預設構造器的處理
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果擴容後的容量大于最大容量了1<<30
if (newThr == ) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//設定為新的值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//完成rehash
if (oldTab != null) {
//對原數組的沒一個位置 這是一個周遊 是以rehash過程的是很耗費時間的
for (int j = ; j < oldCap; ++j) {
Node<K,V> e;
//e = oldTab[j])
if ((e = oldTab[j]) != null) {
//将原位置設為null
oldTab[j] = null;
//如果沒有碰撞，也就是隻有這一個元素，直接定位設定到新數組的位置
if (e.next == null)
newTab[e.hash & (newCap - )] = e;
//如果目前節點是TreeNode類型，說明已經樹化了，紅黑樹的rehash過程
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//表明目前節點沖突是連結清單存儲的，完成rehash
//注意：這是1.8的優化點，這也是容量聲明為2的次幂的另一個應用
else { // preserve order
//rehash後還是原位置
Node<K,V> loHead = null, loTail = null;
//rehash後變為j+oldCap位置
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//如果擴大的那一位hash還是0，則說明它還是在原位置
if ((e.hash & oldCap) == ) {
//如果它是第一個被加入的
if (loTail == null)
loHead = e;
//進行連結
else
loTail.next = e;
loTail = e;
}
//定位到j+oldCap位置
else {
//如果它是第一個被加入的
if (hiTail == null)
hiHead = e;
//進行連結
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//在newTab相應位置設定完成rehash的連結清單
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
從我上邊的代碼注釋中，我相信大家已經很容易了解此過程，但是我們沒有涉及紅黑樹的相應操作，單單看其連結清單的操作，我們就可以看到其代碼寫的确實很好。
與JDK1.7的差別
這是基于jdk1.8的，那它與1.7有什麼差別呢？最大的差別當然是關于紅黑樹的那部分操作，另一部分是hash定位的算法，這在上邊已經分析過了。還有一點注意差別，JDK1.7中rehash的時候，舊連結清單遷移新連結清單的時候，如果在新表的數組索引位置相同，則連結清單元素會倒置，但是從1.8的源碼可以看出，JDK1.8不會倒置。
JDK1.8中當元素定位的哈希桶是一個連結清單時，則采用尾插入法。首先從頭周遊連結清單，根據equals和hashCode來比較key是否相同。是以作為hashMap的key必須同時重載equals方法和hashCode方法。
JDK 1.7的連結清單操作采用了頭插入法，即新的元素插入到連結清單頭部。在JDK1.8中采用了尾插入法。插入以後如果連結清單長度大于8，那麼就會将連結清單轉換為紅黑樹。因為如果連結清單長度過長會導緻元素的增删改查效率低下，呈現線性搜尋時間。JDK1.8采用采用紅黑樹進行優化，進而提高HashMap性能。
如果哈希桶是一個紅黑樹，則直接使用紅黑樹插入方式直接插入到紅黑樹中。
下邊是jdk1.7的rehash過程。因為jdk1.7使用的是頭插法，它依次周遊數組每個bin上的連結清單，完成rehash。
我們從代碼中就不難了解，由于1.7采用的是頭插法，是以JDK1.7中rehash的時候，舊連結清單遷移新連結清單的時候，如果在新表的數組索引位置相同，則連結清單元素會倒置。（後在前，前在後）
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了舊的Entry數組
int newCapacity = newTable.length;
for (int j = ; j < src.length; j++) { //周遊舊的Entry數組
Entry<K,V> e = src[j]; //取得舊Entry數組的每個元素
if (e != null) {
src[j] = null;//釋放舊Entry數組的對象引用（for循環後，舊的Entry數組不再引用任何對象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新計算每個元素在數組中的位置
e.next = newTable[i]; //标記[1]
newTable[i] = e; //将元素放在數組上
e = next; //通路下一個Entry鍊上的元素
} while (e != null);
}
}
}
JDK1.8與JDK1.7對比，當hash沖突較多時，顯然是JDK1.8效率更高。
線程安全性
HashMap線程不安全的展現在哪？主要是resize和疊代器的fail-fast上
在多線程使用場景中，應該盡量避免使用線程不安全的HashMap，而使用線程安全的ConcurrentHashMap。那麼為什麼說HashMap是線程不安全的，下面舉例子說明在并發的多線程使用場景中使用HashMap可能造成死循環。resize死循環（會形成環形連結清單）。
jdk1.7出現的resize死循環比較好了解，可以參看這篇文章：談談HashMap線程不安全的展現 。但因為1.8保持了連結清單原來的順序不變，JDK 1.8 是否會出現類似于 JDK 1.7中那樣的死循環呢??這個有點不了解啊啊，求解答。。。。。。。
HashMap與Hashtable的差別
HashMap和Hashtable都實作了Map接口，但決定用哪一個之前先要弄清楚它們之間的分别。主要的差別有：線程安全性，同步(synchronization)，以及速度。
第一、繼承不同
第一個不同主要是曆史原因。Hashtable是基于陳舊的Dictionary類的，HashMap是Java 1.2引進的Map接口的一個實作。但後來Hashtable也實作了map接口。
第二、線程安全不一樣
Hashtable 中的方法是同步的（利用synchronized關鍵字實作），而HashMap中的方法在預設情況下是非同步的。在多線程并發的環境下，可以直接使用Hashtable，但是要使用HashMap的話就要自己增加同步處理了。
第三、允不允許null值
從上面的put()方法源碼可以看到，Hashtable中，key和value都不允許出現null值，否則會抛出NullPointerException異常。
而在HashMap中，null可以作為鍵，這樣的鍵隻有一個；可以有一個或多個鍵所對應的值為null。當get()方法傳回null值時，即可以表示 HashMap中沒有該鍵，也可以表示該鍵所對應的值為null。是以，在HashMap中不能由get()方法來判斷HashMap中是否存在某個鍵， 而應該用containsKey()方法來判斷。
第四、周遊方式的内部實作上不同
Hashtable、HashMap都使用了 Iterator。而由于曆史原因，Hashtable還使用了Enumeration的方式 。
第五、哈希值的使用不同
HashTable直接使用對象的hashCode。而HashMap重新計算hash值。
//hashtable
int hash = key.hashCode();
int index = (hash & ) % tab.length;
第六、内部實作方式的數組的初始大小和擴容的方式不一樣
HashTable中的hash數組初始大小是11，增加的方式是 old*2+1。HashMap中hash數組的預設大小是16，而且一定是2的指數。
HashMap的周遊方法
HashMap有多種周遊方式，主要是依賴于疊代器（因為for-each也是利用疊代器實作的），這裡就不詳細介紹了，可以參看Java Map周遊方式的選擇 和 HashMap循環周遊方式及其性能對比 。
HashMap内容太多了，但搞懂還是有必要的，另外要想徹底搞定HashMap，ConcurrentHashMap更是并發學習的經典，在後邊并發包的源碼解析中再進行介紹。