JDK1.8中HashMap實現

JDK1.8中的HashMap實現跟JDK1.7中的實現有很大差別。下麵分析JDK1.8中的實現，主要看put和get方法。

構造方法的時候並沒有初始化，而是在第一次put的時候初始化

putVal方法的主要邏輯是這樣的：

1、如果數組還沒有初始化（數組長度是0），則先初始化

2、通過hash方法計算key的hash值，進而計算得到應該放置到數組的位置

3、如果該位置為空，則直接放置此處

4、如果該位置不為空，而且元素是紅黑樹，則插入到其中

5、如果是鏈表，則遍歷鏈表，如果找到相等的元素則替換，否則插入到鏈表尾部

6、如果鏈表的長度大於或等於8，則將鏈表轉成紅黑樹

1、計算hash求位置

2、看第一個元素是不是要找的，是則返回，否則遍歷

擴容就是將舊數組的元素移動到新數組

總結：

1、HashMap底層是用數組+雙向鏈表+紅黑樹實現的

2、插入元素的時候，首先通過一個hash方法計算得到key的哈希值，進而計算出待插入的位置

3、如果該位置為空，則直接插入（包裝成Node）

4、如果該位置有值，則依次遍歷。比較的規則是，hash值相同，key值相等的元素視為相同，則用新值替換舊值並返回舊值。

5、如果該位置的元素是紅黑樹結構，則同理，查找，找到則替換，沒找到則插入。

劃重點：

JDK1.8中HashMap與JDK1.7中有很多地方不一樣

1、1.8中引入了紅黑樹，而1.7中沒有

2、1.8中元素是插在鏈表的尾部，而1.7中新元素是插在鏈表的頭部

3、擴容的時候，1.8中不會出現死迴圈，而1.7中容易出現死迴圈，而且鏈表不會倒置