JDK1.8 HashMap putValue源碼解析

今天主要和大家一起看一下JDK1.8裡面HashMap類的putValue的原理。

分析能力有限，有錯誤歡迎指出。 廢話不多說開始把！

今天要分析的就是這個方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) 
           

首先看一下源碼

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == )
        //這裡的resize  是初始化的時候調用 後面會講
            n = (tab = resize()).length;    //重新計算一下大小
    //擷取要插入元素在 哈希桶中的位置
    if ((p = tab[i = (n - ) & hash]) == null) //如果這個位置沒有Node
        //   return new Node<>(hash, key, value, next);
        tab[i] = newNode(hash, key, value, null);   //直接建立一個新的Node
        else {  //原來這個桶的位置上有Node
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) //如果你和桶上的第一個Node相等
                e = p;  //直接覆寫值
            else if (p instanceof TreeNode)//如果 你定位到的元素是一個TreeNode(Node的一個子類，也是HashMap的一個内部類)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//那麼就插入一TreeNode節點
            else {//定位到這個hash桶了 但是這裡面是連結清單（沒有進行過樹化）
                for (int binCount = ; ; ++binCount) {//是連結清單
                    if ((e = p.next) == null) {
                    //如果p節點的next為空 直接在後面插入
                        p.next = newNode(hash, key, value, null);
    //這裡的樹化是putValue的時候 如果本來是連結清單 而且長度超過了8 那麼就進行樹化 
                        if (binCount >= TREEIFY_THRESHOLD - ) 
                    //** 這個方法一會來分析
                            treeifyBin(tab, hash);
                        break;
                }
//如果下一個節點e 不為null 并且這個連結清單中的節點就是你要找的節點 終止循環               
                    if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value; //将老的值複制給一個變量準備傳回
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;    //将新的值指派
                afterNodeAccess(e); //這個是空實作
                return oldValue;
            }
        }
            ++modCount;// 修改次數+1 和fastRemove()有關也和并發修改有關
        if (++size > threshold) //如果大于了阙值 需要擴容的大小
            resize();   //重新設定hash桶的大小，也有可能進行樹化，見後面代碼
        afterNodeInsertion(evict);//空方法
        return null;
    }
           

有三個方法需要跟進去看看

1. resize()

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table; // oldTable:目前的表
        int oldCap = (oldTab == null) ?  : oldTab.length;  //如果你是新建立的話 表的大小就是0 否則就是原來的大小
        //第一次是為0的    代表 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
        int oldThr = threshold;     
        int newCap, newThr = ; //新的容量和新的擴容
        //如果舊的容量大于0
        if (oldCap > ) {
        //如果舊的容量大于最大的容量
            if (oldCap >= MAXIMUM_CAPACITY) {   
            //那麼擴容大小 = 最大範圍
                threshold = Integer.MAX_VALUE;  
            //直接傳回了
                return oldTab;  
            }
        //否則 如果新的大小等于 oldCap * 2 < 最大的容量 ， 并且舊的容量大于預設的初始化大小16
            else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
     // double threshold  新的擴容 = 舊的擴容 * 2 
                newThr = oldThr << ;
        }
        else if (oldThr > ) // initial capacity was placed in threshold 
            newCap = oldThr;    //如果舊的擴容本來就大于0，那麼新的容量就是舊的擴容
        else {               // zero initial threshold signifies using defaults 說明是 threshold為0的時候的情況
            newCap = DEFAULT_INITIAL_CAPACITY;      //新的容量為預設容器的容量
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //新的阙值為 預設的容量 * 負載因子
        }   
        if (newThr == ) {  //如果新的擴容為0 
            float ft = (float)newCap * loadFactor;  //計算得到新的阙值
        //新的阙值 =  如果新的容量小于 最大的容量 并且 新的阙隻 < 最大的容量 那麼新的阙值 = 計算的 否則 = 最大int
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr; //阙值 = 新的阙值
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//建立一個新的哈希數組桶 大小為新的容量    
        table = newTab; // 
        if (oldTab != null) {
    //周遊舊的hash桶
        for (int j = ; j < oldCap; ++j) {  
                Node<K,V> e;    
                if ((e = oldTab[j]) != null) {//如果舊的hash桶的元素不為null  e為舊的hash桶的元素
                    oldTab[j] = null;   //舊的hash桶設定為null
                    if (e.next == null)     //如果你就是一個元素
                        newTab[e.hash & (newCap - )] = e;  //那麼在新的hash桶給你安排一個位置  位置是你的hash值 & 新的桶的容量-1 這相當于 你的hash值 與 你的容量進行取模運算
                    else if (e instanceof TreeNode) //如果你不隻一個元素并且是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;
                            if ((e.hash & oldCap) == ) {   //看是否需要進行位置變化 新增位的值 不需要變化就放在原來的位置
                                if (loTail == null)
                                    loHead = e; 
                                else
                                    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;
                            newTab[j + oldCap] = hiHead;//在新連結清單的位置指派
                        }
                    }
                }
            }
        }
        return newTab;
    }
           

