歡迎光臨
每天分享高質量文章

Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析(下)

(點選上方公眾號,可快速關註)


來源:JavaDoop,

javadoop.com/post/hashmap

Java8 HashMap

Java8 對 HashMap 進行了一些修改,最大的不同就是利用了紅黑樹,所以其由 陣列+連結串列+紅黑樹 組成。

根據 Java7 HashMap 的介紹,我們知道,查詢的時候,根據 hash 值我們能夠快速定位到陣列的具體下標,但是之後的話,需要順著連結串列一個個比較下去才能找到我們需要的,時間複雜度取決於連結串列的長度,為 O(n)。

為了降低這部分的開銷,在 Java8 中,當連結串列中的元素超過了 8 個以後,會將連結串列轉換為紅黑樹,在這些位置進行查詢的時候可以降低時間複雜度為 O(logN)。

來一張圖簡單示意一下吧:

註意,上圖是示意圖,主要是描述結構,不會達到這個狀態的,因為這麼多資料的時候早就擴容了。

下麵,我們還是用程式碼來介紹吧,個人感覺,Java8 的原始碼可讀性要差一些,不過精簡一些。

Java7 中使用 Entry 來代表每個 HashMap 中的資料節點,Java8 中使用 Node,基本沒有區別,都是 key,value,hash 和 next 這四個屬性,不過,Node 只能用於連結串列的情況,紅黑樹的情況需要使用 TreeNode。

我們根據陣列元素中,第一個節點資料型別是 Node 還是 TreeNode 來判斷該位置下是連結串列還是紅黑樹的。

put 過程分析

public V put(K key, V value) {

    return putVal(hash(key), key, value, false, true);

}

 

// 第三個引數 onlyIfAbsent 如果是 true,那麼只有在不存在該 key 時才會進行 put 操作

// 第四個引數 evict 我們這裡不關心

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

               boolean evict) {

    Node[] tab; Node p; int n, i;

    // 第一次 put 值的時候,會觸發下麵的 resize(),類似 java7 的第一次 put 也要初始化陣列長度

    // 第一次 resize 和後續的擴容有些不一樣,因為這次是陣列從 null 初始化到預設的 16 或自定義的初始容量

    if ((tab = table) == null || (n = tab.length) == 0)

        n = (tab = resize()).length;

    // 找到具體的陣列下標,如果此位置沒有值,那麼直接初始化一下 Node 並放置在這個位置就可以了

    if ((p = tab[i = (n – 1) & hash]) == null)

        tab[i] = newNode(hash, key, value, null);

 

    else {// 陣列該位置有資料

        Node e; K k;

        // 首先,判斷該位置的第一個資料和我們要插入的資料,key 是不是”相等”,如果是,取出這個節點

        if (p.hash == hash &&

            ((k = p.key) == key || (key != null && key.equals(k))))

            e = p;

        // 如果該節點是代表紅黑樹的節點,呼叫紅黑樹的插值方法,本文不展開說紅黑樹

        else if (p instanceof TreeNode)

            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

        else {

            // 到這裡,說明陣列該位置上是一個連結串列

            for (int binCount = 0; ; ++binCount) {

                // 插入到連結串列的最後面(Java7 是插入到連結串列的最前面)

                if ((e = p.next) == null) {

                    p.next = newNode(hash, key, value, null);

                    // TREEIFY_THRESHOLD 為 8,所以,如果新插入的值是連結串列中的第 9 個

                    // 會觸發下麵的 treeifyBin,也就是將連結串列轉換為紅黑樹

                    if (binCount >= TREEIFY_THRESHOLD – 1) // -1 for 1st

                        treeifyBin(tab, hash);

                    break;

                }

                // 如果在該連結串列中找到了”相等”的 key(== 或 equals)

                if (e.hash == hash &&

                    ((k = e.key) == key || (key != null && key.equals(k))))

                    // 此時 break,那麼 e 為連結串列中[與要插入的新值的 key “相等”]的 node

                    break;

                p = e;

            }

        }

        // e!=null 說明存在舊值的key與要插入的key”相等”

        // 對於我們分析的put操作,下麵這個 if 其實就是進行 “值改寫”,然後傳回舊值

        if (e != null) {

            V oldValue = e.value;

            if (!onlyIfAbsent || oldValue == null)

                e.value = value;

            afterNodeAccess(e);

            return oldValue;

        }

    }

    ++modCount;

    // 如果 HashMap 由於新插入這個值導致 size 已經超過了閾值,需要進行擴容

    if (++size > threshold)

        resize();

    afterNodeInsertion(evict);

    return null;

}

