HashMap在實際開發(fā)中用到的頻率非常高，面試中也是熱點。所以決定寫一篇文章進行分析刀荒，希望對想看源碼的人起到一些幫助，看之前需要對鏈表比較熟悉棘钞。
以下都是我自己的理解欠窒，歡迎討論，寫的不好輕噴岸浑。
一们镜、為什么需要散列表
HashMap中的數據結構為散列表，又名哈希表姨拥。在這里我會對散列表進行一個簡單的介紹绅喉，在此之前我們需要先回顧一下 數組、鏈表 的優(yōu)缺點叫乌。
- 數組：數組刪除柴罐、插入性能不佳，尋址性能極優(yōu)
- 鏈表：鏈表查詢性能不佳憨奸，刪除革屠、插入性能極優(yōu)
數組和鏈表的優(yōu)缺點取決于他們各自在內存中存儲的模式，也就是直接使用順序存儲或鏈式存儲導致的。無論是數組還是鏈表似芝，都有明顯的缺點那婉。而在實際業(yè)務中，我們想要的往往是尋址国觉、刪除吧恃、插入性能都很好的數據結構，散列表就是這樣一種結構麻诀，它巧妙的結合了數組與鏈表的優(yōu)點痕寓，并將其缺點弱化（并不是完全消除）
二、散列表原理
- 散列表：散列表是一個根據key來訪問value的存儲結構蝇闭，HashMap中實現的散列表是一個鏈表類型的數組呻率，即數組+鏈表，用來存儲key-value數據對呻引。Ps：在1.8及以后版本的jdk中礼仗，HashMap中還加入了紅黑樹，關于這點后文會細說逻悠。
哈希函數與下標的計算
散列表的做法是將key映射到數組的某個下標元践，存取的時候通過key獲取到下標（index）然后通過下標直接存取。速度極快童谒，而將key映射到下標需要使用散列函數单旁，又名哈希函數。說到哈希函數可能有人已經想到了饥伊，如何將key映射到數組的下標象浑。
圖中計算下標使用到了以下兩個函數：
-
hash(key)：對key進行hash計算，獲得一個int類型的hash值 效果參考Object.hashCode() -
index(hash, N+1)：對上面得到的hash值進行計算琅豆，獲得一個不超過數組大小的下標 效果參考 hash%(N+1)
值得注意的是愉豺，下標并不是通過hash函數直接得到的，計算下標還要對hash值做index()處理茫因。
Ps：在散列表中蚪拦，數組的格子叫做桶，下標叫做桶號冻押，桶可以包含一個key-value對驰贷，為了方便理解，后文不會使用這兩個名詞翼雀。
哈希碰撞與下標沖突
以下是哈希碰撞相關的說明：
- 哈希碰撞的定義：有a饱苟，b兩條數據孩擂，且a != b狼渊，對于這組數據，如果有hash(a) == hash(b)，則哈希發(fā)生碰撞
- 原因：hash函數的返回值是一個int類型的數據狈邑，int的取值是有范圍的城须，而散列表的key是沒有范圍的，可以是任何值米苹。將多數key映射到少數hashCode糕伐，必然會有多個key對應同一個hashCode的情況。
- 可能性：許多人認為int的取值范圍夠大蘸嘶，在實際使用中很少會發(fā)生碰撞良瞧。其實不然，可以參見生日悖論训唱，簡單解釋一下生日悖論：23人里有兩人同一天生日的概率超過50%褥蚯。（更加具體的說明請自行搜索“生日悖論”）同理，哈希碰撞的可能性是很大的况增。
以下是下標沖突相關的說明：
- 下標沖突：與哈希的碰撞類似赞庶，在將hashCode映射到數組下標時也是有可能重復的。在往數組的某個下標插入節(jié)點的時候發(fā)現該下標已經有其他節(jié)點澳骤，即為下標沖突歧强。
很多人認為哈希值的碰撞和下標沖突是同一個東西，其實不是的为肮，它們的正確關系是這樣的摊册，hashCode發(fā)生碰撞，則下標一定沖突弥锄；而下標沖突丧靡，hashCode并不一定碰撞
如何解決碰撞和沖突
上文提到，在jdk1.8以前HashMap的實現是散列表 = 數組 + 鏈表 籽暇，但是到目前為止我們還沒有看到鏈表起到的作用温治。事實上，HashMap引入鏈表的用意就是解決下標沖突戒悠。
下圖是引入鏈表后的散列表：
如上圖所示熬荆，左邊的豎條，是一個大小為16的數組绸狐，其中存儲的是鏈表的頭結點卤恳，我們知道，擁有鏈表的頭結點即可訪問整個鏈表寒矿，所以認為這個數組中的每個下標都存儲著一個鏈表突琳。其具體做法是，如果發(fā)現下標沖突符相，則后插入的節(jié)點以鏈表的形式追加到前一個節(jié)點的后面拆融。
-
舉個例子蠢琳，現在假設有節(jié)點B要添加到表中，那么遇到沖突后的整個流程是這樣的：
1镜豹、計算得到B.key對應的下標為 n
2傲须、判斷 n 下標下是否有值
3、發(fā)現有值趟脂，下標沖突泰讽，獲取到該下標已有的節(jié)點A
4、判斷(B.key).equals(A.key)
5昔期、如果key相等已卸，根據key唯一的特性，B節(jié)點覆蓋A節(jié)點
6硼一、如果key不等咬最，判斷A.next是否有值
7、如果A.next也有值欠动，回到步驟4對A.next節(jié)點進行對比
8永乌、重復步驟4-7，直到發(fā)現key相等的節(jié)點具伍，或遍歷到鏈表的最后一個節(jié)點X翅雏，執(zhí)行操作X.next = B
Ps：讀取節(jié)點的流程與添加類似，先計算下標人芽，然后遍歷鏈表望几，直到找到對應的key
這種使用鏈表解決沖突的方法叫做：拉鏈法（又叫鏈地址法）。HashMap使用的就是拉鏈法萤厅，拉鏈法是沖突發(fā)生以后的解決方案橄抹。
Q：有了拉鏈法，就不用擔心發(fā)生沖突嗎惕味？
A：并不是楼誓！由于沖突的節(jié)點會不停的在鏈表上追加，大量的沖突會導致單個鏈表過長名挥，使查詢性能降低疟羹。所以一個好的散列表的實現應該從源頭上減少沖突發(fā)生的可能性，沖突發(fā)生的概率和哈希函數返回值的均勻程度有直接關系禀倔，得到的哈希值越均勻榄融，沖突發(fā)生的可能性越小。為了使哈希值更均勻救湖，HashMap內部單獨實現了hash()方法愧杯。
三、HashMap中散列表的實際運用
以上是散列表的存儲結構鞋既，但是在被運用到HashMap中時還有其他需要注意的地方力九，這里會詳細說明憔维。
擴容與負載因子
現在我們清楚了散列表的存儲結構，細心的人應該已經發(fā)現了一個問題：Java中數組的長度是固定的畏邢，無論哈希函數是否均勻，隨著插入到散列表中數據的增多检吆，在數組長度不變的情況下舒萎，鏈表的長度會不斷增加。這會導致鏈表查詢性能不佳的缺點出現在散列表上蹭沛，從而使散列表失去原本的意義臂寝。為了解決這個問題，HashMap引入了擴容與負載因子摊灭。
以下是和擴容相關的一些概念和解釋：
- 默認容量：HashMap中數組的長度如果不指定咆贬，則默認為16
-
2的n次冪：HashMap在new的時候可以指定數組長度，但不管如何指定帚呼，實際長度一定是
2的n次冪（16掏缎、32、64煤杀、128等）眷蜈，舉幾個例子，指定長度為17或29沈自，實際長度為32酌儒，指定為35、57或63枯途，實際長度為64忌怎，以此類推。 -
擴容：隨著散列表存儲節(jié)點的不斷增加酪夷，散列表中數組的長度也應該增加榴啸，為了保證
2的n次冪特性，每次擴容都是當前長度*2晚岭， 擴容的方法是插掂，新建一個兩倍的數組，然后遍歷散列表中的所有節(jié)點腥例，重新計算下標放入新數組辅甥。 -
負載因子：由于散列存儲下標具有不確定性，在數組即將被占滿的時候燎竖，后續(xù)添加會發(fā)生大量沖突璃弄，為了避免，需要使數組在即將被占滿前就擴容构回，而不是等待數組被占滿夏块。負載因子決定具體何時擴容疏咐。其默認值是
0.75，可以在調用構造器的時候指定脐供。0.75的意思是浑塞，在調用put方法時，算上被put的節(jié)點政己，如果當前數組被占用達到75%則進行擴容酌壕。
Ps：擴容要重新計算下標，擴容要重新計算下標歇由，擴容要重新計算下標卵牍，因為下標的計算和數組長度有關，長度改變沦泌，下標也應當重新計算糊昙。
引入紅黑樹
在1.8及其以上的jdk版本中，HashMap又引入了紅黑樹谢谦。
- 紅黑樹：紅黑樹是一個相對平衡的二叉查找樹释牺。平衡二叉樹的查找原理和二分查找類似，時間復雜度也一樣回挽，都是從有序序列的中間開始查找船侧。此處不做更詳細的解釋，只需要知道是一個查詢效率很高的數據結構即可厅各。
紅黑樹的引入被用于替換鏈表镜撩，上文說到，如果沖突過多队塘，會導致鏈表過長袁梗，降低查詢性能，均勻的hash函數能有效的緩解沖突過多憔古，但是并不能完全避免遮怜。所以HashMap加入了另一種解決方案，在往鏈表后追加節(jié)點時鸿市，如果發(fā)現鏈表長度達到8锯梁，就會將鏈表轉為紅黑樹，以此提升查詢的性能焰情。
