前幾天寫了一篇StringBuilder與TextWriter二者之間區(qū)別的文章（鏈接）。當時提了一句沒有找到相關源碼，于是隨后有很多熱心人士給出了相關的源碼鏈接（鏈接），感謝大家。這幾天抽了點時間查看了下StringBuilder是如何動態(tài)構造字符串的，發(fā)現(xiàn)在.NET Core中字符串的構建似乎和我原先猜想的并不完全一樣，故此寫了這篇文章，如有錯誤，歡迎指出。

`StringBuilder`字段和屬性

字符數(shù)組

明確一點的是，StringBuilder的內(nèi)部確實使用字符數(shù)組來管理字符串信息的，這一點上和我當時的猜測是差不多的。相較于字符串在大多數(shù)情況下的不變性而言，字符數(shù)組有其優(yōu)點，即修改字符數(shù)組內(nèi)部的數(shù)據(jù)不會全部重新創(chuàng)建字符數(shù)組（字符串的不變性）。下面是StringBuilder的部分源碼，可以看到，內(nèi)部采用m_ChunkChars字段存儲字符數(shù)組信息。

public sealed class StringBuilder
{
    internal char[] m_ChunkChars;
    ...
}

然而，采用字符數(shù)組并不是沒有缺點，數(shù)組最大的缺點就是在在使用前就需要指定它的空間大小，這種固定大小的數(shù)組空間不可能有能力處理多次的字符串拼接，總有某次，數(shù)組中的空余部分塞不下所要拼接的字符串。如果某次拼接的字符串超過數(shù)組的空閑空間時，一種易想到做到的方法就是開辟一個更大的空間，并將原先的數(shù)據(jù)復制過去。這種方法能夠保證數(shù)組始終是連續(xù)的，然而，它的問題在于，復制是一個非常耗時的操作，如非必要，盡可能地降低復制的頻率。在.NET Core中，StringBuilder采用了一個新方法避免了復制操作。

單鏈表

為了能夠有效地提高性能，StringBuilder采用鏈表的形式規(guī)避了兩個字符數(shù)組之間的復制操作。在其源代碼中，可以發(fā)現(xiàn)每個StringBuilder內(nèi)部保留對了另一個StringBuilder的引用。

public sealed class StringBuilder
{
    internal StringBuilder? m_ChunkPrevious;
    ...
}

在StringBuilder中，每個對象都維護了一個m_ChunkPrevious引用，按字段命名的意思來說，就是每個類對象都維護指向前一個類對象的引用。這一點和我們常見的單鏈表結構有點一點不太一樣，常見的單鏈表結構中每個節(jié)點維護的是指向下一個節(jié)點的引用，這和StringBuilder所使用的模式剛好相反，挺奇怪的。整理下，這部分有兩個問題：

為什么說采用單鏈表能避免復制操作？
為什么采用逆向鏈表，即每個節(jié)點保留指向前一個節(jié)點的引用？

對于第一個問題，試想下，如果又有新的字符串需要拼接且其長度超過字符數(shù)組空閑的容量時，可以考慮新開辟一個新空間專門存儲超額部分的數(shù)據(jù)。這樣，先前部分的數(shù)據(jù)就不需要進行復制了，但這又有一個新問題，整個數(shù)據(jù)被存儲在兩個不相連的部分，怎么關聯(lián)他們，采用鏈表的形式將其關聯(lián)是一個可行的措施。以上就是StringBuilder拼接字符串最為核心的部分了。

那么，對于第二個問題，采用逆向鏈表對的好處是什么？這里我給出的原因?qū)儆谖覀€人的主觀意見，不一定對。從我平時使用上以及一些開源類庫中來看，對StringBuilder使用最廣泛的功能就是拼接字符串了，即向尾部添加新數(shù)據(jù)。在這個基礎上，如果采用正向鏈表（每個節(jié)點保留下一個節(jié)點的引用），那么多次拼接字符串在數(shù)組容量不夠的情況下，勢必需要每次循環(huán)找到最后一個節(jié)點并添加新節(jié)點，時間復雜度為O(n)。而采用逆向鏈表，因為用戶所持有的就是最后一個節(jié)點，只需要在當前節(jié)點上做些處理就可以添加新節(jié)點，時間復雜度為O(1)。因此，StringBuilder內(nèi)的字符數(shù)組可以說是字符串的一個部分，也被稱為Chunk。

