HashMap實作原理（jdk1.7/jdk1.8）

HashMap的底層實作： 

1、簡單回答 

  JDK1.7：HashMap的底層實作是：數組+連結清單

  JDK1.8：HashMap的底層實作是：數組+連結清單/紅黑樹

  為什麼要紅黑樹？

  紅黑樹：一個自平衡的二叉樹

  當結點多了用紅黑樹，少了用連結清單

  因為少的話用紅黑樹太複雜，多了話用紅黑樹可以提高查詢效率。

  紅黑樹：（自動調整根結點，保證左右兩邊的結點數差不多），它會左旋，右旋來實作。

 JDK1.7：HashMap的底層實作是：數組+連結清單

2、複雜回答v1.0版

 每一個對映射關系的存儲位置：

  存儲的位置：

（1）先計算key的hash值，通過hashCode()就可以得到，

（2）再用hash值經過各種（異或）操作，得到一個int數字，目的是使得更均勻的分布在數組的每一個元素中。

（3）再用剛才的int值，與table數組的長度-1做一個“按位與&"

運算，目的是得到一個[i]

    因為數組的長度是2的n次方，長度-1的數的二進制是前面都是0，後面都是1，任何數與它做“&”，結果一定是[0,該數]之間

 為什麼會出現連結清單？

  (1)兩個不同的key對象，仍然可能出現hashCode值一樣

  (2)就算hashCode不一樣，經過剛才的計算，得到[i]是一樣的

  (3)而我們的數組的元素table[i]本來隻能放一個元素，那麼現在有多個元素需要存儲到table[i]中，隻能把這幾個元素用連結清單連接配接起來

   簡單比喻：

   y = f(x)

  兩個不一樣的x，可能得到一樣的y

 那麼存儲到HashMap中的是什麼樣的元素呢？

  (1)首先是Map.Entry類型：映射項（鍵-值對）。

  (2)其次HashMap有一個内部類HashMap.Entry實作了Map.Entry接口類型

  内部類Entry由四部分組成：

  （1）key

  （2）value

  （3）下一個Entry：next

  （4）hash值計算的整數值，為了後面查詢快一點

  如何避免重複？

  如果兩個key的hash值是一樣的，還要調用一下equlas()方法，如果傳回true，就會把新的value替換舊的value。

  如果兩個key的hash值是一樣的，還要調用一下equlas()方法，如果傳回false，就會把新的Entry連接配接到舊的Entry所在連結清單的頭部(first)

 如果兩個key的hash值是不一樣的，但是[i]是一樣的，就會把新的Entry連接配接到舊的Entry所在連結清單的頭部(first)

  如果兩個key的hash值是不一樣的，并且[i]不一樣的，肯定存在不同table[i]中

  我們把table[i]稱為“桶bucket”。

  回憶：兩個對象的hash值：

  （1）如果兩個對象是“相等”，他們的hash值一定是一樣

   （2）如果兩個對象的hash值是一樣，他們可能是相同的對象，也可能是不同的對象。

  3、複雜追蹤源代碼v2.0版

  (1)什麼時候擴容

  當元素的個數達到“門檻值”，并且新添加的映射關系計算出來的table[i]位置是非空的情況下，再擴容

  預設加載因子 (0.75)：DEFAULT_LOAD_FACTOR

  門檻值 = table.length * 加載因子(loadFactor)

  第一次門檻值：16 * 0.75 = 12

  初始容量：DEFAULT_INITIAL_CAPACITY：16

  第二次門檻值：32 * 0.75 = 24

  ...

 HashMap中table的長度有一個要求：必須是2的n次方

  (2)跟蹤一下put方法的源代碼

  第一步：如果table是空的，會先把table初始化為一個長度為16的數組，如果你指定的長度不是2的n次方，會往上糾正為最接近的2的n次方

          并且把門檻值 threshold= table.length * 加載因子(loadFactor) = 12。

  第二步：如果key是null，首先确定的位置是table[0]，

     如果原來table[0]已經有key為null的Entry，用新的value替換舊的value

   如果原來table[0]沒有key為null的Entry，那麼建立一個新的Entry對象，作為table[0]桶下面的連結清單的頭，原來的那些作為它next。

  第三步：如果key不是null，那麼用key的hashCode值，通過hash()函數算出一個int值稱為"hash"

  第四步：通過剛才的“hash”的int值與table.length-1做&運算，得到一個下标index，表示新的映射關系即将存入table[index]

  第五步：循環判斷table[index]位置是否為空，并且是否有Entry的key與我新添加的key是否“相同”，如果相同，就用新的value替換舊的value

  第六步：添加新的映射關系

    （1）判斷是否要擴容：        

        當元素的個數達到“門檻值”，并且新添加的映射關系計算出來的table[i]位置是非空的情況下，table再擴容為原來的2倍長

        如果擴容了，那麼要重新計算hash和index

    （2）把新的映射關系建立為一個Entry的對象放到table[index]的頭部。

 JDK1.8:HashMap的底層實作是：數組+連結清單/紅黑樹 

  1、複雜回答v1.0

  （1）映射關系的類型

 添加到HashMap1.8種的映射關系的對象是HashMap.Node類型，或者是HashMap.TreeNode類型。

  它也是Map.Entry接口的實作類。

 （2）映射關系添加到table[i]中時，如果裡面是連結清單，新的映射關系是作為原來連結清單的尾部

  “七上八下”：JDK1.7在上，JDK1.8在下。

  為什麼要在下面，因為如果是紅黑樹，那麼是在葉子上，保持一緻，都在下面。

 （3）擴容的時機不同

  第一種擴容：元素個數size達到門檻值threshod = table.length * 加載因子  并且table[i]是非空的

 第二種擴容：當某個桶table[index]下面的結點的總數原來已經達到了8個，這個時候，要添加第9個時，會檢查

  table.length是否達到64，如果沒達到就擴容。如果添加第10個時，也會檢查table.length是否達到64，如果沒達到就擴容。

 為什麼，因為一旦擴容，所有的映射關系要重新計算hash和index，一計算原來table[index]下面可能就沒有8個，或新的映射關系也可能不在table[index]，

  這樣就可能均勻分布。

 （4）什麼時候從連結清單變成紅黑樹

 當table[index]下面結點的總數已經達到8個，并且table.length也已經達到64，那麼再把映射關系添加到

  table[index]下時，就會把原來的連結清單修改紅黑樹

  （5）什麼時候會從紅黑樹變為連結清單

  當删除映射關系時table[index]下面結點的總數少于6個，會把table[index]下面的紅黑樹變回連結清單。