和 Java7 稍微有點不一樣的地方就是,Java7 是先擴容後插入新值的,Java8 先插值再擴容,不過這個不重要。

陣列擴容

resize() 方法用於初始化陣列或陣列擴容,每次擴容後,容量為原來的 2 倍,併進行資料遷移。

final Node[] resize() {

    Node[] oldTab = table;

    int oldCap = (oldTab == null) ? 0 : oldTab.length;

    int oldThr = threshold;

    int newCap, newThr = 0;

    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

    }

    else if (oldThr > 0) // 對應使用 new HashMap(int initialCapacity) 初始化後,第一次 put 的時候

        newCap = oldThr;

    else {// 對應使用 new HashMap() 初始化後,第一次 put 的時候

        newCap = DEFAULT_INITIAL_CAPACITY;

        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

    }

 

    if (newThr == 0) {

        float ft = (float)newCap * loadFactor;

        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

                  (int)ft : Integer.MAX_VALUE);

    }

    threshold = newThr;

 

    // 用新的陣列大小初始化新的陣列

    Node[] newTab = (Node[])new Node[newCap];

    table = newTab; // 如果是初始化陣列,到這裡就結束了,傳回 newTab 即可

 

    if (oldTab != null) {

        // 開始遍歷原陣列,進行資料遷移。

        for (int j = 0; j < oldCap; ++j) {

            Node e;

            if ((e = oldTab[j]) != null) {

                oldTab[j] = null;

                // 如果該陣列位置上只有單個元素,那就簡單了,簡單遷移這個元素就可以了

                if (e.next == null)

                    newTab[e.hash & (newCap – 1)] = e;

                // 如果是紅黑樹,具體我們就不展開了

                else if (e instanceof TreeNode)

                    ((TreeNode)e).split(this, newTab, j, oldCap);

                else { 

                    // 這塊是處理連結串列的情況,

                    // 需要將此連結串列拆成兩個連結串列,放到新的陣列中,並且保留原來的先後順序

                    // loHead、loTail 對應一條連結串列,hiHead、hiTail 對應另一條連結串列,程式碼還是比較簡單的

                    Node loHead = null, loTail = null;

                    Node hiHead = null, hiTail = null;

                    Node next;

                    do {

                        next = e.next;

                        if ((e.hash & oldCap) == 0) {

                            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;

                        // 第二條連結串列的新的位置是 j + oldCap,這個很好理解

                        newTab[j + oldCap] = hiHead;

                    }

                }

            }

        }

    }

    return newTab;

}

get 過程分析

相對於 put 來說,get 真的太簡單了。

  1. 計算 key 的 hash 值,根據 hash 值找到對應陣列下標: hash & (length-1)

  2. 判斷陣列該位置處的元素是否剛好就是我們要找的,如果不是,走第三步

  3. 判斷該元素型別是否是 TreeNode,如果是,用紅黑樹的方法取資料,如果不是,走第四步

  4. 遍歷連結串列,直到找到相等(==或equals)的 key

public V get(Object key) {

    Node e;

    return (e = getNode(hash(key), key)) == null ? null : e.value;

}

final Node getNode(int hash, Object key) {

    Node[] tab; Node first, e; int n; K k;

    if ((tab = table) != null && (n = tab.length) > 0 &&

        (first = tab[(n – 1) & hash]) != null) {

        // 判斷第一個節點是不是就是需要的

        if (first.hash == hash && // always check first node

            ((k = first.key) == key || (key != null && key.equals(k))))

            return first;

        if ((e = first.next) != null) {

            // 判斷是否是紅黑樹

            if (first instanceof TreeNode)

                return ((TreeNode)first).getTreeNode(hash, key);

 

            // 連結串列遍歷

            do {

                if (e.hash == hash &&

                    ((k = e.key) == key || (key != null && key.equals(k))))

                    return e;

            } while ((e = e.next) != null);

        }

    }

    return null;

}

