HashMap底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組 + 單向鏈表 + 紅黑樹

HashMap底層數(shù)據(jù)結(jié)構(gòu).png

一、相關(guān)概念

1、Hash沖突：就是在一個數(shù)組的位置上出現(xiàn)了一個鏈表，這就是所謂的hash沖突。

2、解決hash沖突，就是讓鏈表的長度變短，或者干脆就是不產(chǎn)生鏈表，一個好的hash算法應(yīng)該是讓數(shù)據(jù)很好的散列到數(shù)組的各個位置，
   即一個位置存一個數(shù)據(jù)就是最好的散列，下面說的鏈地址法，說的就是在hashmap里面沖突的時候，一個節(jié)點可以存多個數(shù)據(jù)。

3、桶(bucket)：數(shù)組中的每一個元素的位置就是一個桶。

4、HashMap的初始容量：16，并且 HashMap的底層數(shù)組長度總是2的n次方
           static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
 
   HashMap的最大容量：2的30次方
           static final int MAXIMUM_CAPACITY = 1 << 30;

5、 HashMap的加載因子是：0.75f
           static final float DEFAULT_LOAD_FACTOR = 0.75f;

         如果負(fù)載因子越大，對空間的利用更充分，然而后果是查找效率的降低；
         如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過于稀疏，對空間造成嚴(yán)重浪費。系統(tǒng)默認(rèn)負(fù)載因子為0.75，一般情況下我們是無需修改的。

6、將鏈表轉(zhuǎn)為紅黑樹設(shè)置的鏈表長度的閾值：8
          static final int TREEIFY_THRESHOLD = 8;

7、 從源碼中可以看出，每次新建一個HashMap時，都會初始化一個table數(shù)組。table數(shù)組的元素為Node節(jié)點。
    Node為HashMap的內(nèi)部類，它包含了鍵key、值value、下一個節(jié)點next，以及hash值，正是由于Node才構(gòu)成了table數(shù)組的項為鏈表。

8、創(chuàng)建一個Node類型的數(shù)組，transient 意思是不能序列化
          transient Node<K,V>[] table;

二、計算key在數(shù)組中的位置

1、獲取key的hash值
     (h = key.hashCode()) ^ (h >>> 16)
   
     ● 通過hashCode方法獲取到key的hash值，然后把hash值的低16位與高16位進(jìn)行異或運(yùn)算得到的值即為該key的hash值
  
     ● 原因：
           因為后面要使用 (n - 1) & hash，所以通過hashCode方法獲取的hash值不同也可能數(shù)組下標(biāo)相同。為了降低運(yùn)算結(jié)果值的相同概率，
        使table數(shù)據(jù)分布均勻，減少碰撞

2、計算key在數(shù)組中的位置 【n是數(shù)組的容量，即長度】

   ①、對于HashMap的table數(shù)組而言，數(shù)據(jù)分布需要均勻（最好每項都只有一個元素，這樣就可以直接找到），不能太緊也不能太松，
      太緊會導(dǎo)致查詢速度慢，太松則浪費空間。

   ②、計算hash值后，怎么才能保證table數(shù)組中元素分布均與呢？我們會想到取模，但是由于取模的消耗較大，
      HashMap是這樣處理的：采用按位與運(yùn)算，即  (n - 1) & hash，效率高，可以均勻分布table數(shù)據(jù)和充分利用空間。   
 
   ③、原因：
       ●  (n - 1) & hash   與   hash % n 是等值不等效 ，  (n - 1) & hash 的效率高于 hash % n ，這是HashMap在速度上的一個優(yōu)化。

       ●  按位取與，作用上相當(dāng)于取模mod或者取余%。

★ 為什么 HashMap的底層數(shù)組長度總是2的n次方？

  ● 數(shù)組的默認(rèn)長度是16，用二進(jìn)制表示為：    10000
    (n - 1) 即 (16 - 1) , 用二進(jìn)制表示為：01111

    因為數(shù)組長度總是2的n次方，所以如果擴(kuò)容一次之后，數(shù)組的長度為32，用二進(jìn)制表示為：100000
                            擴(kuò)容一次后，(n - 1) 即 (32 - 1)，用二進(jìn)制表示為： 011111

    然后使用(n - 1) 與 key的 hash 進(jìn)行 & 操作，結(jié)果是由key的hash值決定的(hash值是一個整型)

  ● 如果數(shù)組的長度不是2的n次方，假如數(shù)組的長度為15 ，則用二進(jìn)制表示為：011111
                        則 (n - 1) 即 (15 - 1) , 用二進(jìn)制表示為：011110

    然后使用(n - 1) 與 key的 hash 進(jìn)行 & 操作，因為數(shù)組長度不是2的n次冪，所以 (n - 1) 轉(zhuǎn)換為二進(jìn)制最后一位永遠(yuǎn)都是0 ，
    & 的結(jié)果不能只由key的hash值決定的(hash值是一個整型)，所以空間減少，產(chǎn)生hash碰撞的概率就高

    例如數(shù)組長度為9，hash值為3，計算其在數(shù)組上的位置為： 3 & (9 - 1) = 0  -->   0011 & 1000 = 0
        數(shù)組長度為9，hash值為2，計算其在數(shù)組上的位置為：2 & (9 - 1) = 0   -->   0010 & 1000 = 0  在數(shù)組的相同位置上，發(fā)生碰撞；

    例如數(shù)組長度為8，hash值為3，計算其在數(shù)組上的位置為：3 & (8 - 1) = 3   -->   0011 & 0111 = 0011      
        數(shù)組長度為8，hash值為2，計算其在數(shù)組上的位置為：2 & (8 - 1) = 2   -->   0010 & 0111 = 0010   不同位置上，不碰撞；

