來源：www.jianshu.com/p/ee0de4c99f87

HashMap源碼分析

構造函數

讓我們先從構造函數說起，HashMap有四個構造方法，別慌

1.1 HashMap()

// 1.無參構造方法、
// 構造一個空的HashMap，初始容量爲16，負載因子爲0.75
public HashMap() {
 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

無參構造方法就沒什麼好說的了。

1.2 HashMap(int initialCapacity)

// 2.構造一個初始容量爲initialCapacity，負載因子爲0.75的空的HashMap，
public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

HashMap(int initialCapacity) 這個構造方法調用了1.3中的構造方法。

1.3 HashMap(int initialCapacity, float loadFactor)

// 3.構造一個空的初始容量爲initialCapacity，負載因子爲loadFactor的HashMap
 public HashMap(int initialCapacity, float loadFactor) {
 if (initialCapacity < 0)
 throw new IllegalArgumentException("Illegal initial capacity: " +
 initialCapacity);
 if (initialCapacity > MAXIMUM_CAPACITY)
 initialCapacity = MAXIMUM_CAPACITY;
 if (loadFactor <= 0 || Float.isNaN(loadFactor))
 throw new IllegalArgumentException("Illegal load factor: " +
 loadFactor);
 this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);
 }
 //最大容量
 //static final int MAXIMUM_CAPACITY = 1 << 30;

當指定的初始容量< 0時拋出IllegalArgumentException異常，當指定的初始容量> MAXIMUM_CAPACITY時，就讓初始容量 = MAXIMUM_CAPACITY。

當負載因子小於0或者不是數字時，拋出IllegalArgumentException異常。

設定threshold。 這個threshold = capacity * load factor 。當HashMap的size到了threshold時，就要進行resize，也就是擴容。

tableSizeFor()的主要功能是返回一個比給定整數大且最接近的2的冪次方整數，如給定10，返回2的4次方16.

我們進入tableSizeFor(int cap)的源碼中看看：

// Returns a power of two size for the given target capacity.
 static final int tableSizeFor(int cap) {
 int n = cap - 1;
 n |= n >>> 1;
 n |= n >>> 2;
 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;
 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
 }

note： HashMap要求容量必須是2的冪。

首先，int n = cap -1是爲了防止cap已經是2的冪時，執行完後面的幾條無符號右移操作之後，返回的capacity是這個cap的2倍，因爲cap已經是2的冪了，就已經滿足條件了。 如果不懂可以往下看完幾個無符號移位後再回來看。（建議自己在紙上畫一下）

如果n這時爲0了（經過了cap-1之後），則經過後面的幾次無符號右移依然是0，最後返回的capacity是1（最後有個n+1的操作）。這裏只討論n不等於0的情況

以16位爲例，假設開始時 n 爲 0000 1xxx xxxx xxxx （x代表不關心0還是1）

第一次右移 n |= n >>> 1

由於n不等於0，則n的二進制表示中總會有一bit爲1，這時考慮最高位的1。通過無符號右移1位，則將最高位的1右移了1位，再做或操作，使得n的二進制表示中與最高位的1緊鄰的右邊一位也爲1，如0000 11xx xxxx xxxx 。

第二次右移 n |= n >>> 2

注意，這個n已經經過了n |= n >>> 1; 操作。此時n爲0000 11xx xxxx xxxx ，則n無符號右移兩位，會將最高位兩個連續的1右移兩位，然後再與原來的n做或操作，這樣n的二進制表示的高位中會有4個連續的1。如0000 1111 xxxx xxxx 。

第三次右移 n |= n >>> 4

這次把已經有的高位中的連續的4個1，右移4位，再做或操作，這樣n的二進制表示的高位中會有8個連續的1。如0000 1111 1111 xxxx 。