Java8 ConcurrentHashMap

Java7 中實現的 ConcurrentHashMap 說實話還是比較複雜的,Java8 對 ConcurrentHashMap 進行了比較大的改動。建議讀者可以參考 Java8 中 HashMap 相對於 Java7 HashMap 的改動,對於 ConcurrentHashMap,Java8 也引入了紅黑樹。

說實話,Java8 ConcurrentHashMap 原始碼真心不簡單,最難的在於擴容,資料遷移操作不容易看懂。

我們先用一個示意圖來描述下其結構:

結構上和 Java8 的 HashMap 基本上一樣,不過它要保證執行緒安全性,所以在原始碼上確實要複雜一些。

初始化

// 這建構式裡,什麼都不乾

public ConcurrentHashMap() {

}

public ConcurrentHashMap(int initialCapacity) {

    if (initialCapacity < 0)

        throw new IllegalArgumentException();

    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?

               MAXIMUM_CAPACITY :

               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));

    this.sizeCtl = cap;

}

這個初始化方法有點意思,透過提供初始容量,計算了 sizeCtl,sizeCtl = 【 (1.5 * initialCapacity + 1),然後向上取最近的 2 的 n 次方】。如 initialCapacity 為 10,那麼得到 sizeCtl 為 16,如果 initialCapacity 為 11,得到 sizeCtl 為 32。

sizeCtl 這個屬性使用的場景很多,不過只要跟著文章的思路來,就不會被它搞暈了。

如果你愛折騰,也可以看下另一個有三個引數的構造方法,這裡我就不說了,大部分時候,我們會使用無參建構式進行實體化,我們也按照這個思路來進行原始碼分析吧。

put 過程分析

仔細地一行一行程式碼看下去:

public V put(K key, V value) {

    return putVal(key, value, false);

}

final V putVal(K key, V value, boolean onlyIfAbsent) {

    if (key == null || value == null) throw new NullPointerException();

    // 得到 hash 值

    int hash = spread(key.hashCode());

    // 用於記錄相應連結串列的長度

    int binCount = 0;

    for (Node[] tab = table;;) {

        Node f; int n, i, fh;

        // 如果陣列”空”,進行陣列初始化

        if (tab == null || (n = tab.length) == 0)

            // 初始化陣列,後面會詳細介紹

            tab = initTable();

 

        // 找該 hash 值對應的陣列下標,得到第一個節點 f

        else if ((f = tabAt(tab, i = (n – 1) & hash)) == null) {

            // 如果陣列該位置為空,

            //    用一次 CAS 操作將這個新值放入其中即可,這個 put 操作差不多就結束了,可以拉到最後面了

            //          如果 CAS 失敗,那就是有併發操作,進到下一個迴圈就好了

            if (casTabAt(tab, i, null,

                         new Node(hash, key, value, null)))

                break;                   // no lock when adding to empty bin

        }

        // hash 居然可以等於 MOVED,這個需要到後面才能看明白,不過從名字上也能猜到,肯定是因為在擴容

        else if ((fh = f.hash) == MOVED)

            // 幫助資料遷移,這個等到看完資料遷移部分的介紹後,再理解這個就很簡單了

            tab = helpTransfer(tab, f);

 

        else { // 到這裡就是說,f 是該位置的頭結點,而且不為空

 

            V oldVal = null;

            // 獲取陣列該位置的頭結點的監視器鎖

            synchronized (f) {

                if (tabAt(tab, i) == f) {

                    if (fh >= 0) { // 頭結點的 hash 值大於 0,說明是連結串列

                        // 用於累加,記錄連結串列的長度

                        binCount = 1;

                        // 遍歷連結串列

                        for (Node e = f;; ++binCount) {

                            K ek;

                            // 如果發現了”相等”的 key,判斷是否要進行值改寫,然後也就可以 break 了

                            if (e.hash == hash &&

                                ((ek = e.key) == key ||

                                 (ek != null && key.equals(ek)))) {

                                oldVal = e.val;

                                if (!onlyIfAbsent)

                                    e.val = value;

                                break;

                            }

                            // 到了連結串列的最末端,將這個新值放到連結串列的最後面

                            Node pred = e;

                            if ((e = e.next) == null) {

                                pred.next = new Node(hash, key,

                                                          value, null);

                                break;

                            }

                        }

                    }

                    else if (f instanceof TreeBin) { // 紅黑樹

                        Node p;

                        binCount = 2;

                        // 呼叫紅黑樹的插值方法插入新節點

                        if ((p = ((TreeBin)f).putTreeVal(hash, key,

                                                       value)) != null) {

                            oldVal = p.val;

                            if (!onlyIfAbsent)

                                p.val = value;

                        }

                    }

                }

            }

            // binCount != 0 說明上面在做連結串列操作

            if (binCount != 0) {

                // 判斷是否要將連結串列轉換為紅黑樹,臨界值和 HashMap 一樣,也是 8

                if (binCount >= TREEIFY_THRESHOLD)

                    // 這個方法和 HashMap 中稍微有一點點不同,那就是它不是一定會進行紅黑樹轉換,

                    // 如果當前陣列的長度小於 64,那麼會選擇進行陣列擴容,而不是轉換為紅黑樹

                    //    具體原始碼我們就不看了,擴容部分後面說

                    treeifyBin(tab, i);

                if (oldVal != null)

                    return oldVal;

                break;

            }

        }

    }

    // 

    addCount(1L, binCount);

    return null;

}

