簡介：
HashMap是我們在Java中用來保存key-value值使用頻率較高的一個工具，其本身是對數據結構哈希表的一個具體實現，本文主要是以源碼為主來解決我們下面提出的問題
1、HashMap是如何將一個對象的hashCode轉換為數組中的索引？
2、當發生衝突時，HashMap是如何解決衝突的？
3、HashMap在什麼情況下會擴容？怎麼擴容？
4、HashMap的線程安全問題
一、HashMap是如何將一個對象的hashCode轉換為數組中的索引？
首先我們看一下是如何獲取hashcode的
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }這段代碼主要做了如下幾下事情：
1、如果key值為null則將key值設置為0
2、根據object中的native方法獲取到一個int型的hashcode
3、hashcode的二進制位移動16位
4、將本身的hashcode與位移後的hashcode進行了一個^運算，得出結果
步驟3和步驟四是將已經獲取到的hashcode進行了一個高低位的干擾運算。
我們知道int類型是取值範圍是-2147483648到2147483648，加起來大概40億的映射空間。
直接用來當作索引的話hashmap的默認容量就需要40Y個了，但是我們知道hashmap的初始空間為16。
所以需要將得到的hashcode映射為數組中的索引，我們看下面代碼：
tab[i = (n - 1) & hash]
這個就是將hashcode轉化為索引的方法，n為數組的長度。
& 運算後就是高位值全部歸零，只使用低位值來保證得到的索引是不超過當前數組的長度的。
（這裡也就說明了為什麼擴容是擴2次冪，因為這樣數組的長度減1之後得到的二進制位尾數都是1）
但是這樣問題就來了，兩個完全不一樣的hashcode，但是低位相同就會發生衝突，所以就有了步驟三和步驟四。
我們看一下下面的計算過程：
h: 1111 1111 1111 1111 1111 0000 1110 1010h >>> 16: 0000 0000 0000 0000 1111 1111 1111 1111h ^ (h >>> 16): 1111 1111 1111 1111 0000 1111 0001 0101
這樣將高低位都參與到運算中就避免了低位相同導致出現衝突的情況。
二、當發生衝突時，HashMap是如何解決衝突的？
首先我們看一下添加元素進哈希表的putVal方法一個流程圖
然後我們分析一下源碼:
1、判斷當前hash表的容量是否為空，為空則進行擴容
if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
2、根據得到的索引判斷該位置是否有元素，沒有則保存
if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
3、判斷當前的key值和發生衝突位置的key值是否相等，相等稍後直接覆蓋
if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }4、判斷當前的元素是否為紅黑樹中的一個節點，是在添加到樹中
else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
5、遍歷該鏈表上的元素，將當前元素保存到最後一位
else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null);6、當鏈表的長度超過8時，將鏈表轉為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash);
上面步驟就是將元素添加到哈希表中的過程，其中3-4-5-6是就是解決衝突的方法。
紅黑樹是在JDK1.8引入進來了，為了解決鏈表過長導致的效率慢的問題
三、HashMap在什麼情況下會擴容？怎麼擴容？
首先是在put方法剛開始時，哈希表未初始化時則進行擴容，其次就是在添加完成後
if (++size > threshold) resize();
當前的數組長度已經大於threshold（數組長度*0.75）則進行擴容。
為什麼不是當長度超過數組長度進行擴容呢？
我們知道，當數組所剩餘的長度比我們的元素數量少很多時，
就會發生大量的元素衝突（也未必能填滿數組），導致哈希表的效率變慢，
所以我們需要提前對數組進行擴容。默認的0.75的在效率和內存空間上的一個平衡點。
接下來我們看一下擴容裡面的一段代碼：
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold
新數組的長度其實就是舊數組的長度*2,上面也解釋了為什麼是2。
四、HashMap的線程安全問題
HashMap本身是線程不安全的，在多線程環境下會導致丟失數據，在JDK1.8之前擴容操作還會死循環，CPU飆升100%。
JDK1.7中出現死循環的原因主要是鏈表在轉移數據的過程中，多線程環境下出現環形鏈表導致的，在JDK1.8中已經使用雙鏈表解決了。
但是在多線程環境下還是不要使用，也不用加同步（鎖全部對象導致效率差），直接使用ConcurrentHashMap來解決
閱讀更多 3T教育編程猿 的文章