2.final void split(HashMap< K,V > map, Node< K,V >[] tab, int index, int bit)

上述方法在resize()過程中被調用

//被調用的代碼 split(目前hash表，新的哈希桶，要分割的元素的小标，舊的容量)

((TreeNode

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this; //這裡的this :    e = oldTab[j] 上下文中的代碼
            // Relink into lo and hi lists, preserving order
            TreeNode<K,V> loHead = null, loTail = null; //低位的頭和低位的尾
            TreeNode<K,V> hiHead = null, hiTail = null; //高位的頭和高位的尾
            int lc = , hc = ; //地位和高位的2個計數器
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                next = (TreeNode<K,V>)e.next;   //擷取下一個節點
                e.next = null;  //設定為null
                if ((e.hash & bit) == ) {  //如果 e.hash 與 原來舊的容量 & 為 0 說明不需要進行移動位置      (e.hash & (bit-1) ) <==> e.hash % bit , e.hash & bit 計算的就是新增出來的那一位 如果結果為0 說明不需要進行位移
                    if ((e.prev = loTail) == null)  //如果低位的尾巴為null
                        loHead = e;     //将e 複制給頭
                    else
                        loTail.next = e;    //如果尾巴不為null 尾巴的next 為 e
                    loTail = e;     //将e 作為新的尾巴
                    ++lc;   //次數 + 1 
                }
                else {
                    if ((e.prev = hiTail) == null)  //否則需要移動位置  
                        hiHead = e;     //高位的連結清單和低位一樣
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }

            if (loHead != null) {   //如果有連結清單
                if (lc <= UNTREEIFY_THRESHOLD)  //如果長度 <= 6  
                    tab[index] = loHead.untreeify(map);//取消樹化 将這個樹裡面的連結清單結構變成普通的連結清單結構
                else {
                    tab[index] = loHead;    //否則将地位複制給原來的下标
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);    //進行樹化
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)  hc < = ;取消樹化
                    tab[index + bit] = hiHead.untreeify(map);//進行了移位 位置偏移 下标 + 原來的容器大小
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }
           

這裡面設計到2個方法在resize中 如果連結清單的長度 <= UNTREEIFY_THRESHOLD

就進行非樹化，否則就進行樹化。這裡的非樹化就是将TreeNode轉換成Node

final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            for (Node<K,V> q = this; q != null; q = q.next) {
   //将q轉換成普通的Nod return new Node<>(p.hash, p.key, p.value, next);
                Node<K,V> p = map.replacementNode(q, null);
                if (tl == null) 
                    hd = p; //頭為p
                else
                    tl.next = p;    
                tl = p;     
            }
            return hd;//傳回這個連結清單
        }
           

樹化為相反的過程

/**
     * Forms tree of the nodes linked from this node.
     * @return root of tree
     */
           

下面的這個方法也在hashMap中的putVal方法中的 treeifyBin(tab, hash);被調用

如果當時插入元素在hash桶為普通連結清單的情況下并且連結清單的長度大于8 就進行樹化