put 的主流程看完了,但是至少留下了幾個問題,第一個是初始化,第二個是擴容,第三個是幫助資料遷移,這些我們都會在後面進行一一介紹。

初始化陣列:initTable

這個比較簡單,主要就是初始化一個合適大小的陣列,然後會設定 sizeCtl。

初始化方法中的併發問題是透過對 sizeCtl 進行一個 CAS 操作來控制的。

private final Node[] initTable() {

    Node[] tab; int sc;

    while ((tab = table) == null || tab.length == 0) {

        // 初始化的”功勞”被其他執行緒”搶去”了

        if ((sc = sizeCtl) < 0)

            Thread.yield(); // lost initialization race; just spin

        // CAS 一下,將 sizeCtl 設定為 -1,代表搶到了鎖

        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {

            try {

                if ((tab = table) == null || tab.length == 0) {

                    // DEFAULT_CAPACITY 預設初始容量是 16

                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;

                    // 初始化陣列,長度為 16 或初始化時提供的長度

                    Node[] nt = (Node[])new Node,?>[n];

                    // 將這個陣列賦值給 table,table 是 volatile 的

                    table = tab = nt;

                    // 如果 n 為 16 的話,那麼這裡 sc = 12

                    // 其實就是 0.75 * n

                    sc = n – (n >>> 2);

                }

            } finally {

                // 設定 sizeCtl 為 sc,我們就當是 12 吧

                sizeCtl = sc;

            }

            break;

        }

    }

    return tab;

}

連結串列轉紅黑樹: treeifyBin

前面我們在 put 原始碼分析也說過,treeifyBin 不一定就會進行紅黑樹轉換,也可能是僅僅做陣列擴容。我們還是進行原始碼分析吧。

private final void treeifyBin(Node[] tab, int index) {

    Node b; int n, sc;

    if (tab != null) {

        // MIN_TREEIFY_CAPACITY 為 64

        // 所以,如果陣列長度小於 64 的時候,其實也就是 32 或者 16 或者更小的時候,會進行陣列擴容

        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)

            // 後面我們再詳細分析這個方法

            tryPresize(n << 1);

        // b 是頭結點

        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {

            // 加鎖

            synchronized (b) {

 

                if (tabAt(tab, index) == b) {

                    // 下麵就是遍歷連結串列,建立一顆紅黑樹

                    TreeNode hd = null, tl = null;

                    for (Node e = b; e != null; e = e.next) {

                        TreeNode p =

                            new TreeNode(e.hash, e.key, e.val,

                                              null, null);

                        if ((p.prev = tl) == null)

                            hd = p;

                        else

                            tl.next = p;

                        tl = p;

                    }

                    // 將紅黑樹設定到陣列相應位置中

                    setTabAt(tab, index, new TreeBin(hd));

                }

            }

        }

    }

}

