快捷導(dǎo)航

Java的LinkedHashSet源碼深入講解

更新時間：2023年09月04日 10:22:26 作者：Cyan_RA9

這篇文章主要介紹了Java的LinkedHashSet源碼深入講解,LinkedHashSet是HashSet的子類,而由于HashSet實現(xiàn)了Set接口,因此LinkedHashSet也間接實現(xiàn)了Set類,LinkedHashSet類屬于java.base模塊,java.util包下,需要的朋友可以參考下

一、前言

大家好，本篇博文是對集合篇章——單列集合Set的內(nèi)容補充。

Set集合常見的實現(xiàn)類有兩個——HashSet和TreeSet。

我們分析了HashSet的源碼，知道了HashSet的底層其實就是HashMap。

今天我們要解讀的是HashSet的一個子類——LinkedHashSet。

注意 :

①解讀源碼需要扎實的基礎(chǔ)，比較適合希望深究的同學(xué)；

②不要眼高手低，看會了不代表你會了，自己能全程Debug下來才算有收獲；

二、LinkedHashSet簡介

1.LinkedHashSet是HashSet的子類，而由于HashSet實現(xiàn)了Set接口，因此LinkedHashSet也間接實現(xiàn)了Set類。

LinkedHashSet類屬于java.base模塊，java.util包下，如下圖所示 :

我們再來看一下LinkedHashSet的類圖，如下 :

2.LinkedHashSet底層是一個LinkedHashMap，是"數(shù)組 + 雙向鏈表"的結(jié)構(gòu)。

3.LinkedHashSet也具有Set集合"不可重復(fù)"的特點。

但由于LinkedHashSet根據(jù)元素的hashCode值來決定元素的存儲位置，同時使用雙向鏈表來維護元素的次序，所以這就使得元素看起來是以插入順序保存的。

三、LinkedHashSet的底層實現(xiàn)

1.LinkedHashSet在底層維護了一個hash表（table）和雙向鏈表。（LinkedHashSet和LinkedList一樣也有head和tail）。

2.每個結(jié)點中維護了before，item，after三個屬性，其中通過before指向前一個結(jié)點，通過after指向后一個結(jié)點，從而實現(xiàn)雙向鏈表。

3.LinkedHashSet在添加元素時的底層規(guī)則和HashSet一樣，即先求該元素的hash值，根據(jù)特定算法求得該元素在hashtable中應(yīng)該存放的位置。如果該位置已經(jīng)有相同元素，放棄添加；反之則將該元素加入到雙向鏈表。

4.LinkedHashSet的底層其實就是LinkedHashMap，關(guān)于這一點，要類比HashSet的底層是HashMap。

5.LinkedHashSet的底層機制圖示 :

四、LinkedHashSet的源碼解讀（斷點調(diào)試）

準備工作

以LinkedHashSet_Demo類為演示類，代碼如下 : （main函數(shù)第一行設(shè)置斷點）

package csdn.knowledge.api_tools.gather.set;
import java.util.LinkedHashSet;
import java.util.Objects;
/**
 * @author : Cyan_RA9
 * @version : 21.0
 */
public class LinkedHashSet_Demo {
    public static void main(String[] args) {
        LinkedHashSet linkedHashSet = new LinkedHashSet();
        linkedHashSet.add(141);
        linkedHashSet.add(141);
        linkedHashSet.add("CSDN");
        linkedHashSet.add(11);
        linkedHashSet.add("Cyan");
        linkedHashSet.add(new Apple("紅富士"));
        linkedHashSet.add(new Apple("紅富士"));
    }
}
class Apple {
    private String name;
    public Apple(String name) {
        this.name = name;
    }
    @Override
    public int hashCode() {
        return 100;
    }
}

向集合中添加第一個元素

①跳入無參構(gòu)造。

首先我們跳入LinkedHashSet的無參構(gòu)造，如下圖所示 :

底層調(diào)用了其父類HashSet 的一個帶參構(gòu)造，我們繼續(xù)追進去看看，如下 :

