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

hash算法的優(yōu)化：對(duì)每個(gè)hash值，在它的低16位中，讓高低16位進(jìn)行異或，讓它的低16位同時(shí)保持了高低16位的特征，盡量避免一些hash值后續(xù)出現(xiàn)沖突，大家可能會(huì)進(jìn)入數(shù)組的同一位置。

對(duì)尋址算法的優(yōu)化

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

hash & (n-1) 效果是跟hash對(duì)n取模是一樣的，但是與運(yùn)算的性能要比hash對(duì)n取模要高很多。數(shù)組的長(zhǎng)度會(huì)一直是2的n次方，只要他保持?jǐn)?shù)組長(zhǎng)度是2的n次方。

• 尋址為什么不用取模？

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

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

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

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

尋址算法的優(yōu)化：用與運(yùn)算替代取模，提升性能。（由于計(jì)算機(jī)對(duì)比取模，與運(yùn)算會(huì)更快）。

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

轉(zhuǎn)換紅黑樹

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