java集合類（四）-HashMap的原碼分析

目錄

前言

​原碼分析

 繼承關系

 類中屬性

 構造函數

 核心方法

總結

附錄1 HashMap與HashSet關系？

​附錄1  HashMap初始化如何保證容量是2的幂？

附錄3 HashMap 如何計算節點所在數組(桶)的位置

附錄4 HashMap 擴容時元素位置如何遷移？

前言

     基于哈希表的 Map 接口的非同步實作，此實作提供所有可選的映射操作，并允許使用 null 值和 null 鍵，不保證映射的順序。另外，HashMap的資料結構是數組+連結清單/紅黑樹。

原碼分析

接下來我們針對其原碼做以下分析：繼承關系、類中屬性、構造函數、核心方法 四個方面分析

 public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
           

• Map: 接口用于存儲元素對（稱作“鍵”和“值”），其中每個鍵映射到一個值
• AbstractMap:實作了Map接口部分方法，為map各自子類實作公共的方法
• Cloneable:支援接口，實作

  Cloneable

  接口，支援Object.clone()方法(

  CloneNotSupportedException

  )
• java.io.Serializable:标記接口，支援序列化

 繼承關系

類中屬性

• DEFAULT_INITIAL_CAPACITY：預設的初始化容量16
• DEFAULT_LOAD_FACTOR：預設的負載因子常量0.75
• MAXIMUM_CAPACITY：最大容量(int型隻能左移動30位,31位就變為負數的了)
• TREEIFY_THRESHOLD：連結清單節點數大于8個連結清單轉紅黑樹
• UNTREEIFY_THRESHOLD：連結清單節點小于6個紅黑樹轉連結清單
• MIN_TREEIFY_CAPACITY：當資料大于等于64的時候才觸發連結清單轉紅黑樹
• loadFactor：負載因子
• threshold：臨界值 = 容量 * 負載因子
• size：映射中存在的鍵值對的數量
• entrySet：具體元素存放集
• table：以Node<k,v>數組存儲元素，長度為2的次幂
• modCount：多線程并發修改觸發fail-fast機制

構造函數

核心方法

接下來我們從初始化、新增、修改、查詢、删除分析下原碼

初始化 Map<k, v> hashMap = new HashMap<>();

•      建構初始容量為16，負載因子為0.75的HashMap

新增 hashMap.put(key,value)

1）根據key計算hash值

2）判斷目前hashMap集合的數組tab[]是否為空；如果為空則執行resize()擴容。

3）根據hash值計算數組的位置i,求得數組tab[i]的值;如果tab[i]=null建立節點并添加到tab[i]并跳轉到4)，否則跳轉到a)

             a) tab[i]的首個元素是否和key相等跳轉到d),否則繼續執行

             b) tab[i]是否為紅黑樹，如果是執行紅黑樹的元素的插入操作并跳轉到d)，否則繼續

             c) 周遊tab[i]直到找到相同的key,或者周遊節點的next為null，在此節點尾插入新增節點

             d) 判斷節點是否新增節點還是修改節點，如果是修改節點則替換原值并跳轉到7)，否則跳轉到4)。

4) 修改計數器modCount+1

5) 修改集合元素大小size+1

6) 判斷size>threshold(擴容閥值)，滿足條件擴容，否則結束

7) 結束流程

擴容步驟：

• 根據原容量的值是否>0計算新容量和擴容閥值并跳轉到4),不大于0則繼續
• 根據原閥值是否>0計算新容量和擴容閥值并跳轉到4),不大于0則繼續
• 初始化預設的容量（16）和閥值（16*0.75）
• 判斷新閥值是否為0，為0則重新計算新閥值
• 建立新數組（新容量大小）
• 遷移老數組資料至新數組

public V put(K key, V value)方法：

public V put(K key, V value) {
    //hash(key)根據key計算hash值;在下文中用hash值計算key分布在數組的位置
    return putVal(hash(key), key, value, false, true);
}


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // tab-hashMap的數組; p-存放(k,v)的節點;n-數組長度;i-數組索引
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // tab為空說明數組還未初始化,HashMap未儲存過資料,故需要擴容resize()
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根據hash值計算key儲存在數組的位置i;tab[i]=null,此處無其它元素，直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //數組位置已經存在其它元素,接下來從連結清單、紅黑樹等添加元素
        Node<K,V> e; K k; //e-需要添加的元素;k-需要添加元素k
        //連結清單的首個元素與需要添加key相等;把目前元素p指派給e,後面替換其鍵值對value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            //目前元素對應的結構為紅黑樹結構,執行樹的新增操作
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //連結清單的首個元素非需要添加的key，循環周遊單向連結清單
            for (int binCount = 0; ; ++binCount) {
                //周遊整個連結清單均無相同的key，新增元素節點并添加到連結清單末尾并退出
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //如果連結清單長度>6,考慮連結清單轉換為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //循環周遊連結清單過程中發現存在的key,則退出等待後面的鍵值對value替換值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //循環周遊連結清單時,目前節點後移
                p = e;
            }
        }
        //e不為空說明待添加的key存在，需要替換value;并退出整個方法，不修改modCount,size
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent為ture代表元素缺少或者value為null才添加
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //修改計數器
    ++modCount;
    //size+1,并判斷是否需要擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

           

