一、結構
如圖所示，HashMap 底層是基于數組和連結清單實作的。其中有兩個重要的參數：
- 容量
- 負載因子
容量的預設大小是 16，負載因子是 0.75，當 HashMap 的 size > 16*0.75 時就會發生擴容(容量和負載因子都可以自由調整，無論是自動擴充還是手動初始化時，必須是2的幂)。
二、方法
2.1、put 方法
首先會将傳入的 Key 做 hash 運算計算出 hashcode,然後根據數組長度取模計算出在數組中的 index 下标。
由于在計算中位運算比取模運算效率高的多且Hash算法均勻分布原則，是以 HashMap 規定數組的長度為 2^n 。這樣用 2^n - 1 做位運算與取模效果一緻，并且效率還要高出許多index = HashCode(Key) & (Length - 1)。
下面我們以值為“book”的Key來示範整個過程：
1.計算book的hashcode，結果為十進制的3029737，二進制的101110001110101110 1001。
2.假定HashMap長度是預設的16，計算Length-1的結果為十進制的15，二進制的1111。
3.把以上兩個結果做與運算，101110001110101110 1001 & 1111 = 1001，十進制是9，是以 index=9。
可以說，Hash算法最終得到的index結果，完全取決于Key的Hashcode值的最後幾位。
由于數組的長度有限，是以難免會出現不同的 Key 通過運算得到的 index 相同，這種情況可以利用連結清單來解決，HashMap 會在 table[index]處形成環形連結清單，采用頭插法(不是插傳入連結表的尾部，而是頭部，因為：後插入的Entry被查找的可能性更大)将資料插入到連結清單中。
2.2、get 方法
get 和 put 類似，也是将傳入的 Key 計算出 index ，如果該位置上是一個連結清單就需要周遊整個連結清單，通過 key.equals(k) 來找到對應的元素。
周遊方式
Iterator> entryIterator = map.entrySet().iterator(); while (entryIterator.hasNext()) { Map.Entry next = entryIterator.next(); System.out.println("key=" + next.getKey() + " value=" + next.getValue());}
Iterator iterator = map.keySet().iterator(); while (iterator.hasNext()){ String key = iterator.next(); System.out.println("key=" + key + " value=" + map.get(key)); }
強烈建議使用第一種 EntrySet 進行周遊。
第一種可以把 key value 同時取出，第二種還得需要通過 key 取一次 value，效率較低。
三、高并發下的HashMap
在并發環境下使用 HashMap 容易出現死循環。
HashMap的容量是有限的。當經過多次元素插入，使得HashMap達到一定飽和度時，Key映射位置發生沖突的幾率會逐漸提高。這時候，HashMap需要擴充它的長度，也就是進行Resize。擴容的影響因子就是Capacity(容量)、LoadFactor(加載因子)，當 HashMap 的 size > 16*0.75 時就會發生擴容。
3.1、擴容
3.1.1、建立一個新的Entry數組
長度時原來的兩倍。
3.1.2、ReHash方法
/** * Transfers all entries from current table to newTable. */void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry e : table) { while(null != e) { Entry 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; } }}
并發場景發生擴容，調用 Resize() 方法裡的 Rehash() 時，容易出現環形連結清單。這樣當擷取一個不存在的 key 時，計算出的 index 正好是環形連結清單的下标時就會出現死循環，避免這種情況，通常采用ConcurrentHashMap。
是以 HashMap 隻能在單線程中使用，并且盡量的預設容量，盡可能的減少擴容。
四、優化
在 JDK1.8 中對 HashMap 進行了優化：
當 hash 碰撞之後寫傳入連結表的長度超過了門檻值(預設為8)，連結清單将會轉換為紅黑樹。
假設 hash 沖突非常嚴重，一個數組後面接了很長的連結清單，此時時間複雜度就是 O(n) 。如果是紅黑樹，時間複雜度就是 O(logn) ，大大提高了查詢效率。