HashMap 是一種散列表，它存儲的內容是鍵值對(key-value)映射。在 HashMap 中，每個鍵(key)映射到一個值(value)。散列表的工作原理是：當通過 put() 方法將鍵值對存儲在 HashMap 中時，HashMap 首先會根據鍵的 hashCode 值來計算出存儲位置，然后將鍵值對存儲在該位置上。當通過 get() 方法獲取鍵值對時，HashMap 再根據鍵的 hashCode 值來獲取存儲位置，然后返回該位置上的值。

hash算法的優化：對每個hash值，在它的低16位中，讓高低16位進行異或，讓它的低16位同時保持了高低16位的特征，盡量避免一些hash值后續出現沖突，大家可能會進入數組的同一位置。

對尋址算法的優化

(p = tab[i = (n - 1) & hash] 
 
 // (n-1) & hash ==> 數組里的一個位置

hash & (n-1) 效果是跟hash對n取模是一樣的，但是與運算的性能要比hash對n取模要高很多。數組的長度會一直是2的n次方，只要他保持數組長度是2的n次方。

• 尋址為什么不用取模？

對于上面尋址算法，由于計算機對比取模，與運算會更快。所以為了效率，HashMap 中規定了哈希表長度為 2 的 k 次方，而 2^k-1 轉為二進制就是 k 個連續的 1，那么 hash & (k 個連續的 1) 返回的就是 hash 的低 k 個位，該計算結果范圍剛好就是 0 到 2^k-1，即 0 到 length - 1，跟取模結果一樣。

也就是說，哈希表長度 length 為 2 的整次冪時， hash & (length - 1) 的計算結果跟 hash % length 一樣，而且效率還更好。

• 為什么不直接用 hashCode() 而是用它的高 16 位進行異或計算新 hash 值？#

int 類型占 32 位，可以表示 2^32 種數（范圍：-2^31 到 2^31-1），而哈希表長度一般不大，在 HashMap 中哈希表的初始化長度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 來尋址，那么相當于只有低 4 位有效，其他高位不會有影響。這樣假如幾個 hashCode 分別是 210、220、2^30，那么尋址結果 index 就會一樣而發生沖突，所以哈希表就不均勻分布了。

尋址算法的優化：用與運算替代取模，提升性能。（由于計算機對比取模，與運算會更快）。

在 JDK1.8 中，HashMap 的結構由數組和鏈表（或紅黑樹）組成。數組是 HashMap 的主體，鏈表和紅黑樹則是為了解決哈希沖突而存在的。從上圖可以看出，HashMap 由一個個 Node 節點組成，每個節點包含了鍵值對的信息，以及指向下一個節點的指針。HashMap 內部維護了一個數組 table，每個元素都是一個鏈表的頭節點（或者是一個紅黑樹的根節點），當多個鍵映射到同一個位置時，它們會被存儲在同一個鏈表中（或者是同一個紅黑樹中）。當鏈表長度超過閾值（默認為 8）時，鏈表就會被轉換成紅黑樹（如下圖），這樣可以提高查找效率。如果紅黑樹的節點數小于等于6，那么就將紅黑樹轉換回鏈表，以節省空間。

轉換紅黑樹

在 JDK1.8 中，HashMap 還引入了一個新的概念，叫做負載因子(load factor)，它是指哈希表中鍵值對的數量與數組長度的比值。當鍵值對的數量超過了負載因子與數組長度的乘積時，就會觸發擴容操作，HashMap 會自動將數組長度擴大一倍，并將原來的鍵值對重新分配到新的數組中。這樣做的目的是為了保證散列表的性能，因為當負載因子過高時，散列表的性能會急劇下降。