舉個例子，如果類型為Stringbuilder變量sb內(nèi)已經(jīng)保存了HELLO字符串，再添加WORLD時，如果字符數(shù)組滿了，再添加就會構造一個新StringBuilder節(jié)點。注意的是調(diào)用類方法不會改變當前變量sb指向的對象，因此，它會移動內(nèi)部的字符數(shù)組引用，并將當前變量的字符數(shù)組引用指向WORLD。下圖中的左右兩圖是添加前后的說明圖，其中黃色StringBuilder是同一個對象。

當然，采用鏈表并非沒有代價。因為鏈表沒有隨機讀取的功能。因此，如果向指定位置添加新數(shù)據(jù)，這反而比只使用一個字符數(shù)組來得慢。但是，如果前面的假設沒錯的話，也就是最頻繁使用的是尾部拼接的話，那么使用鏈表的形式是被允許的。根據(jù)使用場景頻率的不同，提供不同的實現(xiàn)邏輯。

各種各樣的長度

剩下來的部分，就是描述各種各樣的長度及其他數(shù)據(jù)。主要如下：

public sealed class StringBuilder
{
    internal int m_ChunkLength;
    internal int m_ChunkOffset;
    internal int m_MaxCapacity;
    internal const int DefaultCapacity = 16;
    internal const int MaxChunkSize = 8000;
    public int Length
    {
        get => m_ChunkOffset + m_ChunkLength;
    }
    ...
}

m_ChunkLength描述當前Chunk存儲信息的長度。也就是存儲了字符數(shù)據(jù)的長度，不一定等于字符數(shù)組的長度。
m_ChunkOffset描述當前Chunk在整體字符串中的起始位置，方便定位。
m_MaxCapacity描述構建字符串的最大長度，通常設置為int最大值。
DefaultCapacity描述默認設置的空間大小，這里設置的是16。
MaxChunkSize描述Chunk的最大長度，也就是Chunk的容量。
Length屬性描述的是內(nèi)部保存整體字符串的長度。

構造函數(shù)

上述講述的是StringBuilder的各個字段和屬性的意義，這里就深入看下具體函數(shù)的實現(xiàn)。首先是構造函數(shù)，這里僅列舉本文所涉及到的幾個構造函數(shù)。

public StringBuilder()
{
    m_MaxCapacity = int.MaxValue;
    m_ChunkChars = new char[DefaultCapacity];
}

public StringBuilder(string? value, int startIndex, int length, int capacity)
{
    ...
    m_MaxCapacity = int.MaxValue;
    if (capacity == 0)
    {
        capacity = DefaultCapacity;
    }
    capacity = Math.Max(capacity, length);

    m_ChunkChars = GC.AllocateUninitializedArray<char>(capacity);
    m_ChunkLength = length;

    unsafe
    {
        fixed (char* sourcePtr = value)
        {
            ThreadSafeCopy(sourcePtr + startIndex, m_ChunkChars, 0, length);
        }
    }
}

private StringBuilder(StringBuilder from)
{
    m_ChunkLength = from.m_ChunkLength;
    m_ChunkOffset = from.m_ChunkOffset;
    m_ChunkChars = from.m_ChunkChars;
    m_ChunkPrevious = from.m_ChunkPrevious;
    m_MaxCapacity = from.m_MaxCapacity;
    ...
}

這里選出了三個和本文關系較為緊密的構造函數(shù)，一個個分析。

首先是默認構造函數(shù)，該函數(shù)沒有任何的輸入?yún)?shù)。代碼中可以發(fā)現(xiàn)，其分配的長度就是16。也就是說不對其做任何指定的話，默認初始長度為16個Char型數(shù)據(jù)，即32字節(jié)。
第二個構造函數(shù)是當構造函數(shù)傳入為字符串時所調(diào)用的，這里我省略了在開始最前面的防御性代碼。這里的構造過程也很簡單，比較傳入字符串的大小和默認容量DefaultCapacity的大小，并開辟二者之間最大值的長度，最后將字符串復制到數(shù)組中?？梢园l(fā)現(xiàn)的是，這種情況下，初始字符數(shù)組的長度并不總是16，畢竟如果字符串長度超過16，肯定按照更長的來。
第三個構造函數(shù)專門用來構造StringBuilder的節(jié)點的，或者說是StringBuilder的復制，即原型模式。它主要用在容量不夠構造新的節(jié)點，本質(zhì)上就是將內(nèi)部數(shù)據(jù)全部賦值過去。

