簡單聊聊C#字符串構建利器StringBuilder
前言
在日常的開發中StringBuilder大傢肯定都有用過,甚至用的很多。畢竟大傢都知道一個不成文的規范,當需要高頻的大量的構建字符串的時候StringBuilder的性能是要高於直接對字符串進行拼接的,因為直接使用+或+=都會產生一個新的String實例,因為String對象是不可變的對象,這也就意味著每次對字符串內容進行操作的時候都會產生一個新的字符串實例,這對大量的進行字符串拼接的場景是非常不友好的。因此StringBuilder孕育而出。這裡需要註意的是,這並不意味著可以用StringBuilder來代替所有字符串拼接的的場景,這裡我們強調一下是頻繁的對同一個字符串對象進行拼接的操作。今天我們就來看一下c#中StringBuilder的巧妙實現方式,體會一下底層類庫解決問題的方式。
需要註意的是,這裡的不可變指的是字符串對象本身的內容是不可改變的,但是字符串變量的引用是可以改變的。
簡單示例
接下來咱們就來簡單的示例一下操作,其實核心操作主要是Append方法和ToString方法,源碼的的角度上來說還有StringBuilder的構造函數。首先是大傢最常用的方式,直接各種Append然後最後得到結果。
StringBuilder builder = new StringBuilder(); builder.Append("我和我的祖國"); builder.Append(','); builder.Append("一刻也不能分割"); builder.Append('。'); builder.Append("無論我走到哪裡,都留下一首贊歌。"); builder.Append("我歌唱每一座高山,我歌唱每一條河。"); builder.Append("裊裊炊煙,小小村落,路上一道轍。"); builder.Append("我永遠緊依著你的心窩,你用你那母親的脈搏,和我訴說。"); string result = builder.ToString(); Console.WriteLine(result);
StringBuilder也是支持通過構造函數初始化一些數據的,有沒有在構造函數傳遞初始化數據,也就意味著不同的初始化邏輯。比如以下操作
StringBuilder builder = new StringBuilder("我和我的祖國"); //或者是指定StringBuilder的容量,這樣的話StringBuilder初始可承載字符串的長度是16 builder = new StringBuilder(16);
因為StringBuilder是基礎類庫,因此看著很簡單,用起來也很簡單,而且大傢也都經常使用這些操作。
源碼探究
上面咱們簡單的演示瞭StringBuilder的使用方式,一般的類似的StringBuilder或者是List這種雖然我沒使用的過程中可以不關註容器本身的長度一直去添加元素,實際上這些容器的本身內部實現邏輯都包含瞭一些擴容相關的邏輯。上面咱們提到瞭一下StringBuilder的核心主要是三個操作,也就是通過這三個功能可以呈現出StringBuilder的工作方式和原理。
- 一個是構造函數,因為構造函數包含瞭初始化的一些邏輯。
- 其次是Append方法,這是StringBuilder進行字符串拼接的核心操作。
- 最後是將StringBuilder轉換成字符串的操作ToString方法,這是我們得到拼接字符串的操作。
接下來咱們就從這三個相關的方法入手來看一下StringBuilder的核心實現,這裡我參考的.net版本為v6.0.2。
構造入手
我們上面提到瞭StringBuilder的構造函數代表瞭初始化邏輯,大概來看就是默認的構造函數,即默認初始化邏輯和自定義一部分構造函數的邏輯,主要是的邏輯是決定瞭StringBuilder容器可容納字符串的長度。
無參構造
首先來看一下默認的無參構造函數的實現[點擊查看源碼👈]
//可承載字符的最大容量,即可以拼接的字符串的長度 internal int m_MaxCapacity; //承載【拼接字符串的char數組 internal char[] m_ChunkChars; //默認的容量,即默認初始化m_ChunkChars的長度,也就是首次擴容觸發的長度 internal const int DefaultCapacity = 16; public StringBuilder() { m_MaxCapacity = int.MaxValue; m_ChunkChars = new char[DefaultCapacity]; }
通過默認的無參構造函數,我們可以瞭解到兩點信息
- 首先是StringBuilder核心存儲字符串的容器是char[]字符數組。
- 默認容器的char[]字符數組聲明的長度是16,即如果首次StringBuilder容納的字符個數超過16則觸發擴容機制。
帶參數的構造
StringBuilder的有參數的構造函數有好幾個,如下所示
//聲明初始化容量,即首次擴容觸發的長度條件 public StringBuilder(int capacity) //聲明初始化容量,和最大容量即可以動態構建字符串的總長度 public StringBuilder(int capacity, int maxCapacity) //用給定字符串初始化 public StringBuilder(string? value) //用給定字符串初始化,並聲明容量 public StringBuilder(string? value, int capacity) //用一個字符串截取指定長度初始化,並聲明最大容量 public StringBuilder(string? value, int startIndex, int length, int capacity)
雖然構造函數有很多,但是大部分都是在調用調用自己的重載方法,核心的有參數的構造函數其實就兩個,咱們分別來看一下,首先是指定容量的初始化構造函數[點擊查看源碼👈]
//可承載字符的最大容量,即可以拼接的字符串的長度 internal int m_MaxCapacity; //承載【拼接字符串的char數組 internal char[] m_ChunkChars; //默認的容量,即默認初始化m_ChunkChars的長度,也就是首次擴容觸發的長度 internal const int DefaultCapacity = 16; public StringBuilder(int capacity, int maxCapacity) { //指定容量不能大於最大容量 if (capacity > maxCapacity) { throw new ArgumentOutOfRangeException(nameof(capacity), SR.ArgumentOutOfRange_Capacity); } //最大容量不能小於1 if (maxCapacity < 1) { throw new ArgumentOutOfRangeException(nameof(maxCapacity), SR.ArgumentOutOfRange_SmallMaxCapacity); } //初始化容量不能小於0 if (capacity < 0) { throw new ArgumentOutOfRangeException(nameof(capacity), SR.Format(SR.ArgumentOutOfRange_MustBePositive, nameof(capacity))); } //如果指定容量等於0,則使用默認的容量 if (capacity == 0) { capacity = Math.Min(DefaultCapacity, maxCapacity); } //最大容量賦值 m_MaxCapacity = maxCapacity; //分配指定容量的數組 m_ChunkChars = GC.AllocateUninitializedArray<char>(capacity); }
主要就是對最大容量和初始化容量進行判斷和賦值,如果制定瞭初始容量和最大容量則以傳遞進來的為主。接下來再看一下根據指定字符串來初始化StringBuilder的主要操作[點擊查看源碼👈]
//可承載字符的最大容量,即可以拼接的字符串的長度 internal int m_MaxCapacity; //承載【拼接字符串的char數組 internal char[] m_ChunkChars; //默認的容量,即默認初始化m_ChunkChars的長度,也就是首次擴容觸發的長度 internal const int DefaultCapacity = 16; //當前m_ChunkChars字符數組中已經使用的長度 internal int m_ChunkLength; public StringBuilder(string? value, int startIndex, int length, int capacity) { if (capacity < 0) { throw new ArgumentOutOfRangeException(); } if (length < 0) { throw new ArgumentOutOfRangeException(); } if (startIndex < 0) { throw new ArgumentOutOfRangeException(); } //初始化的字符串可以為null,如果為null則隻用空字符串即"" if (value == null) { value = string.Empty; } //基礎長度判斷,這個邏輯其實已經包含瞭針對字符串截取的起始位置和接要截取的長度進行判斷瞭 if (startIndex > value.Length - length) { throw new ArgumentOutOfRangeException(); } //最大容量是int的最大值,即2^31-1 m_MaxCapacity = int.MaxValue; if (capacity == 0) { capacity = DefaultCapacity; } //雖然傳遞瞭默認容量,但是這裡依然做瞭判斷,在傳遞的默認容量和需要存儲的字符串容量總取最大值 capacity = Math.Max(capacity, length); //分配指定容量的數組 m_ChunkChars = GC.AllocateUninitializedArray<char>(capacity); //這裡記錄瞭m_ChunkChars固定長度的快中已經被使用的長度 m_ChunkLength = length; //把傳遞的字符串指定位置指定長度(即截取操作)copy到m_ChunkChars中 value.AsSpan(startIndex, length).CopyTo(m_ChunkChars); }
這個初始化操作主要是截取給定字符串的指定長度,存放到ChunkChars用於初始化StringBuilder,其中初始化的容量取決於可以截取的長度是否大於指定容量,實質是以能夠存放截取長度的字符串為主。
構造小結
通過StringBuilder的構造函數中的邏輯我們可以看到StringBuilder本質存儲是在char[],這個字符數組的初始化長度是16,這個長度主要的作用是擴容機制,即首次需要進行擴容的時機是當m_ChunkChars長度超過16的時候,這個時候原有的m_ChunkChars已經不能承載需要構建的字符串的時候觸發擴容。
核心方法
我們上面看到瞭StringBuilder相關的初始化代碼,通過初始化操作,我們可以瞭解到StringBuilder本身的數據結構,但是想瞭解StringBuilder的擴容機制,還需要從它的Append方法入手,因為隻有Append的時候才有機會去判斷原有的m_ChunkChars數組長度是否滿足存儲Append進來的字符串。關於StringBuilder的Append方法有許多重載,這裡咱們就不逐個列舉瞭,但是本質都是一樣的。因此咱們就選取咱們最熟悉的和最常用的Append(string? value)方法進行講解,直接找到源碼位置[點擊查看源碼👈]
//承載【拼接字符串的char數組 internal char[] m_ChunkChars; //當前m_ChunkChars字符數組中已經使用的長度 internal int m_ChunkLength; public StringBuilder Append(string? value) { if (value != null) { // 獲取當前存儲塊 char[] chunkChars = m_ChunkChars; // 獲取當前塊已使用的長度 int chunkLength = m_ChunkLength; // 獲取傳進來的字符的長度 int valueLen = value.Length; //當前使用的長度 + 需要Append的長度 < 當前塊的長度 則不需要擴容 if (((uint)chunkLength + (uint)valueLen) < (uint)chunkChars.Length) { //判斷傳進來的字符串長度是否<=2 //如果小於2則隻用直接訪問位置的方式操作 if (valueLen <= 2) { //判斷字符串長度>0的場景 if (valueLen > 0) { //m_ChunkChars的已使用長度其實就是可以Append新元素的起始位置 //直接取value得第0個元素放入m_ChunkChars[可存儲的起始位置] chunkChars[chunkLength] = value[0]; } //其實是判斷字符串長度==2的場景 if (valueLen > 1) { //因為上面已經取瞭value第0個元素放入瞭m_ChunkChars中 //現在則取value得第1個元素繼續放入chunkLength的下一位置 chunkChars[chunkLength + 1] = value[1]; } } else { //如果value的長度大於2則通過操作內存去追加value //獲取m_ChunkChars的引用位置,偏移到m_ChunkLength的位置追加value Buffer.Memmove( ref Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(chunkChars), chunkLength), ref value.GetRawStringData(), (nuint)valueLen); } //更新以使用長度的值,新的使用長度是當前已使用長度+追加進來的字符串長度 m_ChunkLength = chunkLength + valueLen; } else { //走到這裡說明進入瞭擴容邏輯 AppendHelper(value); } } return this; }
這一部分邏輯主要展示瞭未達到擴容條件時候的邏輯,其本質就是將Append進來的字符串追加到m_ChunkChars數組裡去,其中m_ChunkLength代表瞭當前m_ChunkChars已經使用的長度,另一個含義也是代表瞭下一次Append進來元素存儲到m_ChunkLength的起始位置。而擴容的需要的邏輯則進入到瞭AppendHelper方法中,咱們看一下AppendHelper方法的實現[點擊查看源碼👈]
private void AppendHelper(string value) { unsafe { //防止垃圾收集器重新定位value變量。 //指針操作,string本身是不可變的char數組,所以它的指針是char* fixed (char* valueChars = value) { //調用瞭另一個append Append(valueChars, value.Length); } } }
這裡是獲取瞭傳遞進來的value指針然後調用瞭另一個重載的Append方法,不過從這段代碼中可以得到一個信息這個操作是非線程安全的。我們繼續找到另一個Append方法[點擊查看源碼👈]
public unsafe StringBuilder Append(char* value, int valueCount) { // value必須有值 if (valueCount < 0) { throw new ArgumentOutOfRangeException(); } //新的長度=StringBuilder的長度+需要追加的字符串長度 int newLength = Length + valueCount; //新的長度不能大於最大容量 if (newLength > m_MaxCapacity || newLength < valueCount) { throw new ArgumentOutOfRangeException(); } // 新的起始位置=需要追加的長度+當前使用的長度 int newIndex = valueCount + m_ChunkLength; // 判斷當前m_ChunkChars的容量是否夠用 if (newIndex <= m_ChunkChars.Length) { //夠用的話則直接將追加的元素添加到m_ChunkChars中去 new ReadOnlySpan<char>(value, valueCount).CopyTo(m_ChunkChars.AsSpan(m_ChunkLength)); //更新已使用的長度為新的長度 m_ChunkLength = newIndex; } //當前m_ChunkChars不滿足存儲則需要擴容 else { // 判斷當前存儲塊m_ChunkChars還有多少未存儲的位置 int firstLength = m_ChunkChars.Length - m_ChunkLength; if (firstLength > 0) { //把需要追加的value中的前firstLength位字符copy到m_ChunkChars中剩餘的位置 //合理的利用存儲空間,截取需要追加的value到m_ChunkChars剩餘的位置 new ReadOnlySpan<char>(value, firstLength).CopyTo(m_ChunkChars.AsSpan(m_ChunkLength)); //更新已使用的位置,這個時候當前存塊m_ChunkChars已經存儲滿瞭 m_ChunkLength = m_ChunkChars.Length; } // 獲取value中未放入到m_ChunkChars(因為當前塊已經放滿)剩餘部分起始位置 int restLength = valueCount - firstLength; //擴展當前存儲塊即擴容操作 ExpandByABlock(restLength); //判斷新的存儲塊是否創建成功 Debug.Assert(m_ChunkLength == 0, "A new block was not created."); // 將value中未放入到m_ChunkChars的剩餘部放入擴容後的m_ChunkChars中去 new ReadOnlySpan<char>(value + firstLength, restLength).CopyTo(m_ChunkChars); // 更新當前已使用長度 m_ChunkLength = restLength; } //一些針對當前StringBuilder的校驗操作,和相關邏輯無關不做詳細介紹 //類似的Debug.Assert(m_ChunkOffset + m_ChunkChars.Length >= m_ChunkOffset, "The length of the string is greater than int.MaxValue."); AssertInvariants(); return this; }
這裡的源代碼涉及到瞭一個StringBuilder的長度問題,Length代表著當前StringBuilder對象實際存放的字符長度,它的定義如下所示
public int Length { //StringBuilder已存儲的長度=塊的偏移量+當前塊使用的長度 get => m_ChunkOffset + m_ChunkLength; set { //註意這裡是有代碼的隻是我們暫時省略set邏輯 } }
上面源碼的這個Append方法其實是另一個重載方法,隻是Append(string? value)調用瞭這個邏輯,這裡可以清晰的看到,如果當前存儲塊滿足存儲,則直接使用。如果當前存儲位置不滿足存儲,那麼存儲空間也不會浪費,按照當前存儲塊的可用存儲長度去截取需要Append的字符串的長度,放入到這個存儲塊的剩餘位置,剩下的存儲不下的字符則存儲到擴容的新的存儲塊m_ChunkChars中去,這個做法就是為瞭不浪費存儲空間。
這一點考慮的非常周到,即使要發生擴容,那麼我當前節點的存儲塊也一定要填充滿,保證瞭存儲空間的最大利用。
通過上面的Append源碼我們自然可看出擴容的邏輯自然也就在ExpandByABlock方法中[點擊查看源碼👈]
//當前StringBuilder實際存儲的總長度 public int Length { //StringBuilder已存儲的長度=塊的偏移量+當前塊使用的長度 get => m_ChunkOffset + m_ChunkLength; set { //註意這裡是有代碼的隻是我們暫時省略set邏輯 } } //當前StringBuilder的總容量 public int Capacity { get => m_ChunkChars.Length + m_ChunkOffset; set { //註意這裡是有代碼的隻是我們暫時省略set邏輯 } } //可承載字符的最大容量,即可以拼接的字符串的長度 internal int m_MaxCapacity; //承載【拼接字符串的char數組 internal char[] m_ChunkChars; //當前塊的最大長度 internal const int MaxChunkSize = 8000; //當前m_ChunkChars字符數組中已經使用的長度 internal int m_ChunkLength; //存儲塊的偏移量,用於計算總長度 internal int m_ChunkOffset; //前一個存儲塊 internal StringBuilder? m_ChunkPrevious; private void ExpandByABlock(int minBlockCharCount) { //當前塊m_ChunkChars存儲滿才進行擴容操作 Debug.Assert(Capacity == Length, nameof(ExpandByABlock) + " should only be called when there is no space left."); //minBlockCharCount指的是剩下的需要存儲的長度 Debug.Assert(minBlockCharCount > 0); AssertInvariants(); //StringBuilder的總長度不能大於StringBuilder的m_MaxCapacity if ((minBlockCharCount + Length) > m_MaxCapacity || minBlockCharCount + Length < minBlockCharCount) { throw new ArgumentOutOfRangeException(); } //!!!需要擴容塊的新長度=max(當前追加字符的剩餘長度,min(當前StringBuilder長度,8000)) int newBlockLength = Math.Max(minBlockCharCount, Math.Min(Length, MaxChunkSize)); //判斷長度是否越界 if (m_ChunkOffset + m_ChunkLength + newBlockLength < newBlockLength) { throw new OutOfMemoryException(); } // 申請一個新的存塊長度為newBlockLength char[] chunkChars = GC.AllocateUninitializedArray<char>(newBlockLength); //!!!把當前StringBuilder中的存儲塊存放到一個新的StringBuilder實例中,當前實例的m_ChunkPrevious指向上一個StringBuilder //這裡可以看出來擴容的本質是構建節點為StringBuilder的鏈表 m_ChunkPrevious = new StringBuilder(this); //偏移量是每次擴容的時候去修改,它的長度就是記錄瞭已使用塊的長度,但是不包含當前StringBuilder的存儲塊 //可以理解為偏移量=長度-已經存放擴容塊的長度 m_ChunkOffset += m_ChunkLength; //因為已經擴容瞭新的容器所以重置已使用長度 m_ChunkLength = 0; //把新的塊重新賦值給當前存儲塊m_ChunkChars數組 m_ChunkChars = chunkChars; AssertInvariants(); }
這段代碼是擴容的核心操作,通過這個我們可以清晰的瞭解到StringBuilder的存儲本質
- 首先StringBuilder的數據存儲在m_ChunkChars字符數組中,但是擴容本質是單向鏈表操作,StringBuilder本身包含瞭m_ChunkPrevious指向的是上一個擴容時保存的數據。
- 然後StringBuilder每次擴容的長度是不固定的,實際的擴容長度是max(當前追加字符的剩餘長度,min(當前StringBuilder長度,8000)),由此我們可以以得知,一個塊m_ChunkChars數組的大小最大是8000。
StringBuilder還包含瞭一個通過StringBuilder構建實例的方法,這個構造函數就是給擴容時候構建單向鏈表使用的,它的實現也很簡單
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; AssertInvariants(); }
其目的就是把擴容之前的存儲相關的各種數據傳遞給新的StringBuilder實例。好瞭到目前為止Append的核心邏輯就說完瞭,我們大致捋一下Append的核心邏輯我們先大致羅列一下,舉個例子
- 1.默認情況m_ChunkChars[16],m_ChunkOffset=0,m_ChunkPrevious=null,Length=0
- 2.第一次擴容m_ChunkChars[16],m_ChunkOffset=16,m_ChunkPrevious=指向最原始的StringBuilder,m_ChunkLength=16
- 3.第二次擴容m_ChunkChars[32],m_ChunkOffset=32,m_ChunkPrevious=擴容之前的m_ChunkChars[16]的StringBuilder,m_ChunkLength=32
- 4.第三次擴容m_ChunkChars[64],m_ChunkOffset=64,m_ChunkPrevious=擴容之前的m_ChunkChars[64]的StringBuilder,m_ChunkLength=64
大概花瞭一張圖,不知道能不能輔助理解一下StringBuilder的數據結構,StringBuilder的鏈表結構是當前節點指向上一個StringBuilder,即當前擴容之前的StringBuilder的實例
c# StringBuilder整體的數據結構來說是一個單向鏈表,但是鏈表的每一個節點存儲塊是m_ChunkChars是
char[]
。擴容的本質就是給這個鏈表新增一個節點,每次擴容新增的節點存儲塊的容量都會增加。大部分使用時遇到的情況是首次為16、二次為16、三次為32、四次為64以此類推。
轉換成字符串
通過上面StringBuilder的數據結構我們瞭解到StringBuilder本質的數據結構是單向鏈表,這個單向鏈表包含m_ChunkPrevious
指向上一個StringBuilder實例,也就是一個倒序的鏈表。我們最終拿到StringBuilder的構建結果是通過StringBuilder的ToString()
方法進行的,得到最終的一個結果字符串,接下來我們就來看一下ToString的實現[點擊查看源碼👈]
//當前StringBuilder實際存儲的總長度 public int Length { //StringBuilder已存儲的長度=塊的偏移量+當前塊使用的長度 get => m_ChunkOffset + m_ChunkLength; set { //註意這裡是有代碼的隻是我們暫時省略set邏輯 } } public override string ToString() { AssertInvariants(); //當前StringBuilder長度為0則直接返回空字符串 if (Length == 0) { return string.Empty; } //FastAllocateString函數負責分配長度為StringBuilder長度的字符串 //這個字符串就是ToString最終返回的結果,所以長度等於StringBuilder的長度 string result = string.FastAllocateString(Length); //當前StringBuilder是遍歷的第一個鏈表節點 StringBuilder? chunk = this; do { //當前使用長度必須大於0,也就是說當前塊的m_ChunkChars必須使用過,才需要遍歷當前節點 if (chunk.m_ChunkLength > 0) { // 取出當前遍歷的StringBuilder的相關數據 // 當前遍歷StringBuilder的m_ChunkChars char[] sourceArray = chunk.m_ChunkChars; int chunkOffset = chunk.m_ChunkOffset; int chunkLength = chunk.m_ChunkLength; // 檢查是否越界 if ((uint)(chunkLength + chunkOffset) > (uint)result.Length || (uint)chunkLength > (uint)sourceArray.Length) { throw new ArgumentOutOfRangeException(); } //把當前遍歷項StringBuilder的m_ChunkChars逐步添加到result中當前結果的前端 Buffer.Memmove( ref Unsafe.Add(ref result.GetRawStringData(), chunkOffset), ref MemoryMarshal.GetArrayDataReference(sourceArray), (nuint)chunkLength); } //獲取當前StringBuilder的前一個節點,循環遍歷鏈表操作 chunk = chunk.m_ChunkPrevious; } //如果m_ChunkPrevious==null則代表是第一個節點 while (chunk != null); return result; }
關於這個ToString操作本質就是一個倒序鏈表的遍歷操作,每一次遍歷都獲取當前StringBuilder的m_ChunkPrevious字符數組
獲取數據拼接完成之後,獲取當前StringBuilder的上一個StringBuilder節點,即m_ChunkPrevious
的指向,結束的條件就是m_ChunkPrevious==null
說明該節點是首節點,最終拼接成一個string字符串返回。關於這個執行的遍歷過程大概可以理解為這麼一個過程,比如咱們的StringBuilder裡存放的是我和我的祖國一刻也不能分割,無論我走到哪裡都留下一首贊歌。,那麼針對ToString遍歷StringBuilder的遍歷過程則是大致如下的效果
//初始化一個等於StringBuilder長度的字符串 string result = "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"; //第一次遍歷後 result = "\0\0\0\0\0\0\0\0\0\0\0\0\0\0無論我走到哪裡都留下一首贊歌。"; //第二次遍歷後 result = "\0\0\0\0\0\0\0一刻也不能分割,無論我走到哪裡都留下一首贊歌。"; //第三次遍歷後 result = "\0\0\0我的祖國一刻也不能分割,無論我走到哪裡都留下一首贊歌。"; //第三次遍歷後 result = "我和我的祖國一刻也不能分割,無論我走到哪裡都留下一首贊歌。";
畢竟StringBuilder隻能記錄上一個StringBuilder的數據,因此這是一個倒序遍歷StringBuilder鏈表的操作,每次遍歷都是向前添加m_ChunkPrevious
中記錄的數據,直到m_ChunkPrevious==null
則遍歷完成直接返回結果。
c# StringBuilder類的ToString本質就是倒序遍歷單向鏈表,鏈表的的每一個node都是StringBuilder實例,獲取裡面的存儲塊
m_ChunkChars字符數組
進行拼裝,循環玩所有的節點之後把結果組裝成一個字符串返回。
對比java實現
我們可以看到在C#上StringBuilder的實現,本質是一個鏈表。那麼和C#語言類似的Java實現思路是否一致的,咱們大致看一下Java中StringBuilder的實現思路如何,我本地的jdk版本為1.8.0_191
,首先也是初始化邏輯
//存儲塊也就是承載Append數據的容器 char[] value; //StringBuilder的總長度 int count; public StringBuilder() { //默認的容量也是16 super(16); } public StringBuilder(String str) { //這個地方有差異如果通過指定字符串初始化StringBuilder //則初始化的長度則是當前傳遞的str的長度+16 super(str.length() + 16); append(str); } // AbstractStringBuilder.java AbstractStringBuilder(int capacity) { value = new char[capacity]; }
在這裡可以看到java的初始化容量的邏輯和c#有點不同,c#默認的初始化長度取決於能存儲初始化字符串的長度為主,而java的實現則是在當前長度上+16的長度,也就是無論如何這個初始化的16的長度必須要有。那麼我們再來看一下append的實現源碼
// AbstractStringBuilder.java public AbstractStringBuilder append(String str) { if (str == null) return appendNull(); int len = str.length(); // 這裡是擴容操作 ensureCapacityInternal(count + len); str.getChars(0, len, value, count); //每次append之後重新設置長度 count += len; return this; }
核心的是擴容ensureCapacityInternal的方法,咱們簡單的看下它的實現
private void ensureCapacityInternal(int minimumCapacity) { //當前需要的長度>char[]的長度則需要擴容 if (minimumCapacity - value.length > 0) expandCapacity(minimumCapacity); } void expandCapacity(int minimumCapacity) { //新擴容的長度是當前塊char[]的長度的2倍+2 int newCapacity = value.length * 2 + 2; if (newCapacity - minimumCapacity < 0) newCapacity = minimumCapacity; if (newCapacity < 0) { if (minimumCapacity < 0) throw new OutOfMemoryError(); newCapacity = Integer.MAX_VALUE; } //把當前的char[]復制到新擴容的字符數組中 value = Arrays.copyOf(value, newCapacity); } // Arrays.java copy的邏輯 public static char[] copyOf(char[] original, int newLength) { //聲明一個新的數組,把original的數據copy到新的char數組中 char[] copy = new char[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }
最後要展示的則是得到StringBuilder結果的操作,同樣是toString方法,咱們看一下java中這個邏輯的實現
@Override public String toString() { // 這裡創建瞭一個新的String對象返回,通過當前char[]初始化這個字符串 return new String(value, 0, count); }
到瞭這裡關於java中StringBuilder的實現邏輯相信大傢都看的非常清楚瞭,這裡和c#的實現邏輯確實是不太一樣,本質的底層數據結構都是不一樣的,這裡咱們簡單的羅列一下它們實現方式的不同
- c#中StringBuilder的雖然真正數據存儲在
m_ChunkChars字符數組
,但整體的數據結構是單向鏈表,java中則完全是char[]
字符數組。 - c#中StringBuilder的初始長度是可容納當前初始化字符串的長度,java的初始化長度則是當前傳遞的字符串長度+16。
- c#中StringBuilder的擴容是生成一個新的StringBuilder實例,容量和上一個StringBuilder長度有關。java則是生成一個是原來
char[]數組長度*2+2
長度的新數組。 - c#中ToString的實現是遍歷倒序鏈表組裝一個新的字符串返回,java上則是用當前StringBuilder的
char[]
初始化一個新的字符串返回。
關於c#和java的StringBuilder實現方式差異如此之大,到底哪種實現方式更優一點呢?這個沒辦法評價,畢竟每一門語言的底層類庫實現都是經過深思熟慮的,集成瞭很多人的思想。在樓主的角度來看StringBuilder本身的核心功能在於構建的過程,所以構建過程的性能非常重要,所以類似數組擴容再copy的邏輯沒有鏈表的方式高效。但是在最後的ToString得到結果的時候,數組的優勢是非常明顯的,畢竟string本質就是一個char[]數組
。
對於StringBuilder來說append是頻繁操作大部分情況可能多次進行append操作,而ToString操作對於StringBuilder來說基本上隻有一次,那就是得到StringBuilder構建結果的時候。所以樓主覺得提升append的性能是關鍵。
總結
本文我們主要講解瞭c# StringBuilder的大致的實現方式,同時也對比瞭c#和java關於實現方式的StringBuilder的不同,主要差異是c#實現的底層數據結構為單向鏈表,但是每一個節點的數據存儲在char[]
中,java實現的方式則整體都是數組。這也為我們提供瞭不同的思路,在這裡我們也再次總結一下它的實現方式
- c# StringBuilder的本質是單向鏈表操作,StringBuilder本身包含瞭
m_ChunkPrevious
指向的是上一個擴容時保存的數據,擴容的本質就是給這個鏈表新增一個節點。 - c# StringBuilder每次擴容的長度是不固定的,實際的擴容長度是
max(當前追加字符的剩餘長度,min(當前StringBuilder長度,8000))
,每次擴容新增的節點存儲塊的容量都會增加。大部分使用時遇到的情況是首次為16、二次為16、三次為32、四次為64以此類推。 - c# StringBuilder類的ToString本質就是倒序遍歷單向鏈表,每一次遍歷都獲取當前StringBuilder的
m_ChunkPrevious字符數組
獲取數據拼接完成之後,然後獲取m_ChunkPrevious
指向的上一個StringBuilder實例,最終把結果組裝成一個字符串返回。 - 關於c#和java實現StringBuilder存在很大差異,主要差異是c#實現的整體底層數據結構為單向鏈表,但是每個StringBuilder實例中數據本身存儲在
char[]
中,這種數據結構有點像redis的quicklist
。java實現的整體方式則都是char[]
字符數組。
雖然大傢都說越努力越幸運,有時候我們努力是為瞭讓自己更幸運。但是我更喜歡的是,我們努力不僅僅是為瞭幸運,而是讓我們的心裡更踏實,結果固然重要,然而許多時候努力過瞭也就問心無愧瞭。
到此這篇關於C#字符串構建利器StringBuilder的文章就介紹到這瞭,更多相關C#字符串構建利器StringBuilder內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Java StringBuilder的用法示例
- 淺談StringBuilder類的capacity()方法和length()方法的一些小坑
- Java常用類之字符串相關類使用詳解
- Java實用工具之StringJoiner詳解
- Java線性表的順序表示及實現