浅谈stringBuilder.ToString()方法底层原理代码解析（C#/JAVA）

一、什么是单向链表？

首先我们要知道，三个StringBuilder的关系是单向链表，那么什么是单向链表呢？

链表是一种特殊的数据结构，能够动态的存储一种结构类型数据。
该结构由节点组成。每个节点包含两个部分数据：

• 第一部分（尾节点）：节点本身的数据
• 第二部分（头节点）：指向下一个节点的指针（整个stringBuilder对象的地址

单向链表就是C# 的 StringBuilder扩容机制。它的容量和上一个stringBuilder长度有关，每次扩容不固定：max(当前追加字符的剩余长度,min(当前StringBuilder长度,8000))

---

二、ToString（）底层区别（C#/Java）

C#

下面我画了一下单向链表的调用关系，如图所示：

从图中可以看出来，引用关系总结了以下几步：

1. 声明的builder绑定的是而stringBuilderC的堆地址0x0003，节点头存放着地址，就叫做单向链表。
2. 而stringBuilderC头节点存放了stringBuilderB堆地址0x0002，
3. stringBuilderB存放的是stringBuilderA的堆地址0x0001。
4. 到这里就发现stringBuilderA的头节点就没有存放下一个节点的指针，这也就说明了char[ ]到头了，A就是一堆扩容数组中的领头。
   在ToString()时，也会根据这个顺序，倒序遍历出各自的元素，组成在一起。

以上是 C# 中stringBuilder扩容机制（单向链表），在ToString()时，会根据这个单向链表顺序，开辟新空间倒序遍历出各自的元素，组成在一起。

Java

扩容机制如图所示：

Java的stringBuilder扩容机（char[ ]数组），从图中就可以看出来和C#的区别。但是，Java在ToString()时开辟新空间（也就是String对象），人家本身就存储在char[ ]数组中。转换的时候将之前的数组内容复制过去，不需要倒序遍历。所以最后ToString（）输出 Java的StringBuilder优势是非常明显的。

两者区别

针对于更多的区别，可以通过一下链接点进去看看，比较全面一些：

链接: String、StringBuilder实现原理、toString方法（ JAVA / C# ）

---

二、ToString底层代码解析（JAVA / C#）

C#底层代码

假设
设定条件：初始值char[16]
现有三个stringBuilder：char[16]stringBuilderA、char[ ]stringBuilderB、char[ ]stringBuilderC

首次 .Append（“16个字符”）；（也就是stringBuilderA）
二次 .Append(“16个字符”)；（扩容出来的stringBuilderB，元素存放在里面）
三次 .Append（“2个字符”）；（扩容出来的stringBuilderC，Append的2个元素存放在里面）

以这种情况为前提，咱走近底层实现代码研究研究（vs2022版可以看见更多的底层实现代码，它给我们开放了一些）：

> 核心步骤一，长度相关：
 public int Length
{
    [__DynamicallyInvokable]
    get
    {
     /******** 新建stringBuilder时，会有两个参数（offset+数组长度）*********/
      return m_ChunkOffset + m_ChunkLength;    
    }
}