第。。。，你還忍心讓我繼續推麼？相信聰明的你已經想出來了，容量最大也就是32位的正數，所以最後一次 n |= n >>> 16; 可以保證最高位後面的全部置爲1。當然如果是32個1的話，此時超出了MAXIMUM_CAPACITY ，所以取值到 MAXIMUM_CAPACITY 。

tableSizeFor示例圖

注意，得到的這個capacity卻被賦值給了threshold。 這裏我和這篇博客的博主開始的想法一樣，認爲應該這麼寫：

this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;

因爲這樣子才符合threshold的定義：

threshold = capacity * load factor;

但是，請注意，在構造方法中，並沒有對table這個成員變量進行初始化，table的初始化被推遲到了put方法中，在put方法中會對threshold重新計算 。

我說一下我在理解這個tableSizeFor函數中間遇到的坑吧，我在想如果n=-1時的情況，因爲初始容量可以傳進來0。我將n= -1 和下面幾條運算一起新寫了個測試程序，發現輸出都是 -1。

這是因爲計算機中數字是由補碼存儲的，-1的補碼是 0xffffffff。所以無符號右移之後再進行或運算之後還是 -1。

那我想如果就無符號右移呢？ 比如-1>>>10。聽我娓娓道來，32個1無符號右移10位後，高10位爲0，低22位爲1，此時這個數變成了正數，由於正數的補碼和原碼相同，所以就變成了0x3FFFFF即10進制的4194303。真刺激。

好開森，這個構造方法我們算是拿下了。怎麼樣，我猜你現在一定很激動，Hey，old Fe，這纔剛開始。接下來看最後一個構造方法。

1.4 HashMap(Map extends K, ? extends V> m)

// 4. 構造一個和指定Map有相同mappings的HashMap，初始容量能充足的容下指定的Map,負載因子爲0.75
 public HashMap(Map extends K, ? extends V> m) {
 this.loadFactor = DEFAULT_LOAD_FACTOR;
 putMapEntries(m, false);
 }

套路，直接看 putMapEntries(m,false) 。源碼如下：

/**
 * 將m的所有元素存入本HashMap實例中
 */
 final void putMapEntries(Map extends K, ? extends V> m, boolean evict) {
 // 得到 m 中元素的個數
 int s = m.size();
 // 當 m 中有元素時，則需將map中元素放入本HashMap實例。
 if (s > 0) {
 // 判斷table是否已經初始化，如果未初始化，則先初始化一些變量。（table初始化是在put時）
 if (table == null) { // pre-size
 // 根據待插入的map 的 size 計算要創建的 HashMap 的容量。
 float ft = ((float) s / loadFactor) + 1.0F;
 int t = ((ft < (float) MAXIMUM_CAPACITY) ? (int) ft : MAXIMUM_CAPACITY);
 // 把要創建的 HashMap 的容量存在 threshold 中
 if (t > threshold)
 threshold = tableSizeFor(t);
 }
 // 如果table初始化過，因爲別的函數也會調用它，所以有可能HashMap已經被初始化過了。
 // 判斷待插入的 map 的 size,若 size 大於 threshold，則先進行 resize()，進行擴容
 else if (s > threshold)
 resize();
 // 然後就開始遍歷 帶插入的 map ，將每一個  插入到本HashMap實例。
 for (Map.Entry extends K, ? extends V> e : m.entrySet()) {
 K key = e.getKey();
 V value = e.getValue();
 // put(K,V)也是調用 putVal 函數進行元素的插入
 putVal(hash(key), key, value, false, evict);
 }
 }
 }

介紹putVal方法前，說一下HashMap的幾個重要的成員變量：