擴容方法：resize()

final Node<K,V>[] resize() {
    // oldTab = 擴容前hashMap的數組結構
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    // newCap 需要擴容的容量; newThr擴容閥值(臨界值)
    int newCap, newThr = 0;
    //原容量>0說明原hashMap已經存在元素，一般擴容為其2倍
    if (oldCap > 0) {
        //如果原容量已經是最大值,僅調整臨界值為Integer的最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 擴容後容量為其原容量的2倍(newCap = oldCap << 1)
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //擴容閥值擴容為其原閥值2倍
            newThr = oldThr << 1; // double threshold
    }
    //原容量<=0但原閥值>0,新容量=原閥值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
     //原容量、原閥值均<=0,HashMap為初始化狀态,容量和閥值擴容為預設值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //新閥值為0，從新計算新閥值(新容量*負載因子)
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //擴容閥值=新計算的擴容閥值
    threshold = newThr;
    //根據新容量建立HashMap建立擴容後需要的數組
    @SuppressWarnings({"rawtypes","unchecked"})
     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        //周遊原數組指派;由于是擴容為2倍且為2的幂;擴容後的位置為其原位置或者原位置+原容量
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                //原數組的額j位置置為null,垃圾回收釋放原數組空間
                oldTab[j] = null;
                if (e.next == null)
                    //原數組目前位置隻有一個值,計算擴容後位置并指派
                    //擴容後的此位置也僅有一個元素
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //數組所在位置的元素為紅黑樹,執行樹的擴容操作,涉及紅黑樹轉連結清單
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    //原數組所在的位置有多個元素(單向連結清單),周遊連結清單
                    Node<K,V> loHead = null, loTail = null;  //擴容後位置不變
                    Node<K,V> hiHead = null, hiTail = null;  //擴容後位置+原容量
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //擴容後位置不變（思考下2的幂bit位隻有一個1）
                        if ((e.hash & oldCap) == 0) { //結果隻有0和oldCap
                            if (loTail == null)
                                //數組目前位置首次添加loHead=loTail=e
                                loHead = e;
                            else
                                //數組位置非首次添加,後來元素添加到前一個元素末尾成單向連結清單
                                loTail.next = e;
                            //loTail始終定位到正在周遊的元素,為loTail.next = e做準備
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        //目前位置添加擴容後新組裝的連結清單
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        //目前位置+oldCap添加擴容後新組裝的連結清單
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
           

• 關于紅黑樹的操作,後期單獨分析
• 擴容後元素位置為原位置或者原位置+原容量下文詳細分析

修改 hashMap.replace(key,value)

      1）調用hash()方法計算key的hash值

      2）調用getNode()獲得需要替換的節點(參數為上一步的計算的hash值和key)

                 a）根據hash值計算查詢節點所在數組位置；并獲得目前位置的的首個元素first

          b) first的key與需要查詢的key相等return first，否則繼續

          c) first資料類型為紅黑樹，查詢紅黑樹的節點傳回，否則繼續

          d) 周遊first查找相同的key傳回，或者傳回null

      3）節點不為null,替換目前節點的value并傳回原value;節點為null退出return;

查詢 hashMap.get(key)

• 調用hash()方法計算key的hash值
• 調用getNode()獲得查找節點(參數為上一步的計算的hash值和key)
• 傳回key對應的value

删除 hashMap.remove(key)

• 根據hash()計算key的hash值，用于後面定位key的位置

               A) 同getNode()方法類似根據key和其hash值定位删除的節點,如有則繼續

               B) 删除對應的節點node

               C) 删除後改變對應的數組或者連結清單或者紅黑樹的連接配接

               D) 修改計數器modCount+1;集合的容量size-1;

              E) 傳回需要删除的節點

• 調用removeNode()方法删除節點

remove()方法

removeNode()方法

總結