擴容:tryPresize

如果說 Java8 ConcurrentHashMap 的原始碼不簡單,那麼說的就是擴容操作和遷移操作。

這個方法要完完全全看懂還需要看之後的 transfer 方法,讀者應該提前知道這點。

這裡的擴容也是做翻倍擴容的,擴容後陣列容量為原來的 2 倍。

// 首先要說明的是,方法引數 size 傳進來的時候就已經翻了倍了

private final void tryPresize(int size) {

    // c:size 的 1.5 倍,再加 1,再往上取最近的 2 的 n 次方。

    int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :

        tableSizeFor(size + (size >>> 1) + 1);

    int sc;

    while ((sc = sizeCtl) >= 0) {

        Node[] tab = table; int n;

 

        // 這個 if 分支和之前說的初始化陣列的程式碼基本上是一樣的,在這裡,我們可以不用管這塊程式碼

        if (tab == null || (n = tab.length) == 0) {

            n = (sc > c) ? sc : c;

            if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {

                try {

                    if (table == tab) {

                        @SuppressWarnings(“unchecked”)

                        Node[] nt = (Node[])new Node,?>[n];

                        table = nt;

                        sc = n – (n >>> 2); // 0.75 * n

                    }

                } finally {

                    sizeCtl = sc;

                }

            }

        }

        else if (c <= sc || n >= MAXIMUM_CAPACITY)

            break;

        else if (tab == table) {

            // 我沒看懂 rs 的真正含義是什麼,不過也關係不大

            int rs = resizeStamp(n);

 

            if (sc < 0) {

                Node[] nt;

                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||

                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||

                    transferIndex <= 0)

                    break;

                // 2. 用 CAS 將 sizeCtl 加 1,然後執行 transfer 方法

                //    此時 nextTab 不為 null

                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))

                    transfer(tab, nt);

            }

            // 1. 將 sizeCtl 設定為 (rs << RESIZE_STAMP_SHIFT) + 2)

            //     我是沒看懂這個值真正的意義是什麼?不過可以計算出來的是,結果是一個比較大的負數

            //  呼叫 transfer 方法,此時 nextTab 引數為 null

            else if (U.compareAndSwapInt(this, SIZECTL, sc,

                                         (rs << RESIZE_STAMP_SHIFT) + 2))

                transfer(tab, null);

        }

    }

}

這個方法的核心在於 sizeCtl 值的操作,首先將其設定為一個負數,然後執行 transfer(tab, null),再下一個迴圈將 sizeCtl 加 1,並執行 transfer(tab, nt),之後可能是繼續 sizeCtl 加 1,並執行 transfer(tab, nt)。

所以,可能的操作就是執行 1 次 transfer(tab, null) + 多次 transfer(tab, nt),這裡怎麼結束迴圈的需要看完 transfer 原始碼才清楚。

資料遷移:transfer

下麵這個方法很點長,將原來的 tab 陣列的元素遷移到新的 nextTab 陣列中。

雖然我們之前說的 tryPresize 方法中多次呼叫 transfer 不涉及多執行緒,但是這個 transfer 方法可以在其他地方被呼叫,典型地,我們之前在說 put 方法的時候就說過了,請往上看 put 方法,是不是有個地方呼叫了 helpTransfer 方法,helpTransfer 方法會呼叫 transfer 方法的。

此方法支援多執行緒執行,外圍呼叫此方法的時候,會保證第一個發起資料遷移的執行緒,nextTab 引數為 null,之後再呼叫此方法的時候,nextTab 不會為 null。