/**
 * The table, initialized on first use, and resized as necessary. When
 * allocated, length is always a power of two. (We also tolerate length zero in
 * some operations to allow bootstrapping mechanics that are currently not
 * needed.)
 */
 // 實際存儲key，value的數組，只不過key，value被封裝成Node了
 transient Node[] table;
 /**
 * The number of key-value mappings contained in this map.
 */
 transient int size;
 /**
 * The number of times this HashMap has been structurally modified Structural
 * modifications are those that change the number of mappings in the HashMap or
 * otherwise modify its internal structure (e.g., rehash). This field is used to
 * make iterators on Collection-views of the HashMap fail-fast. (See
 * ConcurrentModificationException).
 */
 transient int modCount;
 /**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
 // (The javadoc description is true upon serialization.
 // Additionally, if the table array has not been allocated, this
 // field holds the initial array capacity, or zero signifying
 // DEFAULT_INITIAL_CAPACITY.)
 // 因爲 tableSizeFor(int) 返回值給了threshold
 int threshold;
 /**
 * The load factor for the hash table.
 *
 * @serial
 */
 final float loadFactor;

其實就是哈希表。HashMap使用鏈表法避免哈希衝突（相同hash值），當鏈表長度大於TREEIFY_THRESHOLD（默認爲8）時，將鏈表轉換爲紅黑樹，當然小於UNTREEIFY_THRESHOLD（默認爲6）時，又會轉回鏈表以達到性能均衡。 我們看一張HashMap的數據結構（數組+鏈表+紅黑樹 ）就更能理解table了：

HashMap的數據結構

回到putMapEntries函數中，如果table爲null，那麼這時就設置合適的threshold，如果不爲空並且指定的map的size>threshold，那麼就resize()。然後把指定的map的所有Key，Value，通過putVal添加到我們創建的新的map中。

putVal中傳入了個hash(key)，那我們就先來看看hash(key):