可以看到，最終調(diào)用的還是LinkedHashMap的構(gòu)造器。（LinkedHashMap是HashMap的子類）

好的，接下來我們跳出構(gòu)造器，回到演示類中，如下 :

可以看到，此時的map對象是LinkedHashMap類型。

②跳入resize方法。

準備向集合中添加第一個元素，注意，LinkedHashMap和HashMap在底層添加元素時，幾乎完全一樣，前面幾步像是跳入add方法 ——> 跳入put方法 ——> 跳入putVal方法二者是完全一致的。

up這里就不再贅述了，因為在之前的HashSet源碼分析中我們已經(jīng)非常詳細地說過了，這里再長篇大論地給大家講就真的有水博客的嫌疑了，雖然up蠻喜歡水博客的（bushi）。

因此，為了大家的閱讀體驗，強烈建議大家在看本篇"LinkedHashSet"的源碼分析之前，先去看看up寫得"HashSet"源碼分析。

我們直接從二者不一樣的地方開始說起。在putVal方法中，第一個if語句滿足判斷，如下 :

可以看到，我們要進入resize方法對tab數(shù)組進行擴容，resize方法要返回一個Node類型的數(shù)組給tab數(shù)組。

我們跳入resize方法，resize方法源碼如下：

    final Node<K,V>[] resize() {
        Node<K,V>[] 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) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            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;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> 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<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) == 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;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

好的，前面幾步都還和HashSet添加第一個元素時一樣，如下 :

定義Node數(shù)組類型的引用oldTabl，并將table數(shù)組賦值給oldTab引用，oldTab也為null；又用一個三目運算符最終將0賦值給了oldCap變量。

下一步開始就要不一樣了，如下 :

注意看，不知道大家還記不記得，在HashSet的源碼分析中，這里的threshold應(yīng)該等于0呀。我們再次查看一下threshold的源碼，如下 :

欸嘿，奇了怪了，int類型默認值應(yīng)該為0呀，怎么這里也顯示它為16了？

顯然，在前面的某一個步驟中，threshold已經(jīng)被作了修改。這時候可能會有p小將（personable小將，指風(fēng)度翩翩的人）出來bb問了：這™講得個什么玩意兒？也沒見著對threshold的賦值操作呀，你說是就是？

③threshold發(fā)生改變的真正原因

大家仔細想一想，到目前為止，有沒有發(fā)覺到什么蹊蹺的地方？

回顧目前執(zhí)行過的步驟，呃，也就一個無參構(gòu)造，后面跳入add方法幾步都和HashSet一樣我們也沒再演示。

沒錯！就是這個無參構(gòu)造。

請大家翻回去看看，我們一開始調(diào)用的明明是LinkedHashSet的無參構(gòu)造，最后真正起到執(zhí)行效果的卻是LinkedHashMap的帶參構(gòu)造。

還沒發(fā)現(xiàn)么？帶參構(gòu)造！這肯定里面有東西呀。

所以，下一步我們直接重新Debug，并回到我們一開始追到HashSet構(gòu)造器的界面，如下圖所示:

注意看實參，初始容量和加載因子，都是老面孔了，這里不再贅述，但要記住它們此時的值——16和0.75。

好的，接下來我們就繼續(xù)追入LinkedHashMap的這個帶參構(gòu)造，看看里面究竟是什么牛馬玩意兒，如下圖所示 :

哎喲我趣，又是熟悉的復(fù)合包皮結(jié)構(gòu)。沒想到啊，LInkedHashMap的帶參構(gòu)造，最終卻又調(diào)用了其父類HashMap的帶參構(gòu)造，不得不說，java語言里面的"啃老"現(xiàn)象，屬實有丶嚴重了。

好的，看個玩笑。我們回到正題，繼續(xù)追入HashMap的帶參構(gòu)造，如下 :

哎喲，這第一眼看上去還挺有貨。當然，還是那句話——不要因為走得太遠而忘了自己為什么出發(fā)。我們半路折回去，不就是想找到為threshold賦值的語句么。

仔細看，最后一句正是我們要找的為threshold賦值的語句。