閱讀原始碼之前,先要理解併發操作的機制。原陣列長度為 n,所以我們有 n 個遷移任務,讓每個執行緒每次負責一個小任務是最簡單的,每做完一個任務再檢測是否有其他沒做完的任務,幫助遷移就可以了,而 Doug Lea 使用了一個 stride,簡單理解就是步長,每個執行緒每次負責遷移其中的一部分,如每次遷移 16 個小任務。所以,我們就需要一個全域性的排程者來安排哪個執行緒執行哪幾個任務,這個就是屬性 transferIndex 的作用。

第一個發起資料遷移的執行緒會將 transferIndex 指向原陣列最後的位置,然後從後往前的 stride 個任務屬於第一個執行緒,然後將 transferIndex 指向新的位置,再往前的 stride 個任務屬於第二個執行緒,依此類推。當然,這裡說的第二個執行緒不是真的一定指代了第二個執行緒,也可以是同一個執行緒,這個讀者應該能理解吧。其實就是將一個大的遷移任務分為了一個個任務包。

private final void transfer(Node[] tab, Node[] nextTab) {

    int n = tab.length, stride;

 

    // stride 在單核下直接等於 n,多核樣式下為 (n>>>3)/NCPU,最小值是 16

    // stride 可以理解為”步長“,有 n 個位置是需要進行遷移的,

    //   將這 n 個任務分為多個任務包,每個任務包有 stride 個任務

    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)

        stride = MIN_TRANSFER_STRIDE; // subdivide range

 

    // 如果 nextTab 為 null,先進行一次初始化

    //    前面我們說了,外圍會保證第一個發起遷移的執行緒呼叫此方法時,引數 nextTab 為 null

    //       之後參與遷移的執行緒呼叫此方法時,nextTab 不會為 null

    if (nextTab == null) {

        try {

            // 容量翻倍

            Node[] nt = (Node[])new Node,?>[n << 1];

            nextTab = nt;

        } catch (Throwable ex) {      // try to cope with OOME

            sizeCtl = Integer.MAX_VALUE;

            return;

        }

        // nextTable 是 ConcurrentHashMap 中的屬性

        nextTable = nextTab;

        // transferIndex 也是 ConcurrentHashMap 的屬性,用於控制遷移的位置

        transferIndex = n;

    }

 

    int nextn = nextTab.length;

 

    // ForwardingNode 翻譯過來就是正在被遷移的 Node

    // 這個構造方法會生成一個Node,key、value 和 next 都為 null,關鍵是 hash 為 MOVED

    // 後面我們會看到,原陣列中位置 i 處的節點完成遷移工作後,

    //    就會將位置 i 處設定為這個 ForwardingNode,用來告訴其他執行緒該位置已經處理過了

    //    所以它其實相當於是一個標誌。

    ForwardingNode fwd = new ForwardingNode(nextTab);

 

 

    // advance 指的是做完了一個位置的遷移工作,可以準備做下一個位置的了

    boolean advance = true;

    boolean finishing = false; // to ensure sweep before committing nextTab

 

    /*

     * 下麵這個 for 迴圈,最難理解的在前面,而要看懂它們,應該先看懂後面的,然後再倒回來看

     * 

     */

 

    // i 是位置索引,bound 是邊界,註意是從後往前

    for (int i = 0, bound = 0;;) {

        Node f; int fh;

 

        // 下麵這個 while 真的是不好理解

        // advance 為 true 表示可以進行下一個位置的遷移了

        //   簡單理解結局:i 指向了 transferIndex,bound 指向了 transferIndex-stride

        while (advance) {

            int nextIndex, nextBound;

            if (–i >= bound || finishing)

                advance = false;

 

            // 將 transferIndex 值賦給 nextIndex

            // 這裡 transferIndex 一旦小於等於 0,說明原陣列的所有位置都有相應的執行緒去處理了

            else if ((nextIndex = transferIndex) <= 0) {

                i = -1;

                advance = false;

            }

            else if (U.compareAndSwapInt

                     (this, TRANSFERINDEX, nextIndex,

                      nextBound = (nextIndex > stride ?

                                   nextIndex – stride : 0))) {

                // 看括號中的程式碼,nextBound 是這次遷移任務的邊界,註意,是從後往前

                bound = nextBound;

                i = nextIndex – 1;

                advance = false;

            }

        }

        if (i < 0 || i >= n || i + n >= nextn) {

            int sc;

            if (finishing) {

                // 所有的遷移操作已經完成

                nextTable = null;

                // 將新的 nextTab 賦值給 table 屬性,完成遷移

                table = nextTab;

                // 重新計算 sizeCtl:n 是原陣列長度,所以 sizeCtl 得出的值將是新陣列長度的 0.75 倍

                sizeCtl = (n << 1) - (n >>> 1);

                return;

            }

 

            // 之前我們說過,sizeCtl 在遷移前會設定為 (rs << RESIZE_STAMP_SHIFT) + 2

            // 然後,每有一個執行緒參與遷移就會將 sizeCtl 加 1,

            // 這裡使用 CAS 操作對 sizeCtl 進行減 1,代表做完了屬於自己的任務

            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc – 1)) {

                // 任務結束,方法退出

                if ((sc – 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)

                    return;

 

                // 到這裡,說明 (sc – 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT,

                // 也就是說,所有的遷移任務都做完了,也就會進入到上面的 if(finishing){} 分支了

                finishing = advance = true;

                i = n; // recheck before commit

            }

        }

        // 如果位置 i 處是空的,沒有任何節點,那麼放入剛剛初始化的 ForwardingNode ”空節點“

        else if ((f = tabAt(tab, i)) == null)

            advance = casTabAt(tab, i, null, fwd);

        // 該位置處是一個 ForwardingNode,代表該位置已經遷移過了

        else if ((fh = f.hash) == MOVED)

            advance = true; // already processed

        else {

            // 對陣列該位置處的結點加鎖,開始處理陣列該位置處的遷移工作

            synchronized (f) {

                if (tabAt(tab, i) == f) {

                    Node ln, hn;

                    // 頭結點的 hash 大於 0,說明是連結串列的 Node 節點

                    if (fh >= 0) {

                        // 下麵這一塊和 Java7 中的 ConcurrentHashMap 遷移是差不多的,

                        // 需要將連結串列一分為二,

                        //   找到原連結串列中的 lastRun,然後 lastRun 及其之後的節點是一起進行遷移的

                        //   lastRun 之前的節點需要進行克隆,然後分到兩個連結串列中

                        int runBit = fh & n;

                        Node lastRun = f;

                        for (Node p = f.next; p != null; p = p.next) {

                            int b = p.hash & n;

                            if (b != runBit) {

                                runBit = b;

                                lastRun = p;

                            }

                        }

                        if (runBit == 0) {

                            ln = lastRun;

                            hn = null;

                        }

                        else {

                            hn = lastRun;

                            ln = null;

                        }

                        for (Node p = f; p != lastRun; p = p.next) {

                            int ph = p.hash; K pk = p.key; V pv = p.val;

                            if ((ph & n) == 0)

                                ln = new Node(ph, pk, pv, ln);

                            else

                                hn = new Node(ph, pk, pv, hn);

                        }

                        // 其中的一個連結串列放在新陣列的位置 i

                        setTabAt(nextTab, i, ln);

                        // 另一個連結串列放在新陣列的位置 i+n

                        setTabAt(nextTab, i + n, hn);

                        // 將原陣列該位置處設定為 fwd,代表該位置已經處理完畢,

                        //    其他執行緒一旦看到該位置的 hash 值為 MOVED,就不會進行遷移了

                        setTabAt(tab, i, fwd);

                        // advance 設定為 true,代表該位置已經遷移完畢

                        advance = true;

                    }

                    else if (f instanceof TreeBin) {

                        // 紅黑樹的遷移

                        TreeBin t = (TreeBin)f;

                        TreeNode lo = null, loTail = null;

                        TreeNode hi = null, hiTail = null;

                        int lc = 0, hc = 0;

                        for (Node e = t.first; e != null; e = e.next) {

                            int h = e.hash;

                            TreeNode p = new TreeNode

                                (h, e.key, e.val, null, null);

                            if ((h & n) == 0) {

                                if ((p.prev = loTail) == null)

                                    lo = p;

                                else

                                    loTail.next = p;

                                loTail = p;

                                ++lc;

                            }

                            else {

                                if ((p.prev = hiTail) == null)

                                    hi = p;

                                else

                                    hiTail.next = p;

                                hiTail = p;

                                ++hc;

                            }

                        }

                        // 如果一分為二後,節點數少於 8,那麼將紅黑樹轉換回連結串列

                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :

                            (hc != 0) ? new TreeBin(lo) : t;

                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :

                            (lc != 0) ? new TreeBin(hi) : t;

 

                        // 將 ln 放置在新陣列的位置 i

                        setTabAt(nextTab, i, ln);

                        // 將 hn 放置在新陣列的位置 i+n

                        setTabAt(nextTab, i + n, hn);

                        // 將原陣列該位置處設定為 fwd,代表該位置已經處理完畢,

                        //    其他執行緒一旦看到該位置的 hash 值為 MOVED,就不會進行遷移了

                        setTabAt(tab, i, fwd);

                        // advance 設定為 true,代表該位置已經遷移完畢

                        advance = true;

                    }

                }

            }

        }

    }

}