/**
 * key 的 hash值的計算是通過hashCode()的高16位異或低16位實現的：(h = k.hashCode()) ^ (h >>> 16)
 * 主要是從速度、功效、質量來考慮的，這麼做可以在數組table的length比較小的時候
 * 也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷
 */
 static final int hash(Object key) {
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

異或運算：

(h = key.hashCode()) ^ (h >>> 16)

原 來 的 hashCode :

1111 1111 1111 1111 0100 1100 0000 1010

移位後的hashCode:

0000 0000 0000 0000 1111 1111 1111 1111

進行異或運算 結果：

1111 1111 1111 1111 1011 0011 1111 0101

這樣做的好處是，可以將hashcode高位和低位的值進行混合做異或運算，而且混合後，低位的信息中加入了高位的信息，這樣高位的信息被變相的保留了下來。摻雜的元素多了，那麼生成的hash值的隨機性會增大。

剛纔我們漏掉了resize()和putVal() 兩個函數，現在我們按順序分析一波：

首先resize() ,先看一下哪些函數調用了resize()，從而在整體上有個概念：

調用了resize的函數.png

接下來上源碼：

final Node[] resize() {
 // 保存當前table
 Node[] oldTab = table;
 // 保存當前table的容量
 int oldCap = (oldTab == null) ? 0 : oldTab.length;
 // 保存當前閾值
 int oldThr = threshold;
 // 初始化新的table容量和閾值 
 int newCap, newThr = 0;
 /*
 1. resize（）函數在size　> threshold時被調用。oldCap大於 0 代表原來的 table 表非空，
 oldCap 爲原表的大小，oldThr（threshold） 爲 oldCap × load_factor
 */
 if (oldCap > 0) {
 // 若舊table容量已超過最大容量，更新閾值爲Integer.MAX_VALUE（最大整形值），這樣以後就不會自動擴容了。
 if (oldCap >= MAXIMUM_CAPACITY) {
 threshold = Integer.MAX_VALUE;
 return oldTab;
 }
 // 容量翻倍，使用左移，效率更高
 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
 oldCap >= DEFAULT_INITIAL_CAPACITY)
 // 閾值翻倍
 newThr = oldThr << 1; // double threshold
 }
 /*
 2. resize（）函數在table爲空被調用。oldCap 小於等於 0 且 oldThr 大於0，代表用戶創建了一個 HashMap，但是使用的構造函數爲 
 HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
 或 HashMap(Map extends K, ? extends V> m)，導致 oldTab 爲 null，oldCap 爲0， oldThr 爲用戶指定的 HashMap的初始容量。
 */
 else if (oldThr > 0) // initial capacity was placed in threshold
 //當table沒初始化時，threshold持有初始容量。還記得threshold = tableSizeFor(t)麼;
 newCap = oldThr;
 /*
 3. resize（）函數在table爲空被調用。oldCap 小於等於 0 且 oldThr 等於0，用戶調用 HashMap()構造函數創建的　HashMap，所有值均採用默認值，oldTab（Table）表爲空，oldCap爲0，oldThr等於0，
 */
 else { // zero initial threshold signifies using defaults
 newCap = DEFAULT_INITIAL_CAPACITY;
 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 }
 // 新閾值爲0
 if (newThr == 0) {
 float ft = (float)newCap * loadFactor;
 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
 (int)ft : Integer.MAX_VALUE);
 }
 threshold = newThr;
 @SuppressWarnings({"rawtypes","unchecked"})
 // 初始化table
 Node[] newTab = (Node[])new Node[newCap];
 table = newTab;
 if (oldTab != null) {
 // 把 oldTab 中的節點　reHash 到　newTab 中去
 for (int j = 0; j < oldCap; ++j) {
 Node e;
 if ((e = oldTab[j]) != null) {
 oldTab[j] = null;
 // 若節點是單個節點，直接在 newTab　中進行重定位
 if (e.next == null)
 newTab[e.hash & (newCap - 1)] = e;
 // 若節點是　TreeNode 節點，要進行 紅黑樹的 rehash　操作
 else if (e instanceof TreeNode)
 ((TreeNode)e).split(this, newTab, j, oldCap);
 // 若是鏈表，進行鏈表的 rehash　操作
 else { // preserve order
 Node loHead = null, loTail = null;
 Node hiHead = null, hiTail = null;
 Node next;
 // 將同一桶中的元素根據(e.hash & oldCap)是否爲0進行分割（代碼後有圖解，可以回過頭再來看），分成兩個不同的鏈表，完成rehash
 do {
 next = e.next;
 // 根據算法　e.hash & oldCap 判斷節點位置rehash　後是否發生改變
 //最高位==0，這是索引不變的鏈表。
 if ((e.hash & oldCap) == 0) { 
 if (loTail == null)
 loHead = e;
 else
 loTail.next = e;
 loTail = e;
 }
 //最高位==1 （這是索引發生改變的鏈表）
 else { 
 if (hiTail == null)
 hiHead = e;
 else
 hiTail.next = e;
 hiTail = e;
 }
 } while ((e = next) != null);
 if (loTail != null) { // 原bucket位置的尾指針不爲空(即還有node) 
 loTail.next = null; // 鏈表最後得有個null
 newTab[j] = loHead; // 鏈表頭指針放在新桶的相同下標(j)處
 }
 if (hiTail != null) {
 hiTail.next = null;
 // rehash　後節點新的位置一定爲原來基礎上加上　oldCap，具體解釋看下圖
 newTab[j + oldCap] = hiHead;
 }
 }
 }
 }
 }
 return newTab;
 }
}

引自美團點評技術博客。我們使用的是2次冪的擴展(指長度擴爲原來2倍)，所以，元素的位置要麼是在原位置，要麼是在原位置再移動2次冪的位置。看下圖可以明白這句話的意思，n爲table的長度，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴容後key1和key2兩種key確定索引位置的示例，其中hash1是key1對應的哈希與高位運算結果。

hashMap 1.8 哈希算法例圖1.png

元素在重新計算hash之後，因爲n變爲2倍，那麼n-1的mask範圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：

hashMap 1.8 哈希算法例圖2.png

因此，我們在擴充HashMap的時候，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，可以看看下圖爲16擴充爲32的resize示意圖 ：