但是該賦值語句中又調(diào)用了tableSizeFor方法，見名知意，這個方法和table數(shù)組的容量有關(guān)。我們也沒辦法，畢竟已經(jīng)上了賊船，還是得一路坐到西。

跳入tableSizeFor方法，如下 :

首先，定義了n變量，并通過一個算法為其初始化，這里涉及到了二進制無符號右移的內(nèi)容，我們不再深究。

看右面IDEA提示，我們只需要知道最后n = 15就可以了。

其次，return語句的返回值是一個雙重復(fù)合的三目運算符。

什么意思呢？就是說如果外層三目運算符的判斷條件成立，就返回1，否則返回內(nèi)層三目運算符的結(jié)果。

而外層判斷條件n < 0顯然不成立，所以要返回內(nèi)層三目運算符的結(jié)果；內(nèi)容判斷條件n是否大于那一大堆數(shù)（將鼠標懸浮在上面可以顯示），顯然不成立。所以return語句最后返回的值就是 n + 1 = 16。

跳出tableSizeFor方法，如下 :

這下可以解釋我們前面的問題了。

threshold就是在HashMap的無參構(gòu)造中被初始化為了16。（注意此處loadFactor屬性也被初始化，初始化為了0.75）

④繼續(xù)回到resize方法。

好的，搞清楚threshold變量變化的原因后，我們可以返回到剛剛的resize方法繼續(xù)解讀。如下 :

可以看到，將threshold（= 16）賦值給oldThr變量后，又定義了newCap（即newCapacity）和newThr（即newThreshold）兩個變量。第一個if語句顯然判斷不成立，不進入它。但后面的else if語句的判斷是成立的，如下 :

else if語句中，將newCap賦值為了16。

繼續(xù)，接下來的一個if語句如下 :

由于threshold的改變，我們并沒有進入if-else if-esle中的else語句，而是進入了else if語句，所以newThr變量還是默認值0。這里其實就是將ft賦值給了newThr變量，計算方式仍然是數(shù)組容量 * 增長因子 = 16 * 0.75 = 12。

繼續(xù)，如下圖 :

后面幾步就都一樣了。將臨界值12賦值給threshold屬性，這才符合邏輯對不對？（關(guān)于臨界值，up已經(jīng)在HashSet源碼分析中仔細講過了，大家可以去找一下，這里不再贅述）。

然后，又是new一個長度為16的數(shù)組，并最終將table屬性初始化。之后有個巨**大的if 語句，不過，幸好，判斷為假，我們不用進去??。

好的，最后就是返回這個新數(shù)組了，如下 :

⑤回到演示類方法。

接下來，我們先回到putVal方法，如下 :

仍然是根據(jù)當前元素（141）的hash值，通過特定的算法獲得當前元素在table數(shù)組中應(yīng)該存放的位置的索引值。

然后判斷，如果table數(shù)組該索引處為空，就直接放進去；不為空的話就去下面的else語句，去鏈表中一一進行判斷。

當然，這些都是在HashSet源碼分析中講過的。以下幾個步驟也都一樣，我們也不再多說，畢竟老講重復(fù)的東西也沒啥意思對不對？

好滴，接下來我們逐層返回，一直到演示類中，如下GIF圖所示 :

可以看到，table數(shù)組成功初始化為長度 = 16的數(shù)組，141元素也成功添加到了集合中。

但是注意看，此時table數(shù)組仍然是Node類型（LinkedHashMap的內(nèi)部類），但是里面保存的元素卻成了Entry類型（HashMap的內(nèi)部類）。

一個類型的數(shù)組里面存放了另一類型的元素，請問，你想到了什么？大聲告訴我！沒錯，多態(tài)數(shù)組。

顯然，這里的Entry類型一定是繼承或者實現(xiàn)了Node類型。

⑥多態(tài)數(shù)組的體現(xiàn)。

我們來看看Entry類的源碼，如下 :

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

這下真相大白了，Entry類繼承了Node類，因此Node類型數(shù)組中存放Entry類型元素達到了多態(tài)的效果。