從前兩個構造函數(shù)可以看出，如果第一次待拼接的字符串長度超過16，那么直接將該字符串以構造函數(shù)的參數(shù)傳入比構建默認StringBuilder對象再使用Append方法更加高效，畢竟默認構造函數(shù)只開辟了16個char型空間。

`Append`方法

這里主要看StringBuilder Append(char value, int repeatCount)這個方法（位于第710行）。該方法主要是向尾部添加char型字符value，一共添加repeatCount個。

public StringBuilder Append(char value, int repeatCount)
{
    ...

    int index = m_ChunkLength;
    while (repeatCount > 0)
    {
        if (index < m_ChunkChars.Length)
        {
            m_ChunkChars[index++] = value;
            --repeatCount;
        }
        else
        {
            m_ChunkLength = index;
            ExpandByABlock(repeatCount);
            Debug.Assert(m_ChunkLength == 0);
            index = 0;
        }
    }

    m_ChunkLength = index;
    AssertInvariants();
    return this;
}

這里僅列舉出部分代碼，起始的防御性代碼以及驗證代碼略過?？聪缕溥\行邏輯：

依次循環(huán)當前字符repeatCount次，對每一次執(zhí)行以下邏輯。（while大循環(huán)）
如果當前字符數(shù)組還有空位時，則直接向內(nèi)部進行添加新數(shù)據(jù)。（if語句命中部分）
如果當前字符數(shù)組已經(jīng)被塞滿了，首先更新m_ChunkLength值，因為數(shù)組被塞滿了，因此需要下一個數(shù)組來繼續(xù)放數(shù)據(jù)，當前的Chunk長度也就是整個字符數(shù)組的長度，需要更新。其次，調(diào)用了ExpandByABlock(repeatCount)函數(shù)，輸入?yún)?shù)為更新后的repeatCount數(shù)據(jù)，其做的就是構建新的節(jié)點，并將其掛載到鏈表上。
更新m_ChunkLength值，記錄當前Chunk的長度，最后將本身返回。

接下來就是ExpandByABlock方法的實現(xiàn)。

private void ExpandByABlock(int minBlockCharCount)
{
    ...
    int newBlockLength = Math.Max(minBlockCharCount, Math.Min(Length, MaxChunkSize));
    ...

    // Allocate the array before updating any state to avoid leaving inconsistent state behind in case of out of memory exception
    char[] chunkChars = GC.AllocateUninitializedArray<char>(newBlockLength);

    // Move all of the data from this chunk to a new one, via a few O(1) pointer adjustments.
    // Then, have this chunk point to the new one as its predecessor.
    m_ChunkPrevious = new StringBuilder(this);
    m_ChunkOffset += m_ChunkLength;
    m_ChunkLength = 0;

    m_ChunkChars = chunkChars;

    AssertInvariants();
}

和上面一樣，僅列舉出核心功能代碼。

設置新空間的大小，該大小取決于三個值，從當前字符串長度和Chunk最大容量取較小值，然后從較小值和輸入?yún)?shù)長度中取最大值作為新Chunk的大小。值得注意的是，這里當前字符串長度通常是Chunk已經(jīng)被塞滿的情況下，可以理解成所有Chunk的長度之和。
開辟新空間。
通過上述最后一個構造函數(shù)，構造向前的節(jié)點。當前節(jié)點仍然為最后一個節(jié)點，更新其他值，即偏移量應該是原先偏移量加上一個Chunk的長度。清空當前Chunk的長度以及將新開辟空間給Chunk引用。

對于Append(string? value)這個函數(shù)的實現(xiàn)功能和上述說明是差不多的，基本都是新數(shù)據(jù)先往當前的字符數(shù)組內(nèi)塞，如果塞滿了就添加新節(jié)點并刷新當前字符數(shù)組數(shù)據(jù)再塞。詳細的功能可以從L802開始看。這里不做過多說明。

驗證