jdk1.8 hashMap擴容例圖.png

什麼時候擴容：通過HashMap源碼可以看到是在put操作時，即向容器中添加元素時，判斷當前容器中元素的個數是否達到閾值（當前數組長度乘以加載因子的值）的時候，就要自動擴容了。

擴容(resize)：其實就是重新計算容量；而這個擴容是計算出所需容器的大小之後重新定義一個新的容器，將原來容器中的元素放入其中。

resize()告一段落，接下來看 putVal() 。

上源碼：

//實現put和相關方法。
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 boolean evict) {
 Node[] tab; Node p; int n, i;
 //如果table爲空或者長度爲0，則resize()
 if ((tab = table) == null || (n = tab.length) == 0)
 n = (tab = resize()).length;
 //確定插入table的位置，算法是(n - 1) & hash，在n爲2的冪時，相當於取摸操作。
 ////找到key值對應的槽並且是第一個，直接加入
 if ((p = tab[i = (n - 1) & hash]) == null)
 tab[i] = newNode(hash, key, value, null);
 //在table的i位置發生碰撞，有兩種情況，1、key值是一樣的，替換value值，
 //2、key值不一樣的有兩種處理方式：2.1、存儲在i位置的鏈表；2.2、存儲在紅黑樹中
 else {
 Node e; K k;
 //第一個node的hash值即爲要加入元素的hash
 if (p.hash == hash &&
 ((k = p.key) == key || (key != null && key.equals(k))))
 e = p;
 //2.2
 else if (p instanceof TreeNode)
 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
 //2.1
 else {
 //不是TreeNode,即爲鏈表,遍歷鏈表
 for (int binCount = 0; ; ++binCount) {
 ///鏈表的尾端也沒有找到key值相同的節點，則生成一個新的Node,
 //並且判斷鏈表的節點個數是不是到達轉換成紅黑樹的上界達到，則轉換成紅黑樹。
 if ((e = p.next) == null) {
 // 創建鏈表節點並插入尾部
 p.next = newNode(hash, key, value, null);
 ////超過了鏈表的設置長度8就轉換成紅黑樹
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
 break;
 }
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 break;
 p = e;
 }
 }
 //如果e不爲空就替換舊的oldValue值
 if (e != null) { // existing mapping for key
 V oldValue = e.value;
 if (!onlyIfAbsent || oldValue == null)
 e.value = value;
 afterNodeAccess(e);
 return oldValue;
 }
 }
 ++modCount;
 if (++size > threshold)
 resize();
 afterNodeInsertion(evict);
 return null;
 }

注：hash 衝突發生的幾種情況：1.兩節點key 值相同（hash值一定相同），導致衝突；2.兩節點key 值不同，由於 hash 函數的侷限性導致hash 值相同，衝突；3.兩節點key 值不同，hash 值不同，但 hash 值對數組長度取模後相同，衝突；

相比put方法，get方法就比較簡單，這裏就不說了。

1.7和1.8的HashMap的不同點

1、JDK1.7用的是頭插法，而JDK1.8及之後使用的都是尾插法，那麼爲什麼要這樣做呢？因爲JDK1.7是用單鏈表進行的縱向延伸，當採用頭插法就是能夠提高插入的效率，但是也會容易出現逆序且環形鏈表死循環問題。但是在JDK1.8之後是因爲加入了紅黑樹使用尾插法，能夠避免出現逆序且鏈表死循環的問題。

2、擴容後數據存儲位置的計算方式也不一樣：

• 在JDK1.7的時候是直接用hash值和需要擴容的二進制數進行&（這裏就是爲什麼擴容的時候爲啥一定必須是2的多少次冪的原因所在，因爲如果只有2的n次冪的情況時最後一位二進制數才一定是1，這樣能最大程度減少hash碰撞）（hash值 & length-1） 。
• 而在JDK1.8的時候直接用了JDK1.7的時候計算的規律，也就是擴容前的原始位置+擴容的大小值=JDK1.8的計算方式，而不再是JDK1.7的那種異或的方法。但是這種方式就相當於只需要判斷Hash值的新增參與運算的位是0還是1就直接迅速計算出了擴容後的儲存方式。

