如果大家有仔細(xì)閱讀過 HashMap 的源碼就會(huì)發(fā)現(xiàn) HashMap 的哈希表初始化并不是在其構(gòu)造函數(shù)中進(jìn)行的，而是 resize() 方法。

這篇文章不對(duì) HashMap 中的樹進(jìn)行介紹。

一、HashMap 四個(gè)構(gòu)造函數(shù)

這里把 HashMap 的四個(gè)構(gòu)造函數(shù)全貼出來，主要是給大家一個(gè)參照。

PS：并不是所有的構(gòu)造函數(shù)都初始化了 threshold，但是所有的構(gòu)造函數(shù)都初始化了加載因子，另外初始容量大小也都沒有初始化。

// 構(gòu)造函數(shù) 1 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);}// 構(gòu)造函數(shù) 2public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}// 構(gòu)造函數(shù) 3public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; }// 構(gòu)造函數(shù) 4public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}

二、put 方法

我們都知道 HashMap 的底層是一個(gè)基于 Node<K,V>[] table 的數(shù)組，看完了上面的構(gòu)造函數(shù)，我們發(fā)現(xiàn)數(shù)組并不是在構(gòu)造函數(shù)中完成的，那是在哪里初始化的呢？帶著這個(gè)疑問我們來看一下 HashMap 中的 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 為 true 時(shí)不改變已經(jīng)存在的值* @param 為 false 時(shí)表示哈希表正在創(chuàng)建* @return previous value, or null if none*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {/*** tab：哈希表數(shù)組* p：桶位置上的頭節(jié)點(diǎn)* n：哈希表數(shù)組大小* i：下標(biāo)（槽位置）*/Node<K,V>[] tab; Node<K,V> p; int n, i;// 當(dāng)哈希表數(shù)組為 null 或者長度為 0 時(shí)，初始化哈希表數(shù)組if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 頭節(jié)點(diǎn)為空直接插入（無哈希碰撞）if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 哈希碰撞else {Node<K,V> e; K k;// 與頭節(jié)點(diǎn)發(fā)生哈希沖突，進(jìn)行記錄if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 如果是樹節(jié)點(diǎn)，走樹節(jié)點(diǎn)插入流程else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 鏈表處理流程else {for (int binCount = 0; ; ++binCount) {// 在鏈表尾部插入新節(jié)點(diǎn)，注意 jdk1.8 中在鏈表尾部插入新節(jié)點(diǎn)if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 如果當(dāng)前鏈表中的元素大于樹化的閾值，進(jìn)行鏈表轉(zhuǎn)樹的操作if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 如果 key（非頭節(jié)點(diǎn)）已經(jīng)存在，直接結(jié)束循環(huán)if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;// 重置 p 用于遍歷p = e;}}// 如果 key 已經(jīng)存在則更新 value 值if (e != null) { // existing mapping for keyV oldValue = e.value;// 更新當(dāng)前 key 值if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;// 如果鍵值對(duì)個(gè)數(shù)大于閾值時(shí)（capacity * load factor），進(jìn)行擴(kuò)容操作if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

主要流程總結(jié)：

哈希表是否初始化判斷

是否發(fā)生哈希碰撞，（無）頭節(jié)點(diǎn)判斷：如果頭節(jié)點(diǎn)不存在直接插入當(dāng)前鍵值對(duì)

key 是否存在條件判斷：頭節(jié)點(diǎn)沖突進(jìn)行記錄、樹形態(tài)與鏈表形態(tài)分別走對(duì)應(yīng)的流程插入鍵值對(duì)

鏈表處理，如果插入的 key 在鏈表中不存在，則在鏈表尾部插入鍵值對(duì)（后判斷是否需要轉(zhuǎn)樹），如果發(fā)生沖突，則記錄當(dāng)前沖突節(jié)點(diǎn)

key 存在，新的 value 覆蓋舊的 value，并返回舊 value

是否需要擴(kuò)容

三、擴(kuò)容機(jī)制，resize 方法

PS：resize() 方法并不只是用于擴(kuò)容，還用于初始化哈希表。

final Node<K,V>[] resize() {// 用于記錄老的哈希表Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;// 哈希表已存在if (oldCap > 0) {// 如果哈希表容量已達(dá)最大值，不進(jìn)行擴(kuò)容，并把閾值置為 0x7fffffffif (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 新容量為原來數(shù)組大小的兩倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 把新的閾值也擴(kuò)大為兩倍newThr = oldThr << 1; // double threshold}// 初始化哈希表數(shù)組，對(duì)應(yīng)初始化 threshold 的構(gòu)造函數(shù)else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 初始化哈希表數(shù)組，對(duì)應(yīng)沒有初始化 threshold 的構(gòu)造函數(shù)else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 閾值為 0 處理（哈希表還沒有初始化但 threshold 已經(jīng)被初始化）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"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;/*------------- 下面是 rehash 過程 ---------------*/if (oldTab != null) {// 遍歷老哈希表，將當(dāng)前桶位置的鍵值對(duì)移動(dòng)到新的哈希表中for (int j = 0; j < oldCap; ++j) {// 記錄當(dāng)前桶位置的頭節(jié)點(diǎn)Node<K,V> e;// 頭節(jié)點(diǎn)判是否為 nullif ((e = oldTab[j]) != null) {// 置 null（鏈表或樹），讓 GC 回收oldTab[j] = null;// 如果當(dāng)前桶位置上只有一個(gè)元素，直接 rehash 到新的哈希表中if (e.next == null)newTab[e.hash & (newCap - 1)] = e;// 處理樹節(jié)點(diǎn)else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 處理鏈表節(jié)點(diǎn)，下面這個(gè)過程的實(shí)現(xiàn)很巧妙，我把它單獨(dú)拿出來分析else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

鏈表 rehash 過程：

{else { // preserve order/*** rehash 時(shí)分高低位處理*/Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;// 遍歷鏈表do {next = e.next;/*** 判斷舊哈希表桶位置上的所有元素位于低位還是高位* e.hash & oldCap 計(jì)算的不是桶位置* e.hash & (oldCap -1) 計(jì)算的才是桶位置** 關(guān)于高低位我們舉個(gè)來幫助例子：* 條件：原哈希表大小為 16，擴(kuò)容后的哈希表大小為 32* * 1.假設(shè) key1.hashCode = 15，位于舊的哈希表 15 桶位置上* key1.hash & oldCap = 15 & 16 * 0000 1111 & 0001 0000 = 0000 0000 第 5 位為 0* key1 在新的哈希表中的位置也是 15 桶位置上** 2.假設(shè) key2.hashCode = 17，位于舊的哈希表 1 桶位置上* key2.hash & oldCap = 17 & 16 * 0001 0001 & 0001 0000 = 0001 0000 第 5 位 為 1** 為什么要以第 5 位為標(biāo)準(zhǔn)呢？* 因?yàn)槔系萌萘繛?6，在計(jì)算哈希值時(shí)，高于第四位的就沒有計(jì)算的必要了*/if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 上面舉的例子看懂了，這里就很好理解了，低位（0）位置保持不變直接 rehashif (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 高位（1）位置需要加上老哈希表的容量if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;} }

主要流程總結(jié)：

判斷哈希表是否初始化（已經(jīng)初始化、threshold 已經(jīng)初始化、threshold 沒有初始化）

當(dāng) threshold 沒有初始化時(shí)初始化 threshold

遍歷舊的哈希表，進(jìn)行 rehash，如果桶位置上沒有鍵值對(duì)則直接略過，如果只有一個(gè)節(jié)點(diǎn)，直接 rehash 到新的哈希表中

樹與鏈表形態(tài)判斷，分別走對(duì)應(yīng)的 rehash 流程

鏈表通過高低位方式 rehash

四、并發(fā)安全

jdk1.7 中的 HashMap 在擴(kuò)容時(shí)新哈希表數(shù)組和舊哈希表數(shù)組之間存在相互引用關(guān)系（我并沒有仔細(xì)看過，有興趣的可以閱讀一下），因此在并發(fā)情況下會(huì)出現(xiàn)死循環(huán)的問題。在 jdk1.8 中是否還存在同樣的問題？下面我們通過一個(gè)例子進(jìn)行驗(yàn)證一下。

public class HashMapConcurrentTest {/*** NUMBER = 50，表示 50 個(gè)線程分別執(zhí)行 put 方法 50 次* 線程安全的情況下因該 map size 應(yīng)該為 2500*/public static final int NUMBER = 50;public static void main(String[] args) {Map<String, String> map = new HashMap<>();for (int i = 0; i < NUMBER; i++) {new Thread(new HashMapTask(map)).start();}System.out.println("map size = " + map.size());} }class HashMapTask implements Runnable {Map<String, String> map;public HashMapTask(Map<String, String> map) {this.map = map;}@Overridepublic void run() {for (int i = 0; i < HashMapConcurrentTest.NUMBER; i++) {map.put(i + "-" + Thread.currentThread().getName(), "test");}} }

其中一個(gè)執(zhí)行結(jié)果截圖：

上面開了 50 個(gè)線程往 HashMap 中添加元素，每個(gè)線程執(zhí)行 50 次 put 方法，在線程安全的情況下，map 中應(yīng)該有 2500 個(gè)鍵值對(duì)，但是執(zhí)行的結(jié)果大都是小與 2500 的（并不會(huì)產(chǎn)生死循環(huán)）。

jdk1.8 中的 HashMap 新老數(shù)組之間不存在了引用關(guān)系，因此不會(huì)出現(xiàn)死循環(huán)的情況，但是卻會(huì)存在鍵值對(duì)丟失的現(xiàn)象。為什么會(huì)出現(xiàn)鍵值對(duì)丟失的現(xiàn)象呢？下面以鏈表為例來簡單分析一下（個(gè)人理解，不正確的話還請(qǐng)大家指正）。

多線程情況下，可能會(huì)有多個(gè)線程進(jìn)入 resize 方法，假設(shè)第一個(gè)線程進(jìn)入了 resize 方法，在處理鏈表時(shí)會(huì)先記錄一下，然后直接將對(duì)應(yīng)的舊哈希表數(shù)組中的鏈表置 null，此時(shí)第二個(gè)線程進(jìn)來了，因?yàn)樯弦粋€(gè)線程已經(jīng)把鏈表置 null 了，線程 2 判定當(dāng)前桶位置上沒有鍵值對(duì)，如果線程 2 返回的哈希表數(shù)組覆蓋了線程 1 的哈希表數(shù)組，就會(huì)丟失一部分因線程 1 置 null 的鍵值對(duì)。

...if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;...}

jdk1.8 源碼閱讀：https://github.com/zchen96/jdk1.8-source-code-read

參考文章

HashMap在JDK1.8中并發(fā)操作，代碼測(cè)試以及源碼分析

總結(jié)

以上是生活随笔為你收集整理的Java8 HashMap 扩容机制与线程安全分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。