當然，以上只是閱讀代碼的流程，具體是否正確還可以做點測試來驗證。這里我做了一個小測試demo。

var sb = new StringBuilder();
sb.Append('1', 10);
sb.Append('2', 6);
sb.Append('3', 24);
sb.Append('4', 15);
sb.Append("hello world");
sb.Append("nice to meet you");
Console.WriteLine($"結果：{sb.ToString()}");

var p = sb;
char[] data;
Type type = sb.GetType();
int count = 0;
while (p != null)
{
    count++;
    data = (char[])type.GetField("m_ChunkChars", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(p);
    Console.WriteLine($"倒數(shù)第{count}個StringBuilder內(nèi)容:{new string(data)}");
    p = (StringBuilder)type.GetField("m_ChunkPrevious", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(p);
}

這里主要做的是利用Append方法添加不同的數(shù)據(jù)并將最終結果輸出。考慮到內(nèi)部的細節(jié)并沒有對外公開，只能通過反射的操作來獲取，通過遍歷每一個StringBuilder的節(jié)點，反射獲取內(nèi)部的字符數(shù)組并將其輸出。最終的結果如下。

這里分析下具體的過程：

第一句sb = new StringBuilder()。從之前的構造函數(shù)代碼內(nèi)可以得知，無參構造函數(shù)會生成一個16長度的字符數(shù)組。
第二句sb.Append('1', 10)。這句話意思是向sb內(nèi)添加10個1字符，因為添加的長度小于給定的默認值16，因此直接將其添加即可。
第三句sb.Append('2', 6)。在經(jīng)過上面添加操作后，當前字符數(shù)組還剩6個空間，剛好夠塞，因此直接將6個2字符直接塞進去。
第四句sb.Append('3', 24)。在添加字符3之前，StringBuilder內(nèi)部的字符數(shù)組就已經(jīng)沒有空間了。為此，需要構造新的StringBuilder對象，并將當前對象內(nèi)的數(shù)據(jù)傳過去。對于當前對象，需要創(chuàng)建新的字符數(shù)組，按照之前給出的規(guī)則，當前Chunk之和（16）和Chunk長度（8000）取最小值（16），最小值（16）和輸入字符串長度（24）取最大值（24）。因此，直接創(chuàng)建24個字符空間并存下來。此時，sb對象有一個前置節(jié)點。
第五句sb.Append('4', 15)。上一句代碼只創(chuàng)建了長度為24的字符數(shù)組，因此，新數(shù)據(jù)依然無法再次塞入。此時，依舊需要創(chuàng)建新的StringBuilder節(jié)點，按照同樣的規(guī)則，取當前所有Chunk之和（16+24=40）。因此，新字符數(shù)組長度為40，內(nèi)部存了15個字符數(shù)據(jù)4。sb對象有兩個前置節(jié)點。
第六句sb.Append("hello world")。這個字符串長度為11，當前字符數(shù)組能完全放下，則直接放下。此時字符數(shù)組還空余14個空間。
第七句sb.Append("nice to meet you")。這個字符串長度為16，可以發(fā)現(xiàn)超過了剩余空間，首先先填充14個字符。之后多出的2個，則按照之前的規(guī)則再構造新的節(jié)點，新節(jié)點的長度為所有Chunk之和（16+24+40=80），即有80個存儲空間。當前Chunk只存儲最后兩個字符ou。sb對象有3個前置節(jié)點。符合最終的輸出結果。

總結

總的來說，采用定長的字符數(shù)組來保存不定長的字符串，不可能完全避免所添加的數(shù)據(jù)超出剩余空間這樣的情況，重新開辟新空間并復制原始數(shù)據(jù)過于耗時。StringBuilder采用鏈表的形式取消了數(shù)據(jù)的復制操作，提高了字符串連接的效率。對于StringBuilder來說，大部分的操作都在尾部添加，采用逆向鏈表是一個不錯的形式。當然StringBuilder這個類本身有很多復雜的實現(xiàn)，本篇只是介紹了Append方法是如何進行字符串拼接的。

源碼上看 .NET 中 StringBuilder 拼接字符串的實現(xiàn)

StringBuilder字段和屬性

字符數(shù)組

單鏈表

各種各樣的長度

構造函數(shù)

Append方法

驗證

總結

`StringBuilder`字段和屬性

`Append`方法