Java的LinkedHashSet源碼深入講解

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

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

一、前言

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

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

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

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

注意 :

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

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

二、LinkedHashSet簡(jiǎn)介

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

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

我們?cè)賮?lái)看一下LinkedHashSet的類圖，如下 :

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

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

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

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

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

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

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

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

5.LinkedHashSet的底層機(jī)制圖示 :

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

準(zhǔn)備工作

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

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è)元素

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

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

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

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

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

可以看到，此時(shí)的map對(duì)象是LinkedHashMap類型。

②跳入resize方法。

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

up這里就不再贅述了，因?yàn)樵谥暗腍ashSet源碼分析中我們已經(jīng)非常詳細(xì)地說(shuō)過(guò)了，這里再長(zhǎng)篇大論地給大家講就真的有水博客的嫌疑了，雖然up蠻喜歡水博客的（bushi）。

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

我們直接從二者不一樣的地方開(kāi)始說(shuō)起。在putVal方法中，第一個(gè)if語(yǔ)句滿足判斷，如下 :

可以看到，我們要進(jìn)入resize方法對(duì)tab數(shù)組進(jìn)行擴(kuò)容，resize方法要返回一個(gè)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添加第一個(gè)元素時(shí)一樣，如下 :

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

下一步開(kāi)始就要不一樣了，如下 :

注意看，不知道大家還記不記得，在HashSet的源碼分析中，這里的threshold應(yīng)該等于0呀。我們?cè)俅尾榭匆幌聇hreshold的源碼，如下 :

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

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

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

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

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

沒(méi)錯(cuò)！就是這個(gè)無(wú)參構(gòu)造。

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

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

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

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

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

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

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

哎喲，這第一眼看上去還挺有貨。當(dāng)然，還是那句話——不要因?yàn)樽叩锰h(yuǎn)而忘了自己為什么出發(fā)。我們半路折回去，不就是想找到為threshold賦值的語(yǔ)句么。

仔細(xì)看，最后一句正是我們要找的為threshold賦值的語(yǔ)句。

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

跳入tableSizeFor方法，如下 :

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

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

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

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

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

跳出tableSizeFor方法，如下 :

這下可以解釋我們前面的問(wèn)題了。

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

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

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

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

else if語(yǔ)句中，將newCap賦值為了16。

繼續(xù)，接下來(lái)的一個(gè)if語(yǔ)句如下 :

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

繼續(xù)，如下圖 :

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

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

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

⑤回到演示類方法。

接下來(lái)，我們先回到putVal方法，如下 :

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

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

當(dāng)然，這些都是在HashSet源碼分析中講過(guò)的。以下幾個(gè)步驟也都一樣，我們也不再多說(shuō)，畢竟老講重復(fù)的東西也沒(méi)啥意思對(duì)不對(duì)？

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

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

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

一個(gè)類型的數(shù)組里面存放了另一類型的元素，請(qǐng)問(wèn)，你想到了什么？大聲告訴我！沒(méi)錯(cuò)，多態(tài)數(shù)組。

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

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

我們來(lái)看看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類型元素達(dá)到了多態(tài)的效果。

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

同時(shí)要注意，Entry內(nèi)部類中定義了before和after屬性，即我們?cè)谏衔?quot;LinkedHashSet的底層實(shí)現(xiàn)"中提到的——before指向雙向鏈表的前一個(gè)結(jié)點(diǎn)，after指向雙向鏈表的后一個(gè)結(jié)點(diǎn)，從而實(shí)現(xiàn)雙向鏈表。

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

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

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

當(dāng)然，我們?cè)贒ebug界面中也可以查看table數(shù)組的情況，如下 :

可以看到，此時(shí)集合中仍然只有一個(gè)元素。

②向集合中添加第二個(gè)元素

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

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

注意，精彩的要來(lái)了，如下 :

我們點(diǎn)開(kāi)添加的第一個(gè)元素，可以看到，此時(shí)第一個(gè)元素141的after屬性指向了第二個(gè)元素"CSDN"，而第二個(gè)屬性的before屬性則指向了第一個(gè)元素141；

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

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

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

此時(shí)，這個(gè)簡(jiǎn)單的雙向鏈表就應(yīng)該長(zhǎng)下面這個(gè)樣子 :

③向集合中添加第三個(gè)元素。

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

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

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

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

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

但是由于我們?cè)贏pple類中重寫了hashCode方法，這倆對(duì)象返回對(duì)哈希碼值一樣，因此它們會(huì)掛載到同一鏈表下。Debug界面圖示如下 :

我們可以通過(guò)點(diǎn)擊每個(gè)元素的after屬性來(lái)直接查看它的下一個(gè)屬性，如下GIF圖所示 :

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

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

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

after是用于雙向鏈表中專門指向下一個(gè)元素，沒(méi)有下一個(gè)元素則為null。即不管某一個(gè)結(jié)點(diǎn)的下一個(gè)元素是在table數(shù)組中其他索引處的位置，還是掛載在該結(jié)點(diǎn)的后面，after都會(huì)指向它。
next則是和我們?cè)贖ashSet中分析的一樣，如果數(shù)組某一個(gè)索引處的元素形成了鏈表，next會(huì)指向鏈表中的下一個(gè)元素。
比如，此處的第一個(gè)Apple對(duì)象元素，它的after毫無(wú)疑問(wèn)指向了第一個(gè)Apple對(duì)象元素；但是因?yàn)榈诙€(gè)Apple對(duì)象元素恰好掛載在了它的后面，即它們?cè)趖able數(shù)組同一索引處的位置，所以第一個(gè)Apple對(duì)象元素的next屬性也指向了第二個(gè)Apple對(duì)象。
也就是說(shuō)，after是針對(duì)了整個(gè)雙向鏈表，針對(duì)于所有元素，針對(duì)于全局；而next則是僅僅針對(duì)于同一索引位置處形成的單向鏈表，針對(duì)于table數(shù)組同一索引位置處的元素，針對(duì)于局部。

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