• HashMap實作了Map接口對鍵值對進行映射, 并允許使用null值和null鍵,但中不允許重複的鍵
• HashMap資料結構為數組+連結清單/紅黑樹(連結清單長度>8且數組長度>=64轉換為紅黑樹)
• HashMap 的執行個體有兩個參數影響其性能：初始容量 和加載因
• HashMap采用了數組和連結清單的資料結構，能在查詢和修改友善繼承了數組的線性查找和連結清單的尋址修改

附錄1 HashMap與HashSet關系？

 HashSet底層實作是HashMap<k,v>;   v是固定對象PERSENT

附錄2  HashMap初始化如何保證容量是2的幂？

初始化時調用方法tableSizeFor()保證容量為2的幂：

n |= n >>> 1 等價于 n = n | n>>>1 ; 接下來主要分析下n|n>>>1運算結果

• 首先二進制bit位僅且僅0、1;
• 桶容量如果為2的幂,二進制僅有一個1(例：01=1,10=2,100=4,1000=8,….)
• n>>>1相當于n的值無符号右移動1位,高位補0

我得到們接下來實際示範一下具體的例子就能了解其原理:（見下圖）

• 目的確定左側第一個1後面的位均為1
• 操作完成最後獲得的n再+1（n+1）後，原數的最左側1進一位，且後面bit位均為0

下圖的n為001*….經過運算後001後面的所有位均為1（0011 1111 1111 1111 1111 1111 1111 1111）；

執行n+1後的結果為：0100 0000 0000 0000 0000 0000 0000 0000

附錄3 HashMap 如何計算節點所在數組(桶)的位置

計算key所在數組的下标經過2步驟：

• Step1：hash()方法計算key的hash值
• Step2：根據hash值和數組長度計算key所在數組位置（hash值以數組長度為模）

hash()方法通過key對應hashCode的低16位與高16位異或操作得到key的hash值

hash & (數組長度-1) 獲得key對應的數組位置即為取模操作；了解稍費勁，接下來我們看下具體的例子：

例如：數組的長度(桶容量)為8 (二進制：1000) ;

• 8-1=7的二進制位0111
• hash & 0111隻看後3位(二進制位操作符&代表2個運算的數都是1則為1否則為0)
• hash & 0111相當于與8取模（結果在[0-7]之間）

十進制	hash值(二進制)	桶容量(8) - 1	hash&(cap-1)	數組位置
1	0001	0111	0001	1
2	0010	0111	0010	2
8	1000	0111	0000
9	1001	0111	0001	1
10	1010	0111	0010	2
16	1 0000	0111	0000
17	1 0001	0111	0001	1
18	1 0010	0111	0010	2
32	10 0000	0111	0000
33	10 0001	0111	0001	1
34	10 0010	0111	0010	2

附錄4 HashMap 擴容時元素位置如何遷移？

       hashMap擴容後原節點擴容後位置在原位置 or 原位置+原容量，當hash & 原容量=0則在原位置，否則在原位置+原容量；引起這個的原因主要是由于①容量為2的幂 ②擴容後容量為原容量的2倍(計算公式為：hash & 原容量=0或者原容量)

       首先我們先看下hash & 原容量的值為0或者原容量，為什麼？是以原容量是2的幂且二進制表示的時候僅有一位bit位為1，與其它數按位&操作，要麼全為0，要麼跟原容量相等。

       解決了上一個問題，那為什麼節點擴容後位置為原位置或者原位置+原容量呢？其實這個原因主要還是我們HashMap擴容量為其原來的2倍（二進制位表示的話為原容量左移1位），接下來我們分析下一組資料即可找到原因，例如原容量為8現在擴容為16（你會發現數組位置16個數一個循環[0-15]）

Hash值	桶容量為8	桶容量為16
十進制	二進制	cap - 1	hash&(cap-1)	數組位置	cap- 1	hash&(cap-1)	數組位置	hash&原cap (8)
1	0001	0111	0001	1	0 1111	0001	1
2	0010	0111	0010	2	0 1111	0010	2
8	1000	0111	0000	0 1111	1000	8	1
9	1001	0111	0001	1	0 1111	1001	9	1
10	1010	0111	0010	2	0 1111	1010	10	1
16	1 0000	0111	0000	0 1111	0000
17	1 0001	0111	0001	1	0 1111	0001	1
18	1 0010	0111	0010	2	0 1111	0010	2
22	1 0110	0111	0110	6	0 1111	0110	6
24	1 1000	0111	0000	0 1111	1000	8	1
32	10 0000	0111	0000	0 1111	0000
33	10 0001	0111	0001	1	0 1111	0001	1
34	10 0010	0111	0010	2	0 1111	0010	2