> 核心步骤一，ToString()倒序遍历：
// 已标注：不安全的方法（C#默认不让使用指针，想要用指针，需要标注一下，谨防安全隐患）
public unsafe override string ToString()/
{
   if (Length == 0)
   {
   	return string.Empty;
   }
   
   // 新开辟一个新的数组空间，长度是64的：FastAllocateString（16+16+32=64）
   string text = string.FastAllocateString(Length);
   StringBuilder stringBuilder = this;
	
	// fixed 使用指针的关键字
   fixed (char* ptr = text) // 新开辟空间的数组，堆地址赋给指针变量ptr
   {
   // 整个 do-while 倒序遍历单向链表 
   // 顺序：stringBuilderC → stringBuilderB → stringBuilderC
   //顺序是和挂钩的，变量builder引用地址是stringBuilderC的0x0003。以此类推
     do
     {
       if (stringBuilder.m_ChunkLength > 0)
       {
         char[] chunkChars = stringBuilder.m_ChunkChars;
         int chunkOffset = stringBuilder.m_ChunkOffset;
         int chunkLength = stringBuilder.m_ChunkLength;
		 
		 // 长度超出了int最大值或者大于新开辟空间的长度
		 //例如数组长度刚刚好是int最大值，这个后Append两个字符
         if ((uint)(chunkLength + chunkOffset) > text.Length 
		 		     ||
		          (uint)chunkLength > (uint)chunkChars.Length)
         {
            throw new ArgumentOutOfRangeException("chunkLength", Environment.GetResourceString("ArgumentOutOfRange_Index"));
         }

         // 当前stringBuilder它的char[]的指针，堆地址赋给指针变量smem
         //例如首次循环的第三个char[] stringBuilderC
         fixed (char* smem = chunkChars)
         {
          // CLR公共语言运行时 原生提供（copy），将当前char[]元素克隆到新开辟的空间去
		  // ptr + chunkOffset:ptr指的是开头，第三个char[]是放在后面位置的，所以要添加偏移量offset
		  // smem:当前char[]数组指针（引用地址）
		 // chunkLength： 当前char[]数组被使用的长度（被占用）
            string.wstrcpy(ptr + chunkOffset, smem, chunkLength);
         }
        }
	    // stringBuilder = 上一个stringBuilder（也就是第二个stringBuilder）
        stringBuilder = stringBuilder.m_ChunkPrevious;
     }
    while (stringBuilder != null);
  }
  // 最后都添加到最初新开辟的空间数组里去：test
  return text;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

画了一个上面的实现图，希望有所帮助：

Java底层代码

下面是我用的jkd1.8，java中自带的我们可以看到的底层代码。对它进行拆分分析。

> 步骤一，方法：
public String toString() 
{
  return new String(value, 0, count);
}

> 步骤二，条件筛选：
public String(char value[], int offset, int count)
 {
//以下代码判断偏移量或者count（你要复制的元素数量）组合，会不会超出数组的索引
    if (offset < 0) { throw new StringIndexOutOfBoundsException(offset); }
    if (count <= 0)
    {
        if (count < 0) { throw new StringIndexOutOfBoundsException(count); }
        if (offset <= value.length) { this.value = "".value; return;  } 
     }
    if (offset > value.length - count) {  throw new StringIndexOutOfBoundsException(offset + count); }

//如果没有查出索引边界，则进入核心代码：copy相关
	//offset（偏移量）：从那里开始
	//count（数量）：你要复制多少个 
    this.value = Arrays.copyOfRange(value, offset, offset+count);
}


> 步骤三，核心代码：
public static char[] copyOfRange(char[] original, int from, int to)
 {
    //新长度=offset+count-offset   也就是count（我也不知道为什么要这么写，为啥子这么绕0.0）
    int newLength = to - from;
    
 	if (newLength < 0)
        throw new IllegalArgumentException(from + " > " + to);
        
    //new了一个新数组，把刚才的count赋值给这个新数组
 	char[] copy = new char[newLength];
 	
 	//arraycopy(原来的数组, 偏移量, 新数组, 0, 两个选最小(原来数组长度-偏移量, 新数组长度))
  	System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength));
  	
  	//返回新数组
	return copy;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

从代码中可以看出来，java在ToString() 时，也是会开辟一个新空间（也就是创建新数组），但是java的不需要进行倒序遍历。
因为本身就是存储在char[ ]内的，所以最后ToString()是直接将原来的数组copy给新创建的数组中，然后进行返回的。

小结

C# 的StringBuilder是单向链表，扩容的时候挺好，充分利用空间，保证了存储空间的最大利用。但是最后ToString（）需要循环倒序遍历，最终把结果组装成一个字符串返回。


JAVA 的StringBuilder 是 char[ ] 类型的，扩容的时候，会生成一个新的数组并且克隆旧数组中的元素到自己里面。之前的旧数组没人引用就会等待垃圾回收。

所以，类似数组扩容再copy的逻辑没有链表的方式高效。

最后输出结果的时候因为本身存储在char[ ]中，所以随后输出 Java的StringBuilder优势是非常明显的。

推荐内容

---

• string/StringBuilder/ToString()底层代码解析（ JAVA / C# ）
  C# /JAVA: 字符串构建利器StringBuilder区别，附有C# /JAVA 底层源码分析。

---

• string/stringBuilder常量池（驻留池） java/C#学习
  JAVA / C# 详解之：运行时常量池