final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
    //初始化x 就是這個節點
        for (TreeNode<K,V> x = this, next; x != null; x = next) {   
                next = (TreeNode<K,V>)x.next; //擷取x的下一個節點
                x.left = x.right = null;    //設定x的左右為null
                if (root == null) {
                    x.parent = null;    
                    x.red = false;  //根節點為黑色
                    root = x;   //根節點為x 
                }
                else {  //根節點不為null
                    K k = x.key;    //  擷取K key
                    int h = x.hash; //擷取hash
                    Class<?> kc = null; //擷取資料的類型
                    //開始循環建構 将根節點複制給p
            for (TreeNode<K,V> p = root;;) {
            int dir, ph; //ph 目前節點的hash值
                    // dir 判斷左右用的
                        K pk = p.key;
                        if ((ph = p.hash) > h) 
                            dir = -;
                        else if (ph < h)
                            dir = ;
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == )
                            dir = tieBreakOrder(k, pk); //當 hashCode相等 并且沒有比較器的時候 進行另外的一種方式比較 可以看一下源碼

                        TreeNode<K,V> xp = p; 
                        if ((p = (dir <= ) ? p.left : p.right) == null) {  //如果p節點的左兒子或者右兒子為null 那麼就開始建立 否則就繼續往下面找
            //通過大小比較 判斷 如果新的p（原來p的子節點） 為null
                            x.parent = xp;  //x.parent就是目前的p 
                            if (dir <= )   
                                xp.left = x; 
                            else
                                xp.right = x;
                            root = balanceInsertion(root, x);//紅黑樹的插入 把新的節點插入到目前樹中 新的節點的parent就是你目前周遊的節點 而且目前周遊的節點的左兒子/右兒子已經确定
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }

    //紅黑樹的插入
     static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            x.red = true;   //将要插入的節點設定為紅色
        //修正樹
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
       // xp 為 要插入節點的爸爸
       // xpp 為要插入節點的爺爺
       // xppl 要插入節點的爺爺的左孩子
       // xppr 要插入節點的爺爺的右孩子 
                if ((xp = x.parent) == null) {  //如果他的爸爸為null
                    x.red = false;      //就将他設定為黑色 
                    return x;   //直接傳回  根節點
                }
                else if (!xp.red || (xpp = xp.parent) == null)  //如果 爸爸是黑色 不影響紅黑樹的性質  //或者他是紅色 并且他的爺爺為空 說明他爸爸就是根  也直接傳回 符合性質 黑色下面是2個紅色
                    return root;    //那麼直接傳回root

                if (xp == (xppl = xpp.left)) {  //如果爸爸(紅色) 是爺爺的左兒子

                    if ((xppr = xpp.right) != null && xppr.red) {  //叔叔節點不為空并且是紅色
                        xppr.red = false;   //叔叔變成黑色
                        xp.red = false;     //爸爸變成黑色
                        xpp.red = true;     //爺爺變成紅色
                        x = xpp;        //目前節點指向爺爺節點
                    }
                    else {  //叔叔為null 或者 叔叔為黑色（若存在）
                        if (x == xp.right) {    //如果你是爸爸的右孩子 并且叔叔是黑色
                            root = rotateLeft(root, x = xp);    //将父節點作為目前節點    //新的目前節點進行左旋
                            xpp = (xp = x.parent) == null ? null : xp.parent;       // xp 為旋轉後的目前節點的父親
                                            // xpp 如果xp都為空了 那麼xpp 也為空 否則 xpp = xp.parent
                        }
                        if (xp != null) {
                            xp.red = false; //将父節點設定為黑色
                            if (xpp != null) {
                                xpp.red = true; //将祖父節點設定為紅色
                                root = rotateRight(root, xpp);  //對祖父節點進行右旋
                            }
                        }
                    }
                }
                else {  //這裡為父親為右孩子的情況與左邊類似 不在複述
                    if (xppl != null && xppl.red) { 
                        xppl.red = false;   
                        xp.red = false;     
                        xpp.red = true;     
                        x = xpp;        
                    }
                    else {
                        if (x == xp.left) { 
                            root = rotateRight(root, x = xp);   //對你爸爸進行右旋
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }
           

3. moveRootToFront(tab, root);

static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
        int n;
        if (root != null && tab != null && (n = tab.length) > 0) {//如果根存在
            int index = (n - 1) & root.hash;    //擷取根在的hash桶的下标
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index];    //擷取對應的節點
            if (root != first) {    //如果根不是第一個
                Node<K,V> rn;   // rootnext
                tab[index] = root;  //将根設定為第一個
                TreeNode<K,V> rp = root.prev;   //rootprev 根的前面一個
                if ((rn = root.next) != null)   //如果根的next 不為null
                    ((TreeNode<K,V>)rn).prev = rp;  // root.next的prev = root.prev
                if (rp != null) //如果root.prev不為null
                    rp.next = rn;   //root.prev的下一個 = root.next
                if (first != null)   //如果first第一個不為null
                    first.prev = root;  第一個的前面為root
                root.next = first;  //跟的後面為原來的第一個
        root.prev = null; //根的前面為null
            }
            assert checkInvariants(root);
        }
    }