大家注意，此處的Node類型是由HashMap通過類名來引用的，顯然，Node類型其實就是HashMap類中的一個靜態(tài)內(nèi)部類。

同時要注意，Entry內(nèi)部類中定義了before和after屬性，即我們在上文"LinkedHashSet的底層實現(xiàn)"中提到的——before指向雙向鏈表的前一個結(jié)點，after指向雙向鏈表的后一個結(jié)點，從而實現(xiàn)雙向鏈表。

繼續(xù)向集合添加元素

①向集合中添加重復(fù)元素

當我們重復(fù)添加141元素時，肯定無法加入。底層和HashSet玩得是一套，up就不演示了。大家可以自己下去Debug一次，回顧一下就好。

當然，我們在Debug界面中也可以查看table數(shù)組的情況，如下 :

可以看到，此時集合中仍然只有一個元素。

②向集合中添加第二個元素

繼續(xù)向下執(zhí)行，將"CSDN"元素加入集合中。如下圖所示 :

可以看到，目前table數(shù)組中已經(jīng)有倆元素了。注意，記住這倆元素目前的標識——141的標識是819，"CSDN"的標識是836。

注意，精彩的要來了，如下 :

我們點開添加的第一個元素，可以看到，此時第一個元素141的after屬性指向了第二個元素"CSDN"，而第二個屬性的before屬性則指向了第一個元素141；

并且141元素的before屬性和"CSDN"元素的after屬性均為null。

此時，table數(shù)組中的兩個元素已然形成了一個簡單的雙向鏈表。

并且，我們還可以在map對象的界面看到head和tail分別指向了第一個元素和最后一個元素。

此時，這個簡單的雙向鏈表就應(yīng)該長下面這個樣子 :

③向集合中添加第三個元素。

繼續(xù)向下執(zhí)行，將11元素加入到集合中，如下圖所示 :

此時底層的"數(shù)組 + 鏈表"結(jié)構(gòu)如下 :

④向集合中添加第四、五、六個元素。

繼續(xù)向下執(zhí)行，向集合中添加"Cyan"，new Apple("紅富士")，和new Apple("紅富士")這三個對象。

注意，由于我們沒有在Apple類重寫equals方法，因此兩個Apple對象會被判定為不同的元素，可以加入集合；

但是由于我們在Apple類中重寫了hashCode方法，這倆對象返回對哈希碼值一樣，因此它們會掛載到同一鏈表下。Debug界面圖示如下 :

我們可以通過點擊每個元素的after屬性來直接查看它的下一個屬性，如下GIF圖所示 :

此時底層的"數(shù)組 + 鏈表"結(jié)構(gòu)如下 :

可能有點亂，不過看準每個結(jié)點的before和after，以及第一個結(jié)點和最后一個結(jié)點的null，還是可以很輕松找到順序的。

這里還要再說一點——關(guān)于after和next的區(qū)別，其實很簡單——

after是用于雙向鏈表中專門指向下一個元素，沒有下一個元素則為null。即不管某一個結(jié)點的下一個元素是在table數(shù)組中其他索引處的位置，還是掛載在該結(jié)點的后面，after都會指向它。
next則是和我們在HashSet中分析的一樣，如果數(shù)組某一個索引處的元素形成了鏈表，next會指向鏈表中的下一個元素。
比如，此處的第一個Apple對象元素，它的after毫無疑問指向了第一個Apple對象元素；但是因為第二個Apple對象元素恰好掛載在了它的后面，即它們在table數(shù)組同一索引處的位置，所以第一個Apple對象元素的next屬性也指向了第二個Apple對象。
也就是說，after是針對了整個雙向鏈表，針對于所有元素，針對于全局；而next則是僅僅針對于同一索引位置處形成的單向鏈表，針對于table數(shù)組同一索引位置處的元素，針對于局部。

所以，我們可以通過Debug看到，在table數(shù)組的所有元素中，僅有第一個Apple對象元素的next屬性有指向，且指向同它的after屬性一樣，指向了掛載在它后面的第二個Apple對象元素。如下圖所示 :