3、JDK1.7的時候使用的是數組+ 單鏈表的數據結構。但是在JDK1.8及之後時，使用的是數組+鏈表+紅黑樹的數據結構（當鏈表的深度達到8的時候，也就是默認閾值，就會自動擴容把鏈表轉成紅黑樹的數據結構來把時間複雜度從O（N）變成O（logN）提高了效率）。

HashMap爲什麼是線程不安全的？

HashMap 在併發時可能出現的問題主要是兩方面：

put的時候導致的多線程數據不一致

比如有兩個線程A和B，首先A希望插入一個key-value對到HashMap中，首先計算記錄所要落到的 hash桶的索引座標，然後獲取到該桶裏面的鏈表頭結點，此時線程A的時間片用完了，而此時線程B被調度得以執行，和線程A一樣執行，只不過線程B成功將記錄插到了桶裏面，假設線程A插入的記錄計算出來的 hash桶索引和線程B要插入的記錄計算出來的 hash桶索引是一樣的，

那麼當線程B成功插入之後，線程A再次被調度運行時，它依然持有過期的鏈表頭但是它對此一無所知，以至於它認爲它應該這樣做，如此一來就覆蓋了線程B插入的記錄，這樣線程B插入的記錄就憑空消失了，造成了數據不一致的行爲。

resize而引起死循環

這種情況發生在HashMap自動擴容時，當2個線程同時檢測到元素個數超過 數組大小 × 負載因子。

此時2個線程會在put()方法中調用了resize()，兩個線程同時修改一個鏈表結構會產生一個循環鏈表（JDK1.7中，會出現resize前後元素順序倒置的情況）。接下來再想通過get()獲取某一個元素，就會出現死循環。

HashMap和HashTable的區別

HashMap和Hashtable都實現了Map接口，但決定用哪一個之前先要弄清楚它們之間的分別。主要的區別有：線程安全性，同步(synchronization)，以及速度。

• HashMap幾乎可以等價於Hashtable，除了HashMap是非synchronized的，並可以接受null(HashMap可以接受爲null的鍵值(key)和值(value)，而Hashtable則不行)。
• HashMap是非synchronized，而Hashtable是synchronized，這意味着Hashtable是線程安全的，多個線程可以共享一個Hashtable；而如果沒有正確的同步的話，多個線程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴展性更好。
• 另一個區別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當有其它線程改變了HashMap的結構（增加或者移除元素），將會拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常。但這並不是一個一定發生的行爲，要看JVM。這條同樣也是Enumeration和Iterator的區別。
• 由於Hashtable是線程安全的也是synchronized，所以在單線程環境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那麼使用HashMap性能要好過Hashtable。
• HashMap不能保證隨着時間的推移Map中的元素次序是不變的。

需要注意的重要術語：

• sychronized意味着在一次僅有一個線程能夠更改Hashtable。就是說任何線程要更新Hashtable時要首先獲得同步鎖，其它線程要等到同步鎖被釋放之後才能再次獲得同步鎖更新Hashtable。
• Fail-safe和iterator迭代器相關。如果某個集合對象創建了Iterator或者ListIterator，然後其它的線程試圖“結構上”更改集合對象，將會拋出ConcurrentModificationException異常。但其它線程可以通過set()方法更改集合對象是允許的，因爲這並沒有從“結構上”更改集合。但是假如已經從結構上進行了更改，再調用set()方法，將會拋出IllegalArgumentException異常。
• 結構上的更改指的是刪除或者插入一個元素，這樣會影響到map的結構。

HashMap可以通過下面的語句進行同步：

Map m = Collections.synchronizeMap(hashMap);