2、put的源代碼v2.0

 第一步：計算key的hash，用了一個hash()函數，目的得到一個比hashCode更合理分布的一個int值

 第二步：如果table是空的，那麼把table初始化為長度為16的數組，阈(yu)值初始化為= 預設的長度16 * 預設的加載因子0.75 = 12

 DEFAULT_INITIAL_CAPACITY：預設的初始化容量16

 DEFAULT_LOAD_FACTOR：預設加載因子 0.75

 第三步：檢視table[index]是否為空，如果為空，就直接new一個Node放進去

     index = hash的int值 & table.length-1

  第四步：先檢視table[index]的根節點的key是否與新添加的映射關系的key是否“相同”，如果相同，就用新的value替換原來的value。

   第五步：如果table[index]的根節點的key與新添加的映射關系的key不同，

  還要看table[index]根結點的類型是Node還是TreeNode類型，

  如果是Node類型，那麼就檢視連結清單下的所有節點是否有key與新添加的映射關系的key是否“相同”，如果相同，就用新的value替換原來的value。

  如果是TreeNode類型，那麼就檢視紅黑樹下的所有葉子節點的key是否與新添加的映射關系的key是否“相同”，如果相同，就用新的value替換原來的value。

 第六步：如果沒有找到table[index]有結點與新添加的映射關系的key“相同”，那麼

 如果是TreeNode類型，那麼新的映射關系就建立為一個TreeNode，連接配接到紅黑樹中

 如果是Node類型，那麼要檢視連結清單的結點的個數，是否達到8個，如果8個，并且table.length小于64，那麼先擴容。

 TREEIFY_THRESHOLD：樹化門檻值8

 MIN_TREEIFY_CAPACITY：最小樹化容量64

 UNTREEIFY_THRESHOLD：反樹化，從數變為連結清單的門檻值6