▲ 總結(jié)：數(shù)組的長度必須是2的n次冪，當(dāng)length = 2^n時，不同的hash值發(fā)生碰撞的概率比較小，這樣就會使得數(shù)據(jù)在table數(shù)組中分布較均勻，
       查詢速度也較快。

三、HashMap的put方法執(zhí)行過程可以通過下圖來理解：

HashMap的put方法.png

①、調(diào)用put方法，首先判斷數(shù)組table是否為null或數(shù)組的長度是否為0，如果是，就執(zhí)行resize()進(jìn)行擴(kuò)容，轉(zhuǎn)向②，如果不是，轉(zhuǎn)向②；

②.根據(jù)鍵key計算hash值得到插入的數(shù)組索引i，如果table[i]==null，直接新建節(jié)點添加，轉(zhuǎn)向⑥，如果table[i]不為空，轉(zhuǎn)向③；

③.判斷table[i]位置的key是否和要添加的key相同(通過hashCode以及equals進(jìn)行比較)，如果相同直接覆蓋舊的value，添加新value，
  并返回舊的value，否則轉(zhuǎn)向⑥，，如果不同，轉(zhuǎn)向④；

④.判斷table[i] 是否 instanceof TreeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，轉(zhuǎn)向⑥，否則轉(zhuǎn)向⑤；

⑤、遍歷table[i]位置的鏈表，判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操作，否則進(jìn)行鏈表的插入操作；
   遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；

⑥.插入成功后，數(shù)組長度加1，然后判斷實際存在的鍵值對數(shù)量size是否超過了臨界值threshold(數(shù)組容量 * 加載因子)，如果超過，進(jìn)行擴(kuò)容。

四、HashMap的resize方法執(zhí)行過程：

★ resize()方法的作用：
                 初始化數(shù)組Node； 
                 對數(shù)組進(jìn)行擴(kuò)容

①、獲取原來數(shù)組的長度oldCap(oldCapacity)，進(jìn)行判斷：

       if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }

②、如果數(shù)組長度oldCap > 0，判斷數(shù)組長度oldCap是否 > 數(shù)組長度的最大值(2的30次方)，如果大于，則不進(jìn)行擴(kuò)容，返回原來的數(shù)組oldTab；
     
   否則判斷 oldCap << 1是否大于數(shù)組長度的最大值(2的30次方) 并且 oldCap是否 > 數(shù)組長度的最大值(2的30次方) ，
        如果不大于，則進(jìn)行擴(kuò)容，即擴(kuò)容后的數(shù)組長度為原來數(shù)組長度的2倍，臨界值threshold也要左移1位，擴(kuò)大到原來的2倍

③、如果數(shù)組長度oldCap <= 0，則對數(shù)組進(jìn)行初始化操作，數(shù)組默認(rèn)長度為16，臨界值threshold(數(shù)組容量 * 加載因子)為12(16*0.75)；
        newCap = DEFAULT_INITIAL_CAPACITY
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY) 

④、創(chuàng)建新數(shù)組newTab，數(shù)組容量為擴(kuò)容后的，即舊數(shù)組容量的2倍

⑤、判斷舊數(shù)組是否使null，如果不是，則遍歷舊數(shù)組，如果oldTab[i] ！= null，則把oldTab[i] = null 【把舊數(shù)組oldTab[i] 置空】

       ●  判斷oldTab[i] 下面是不是null [即 e.next == null]，如果不存在，則重新計算oldTab[i] 在新數(shù)組中的位置

       ●  判斷oldTab[i] 下面是一個紅黑樹，則把該紅黑樹進(jìn)行split(分割)，然后重新計算在新數(shù)組中的位置

       ●  判斷oldTab[i] 下面是一個鏈表(該鏈表的長度不會超過8)，則進(jìn)行循環(huán)遍歷，新數(shù)組中元素的位置只可能在兩個地方，
           一個是原下標(biāo)的位置，另一個是下標(biāo)為 [原下標(biāo) + 原容量] 的位置

                ●   如果 (e.hash & oldCap) == 0，則新數(shù)組中元素的位置在原下標(biāo)的位置

                ●   如果 (e.hash & oldCap) != 0，則新數(shù)組中元素的位置在下標(biāo)為 [原下標(biāo) + 原容量] 的位置

⑥、返回新數(shù)組newTab