前言
在日常的开发中 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 的有参数的构造函数有好几个,如下所示
//声明初始化容量,即首次扩容触发的长度条件
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[]
字符数组。
虽然大家都说越努力越幸运,有时候我们努力是为了让自己更幸运。但是我更喜欢的是,我们努力不仅仅是为了幸运,而是让我们的心里更踏实,结果固然重要,然而许多时候努力过了也就问心无愧了。
评论