說到底,transfer 這個方法並沒有實現所有的遷移任務,每次呼叫這個方法只實現了 transferIndex 往前 stride 個位置的遷移工作,其他的需要由外圍來控制。

這個時候,再回去仔細看 tryPresize 方法可能就會更加清晰一些了。

get 過程分析

get 方法從來都是最簡單的,這裡也不例外:

  1. 計算 hash 值

  2. 根據 hash 值找到陣列對應位置: (n – 1) & h

  3. 根據該位置處結點性質進行相應查詢

  • 如果該位置為 null,那麼直接傳回 null 就可以了

  • 如果該位置處的節點剛好就是我們需要的,傳回該節點的值即可

  • 如果該位置節點的 hash 值小於 0,說明正在擴容,或者是紅黑樹,後面我們再介紹 find 方法

如果以上 3 條都不滿足,那就是連結串列,進行遍歷比對即可

public V get(Object key) {

    Node[] tab; Node e, p; int n, eh; K ek;

    int h = spread(key.hashCode());

    if ((tab = table) != null && (n = tab.length) > 0 &&

        (e = tabAt(tab, (n – 1) & h)) != null) {

        // 判斷頭結點是否就是我們需要的節點

        if ((eh = e.hash) == h) {

            if ((ek = e.key) == key || (ek != null && key.equals(ek)))

                return e.val;

        }

        // 如果頭結點的 hash 小於 0,說明 正在擴容,或者該位置是紅黑樹

        else if (eh < 0)

            // 參考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k)

            return (p = e.find(h, key)) != null ? p.val : null;

 

        // 遍歷連結串列

        while ((e = e.next) != null) {

            if (e.hash == h &&

                ((ek = e.key) == key || (ek != null && key.equals(ek))))

                return e.val;

        }

    }

    return null;

}

簡單說一句,此方法的大部分內容都很簡單,只有正好碰到擴容的情況,ForwardingNode.find(int h, Object k) 稍微複雜一些,不過在瞭解了資料遷移的過程後,這個也就不難了,所以限於篇幅這裡也不展開說了。

總結

其實也不是很難嘛,雖然沒有像之前的 AQS 和執行緒池一樣一行一行原始碼進行分析,但還是把所有初學者可能會糊塗的地方都進行了深入的介紹,只要是稍微有點基礎的讀者,應該是很容易就能看懂 HashMap 和 ConcurrentHashMap 原始碼了。

看原始碼不算是目的吧,深入地瞭解 Doug Lea 的設計思路,我覺得還挺有趣的,大師就是大師,程式碼寫得真的是好啊。

看完本文有收穫?請轉發分享給更多人

關註「ImportNew」,提升Java技能

贊(0)

分享創造快樂