StringBuilder/StringBuffer可变长原理

2022-07-08 14:08:55

1. 概述

StringBuffer 与StringBuilder 都是可变字符序列（字符串）。
不同的是StringBuilder 非线程安全，StringBuffer 线程安全。
查看源码可以发现，StringBuffer 除构造外的其他方法都直接或间接（重载）用synchronized 修饰。
这里主要讨论可变长，也就是扩容原理，以StringBuilder 为例，StringBuffer 与之一致。

2. StringBuilder 的构造方法

// 类定义publicfinalclassStringBuilderextendsAbstractStringBuilderimplementsjava.io.Serializable, CharSequence{// StringBuilder 的构造publicStringBuilder(){super(16);}publicStringBuilder(int capacity){super(capacity);}publicStringBuilder(String str){super(str.length()+16);append(str);}publicStringBuilder(CharSequence seq){this(seq.length()+16);append(seq);}......}
4 种构造方法都使用了父类AbstractStringBuilder 的构造器。
除了第二种构造外，其他构造种都带有醒目的 16 ，换算后正好是 $2^4$ ，感觉没啥联系，emm。
无参构造，默认传参 16。
参数为 int 类型的构造，传参就为指定的 int 值。
参数为 String 类型的构造，传参为 String 的长度 + 16。
参数为 CharSequence 类型的构造，调用的是参数为 int 的构造，最终传参为 CharSequence 的长度 + 16。

3. AbstractStringBuilder 构造方法

abstractclassAbstractStringBuilderimplementsAppendable, CharSequence{/* The value is used for character storage. *//*  value 用于存放字符 */char[] value;/* The count is the number of characters used. *//* count 是有效字符个数 */int count;AbstractStringBuilder(){}AbstractStringBuilder(int capacity){
       value=newchar[capacity];}......}
AbstractStringBuilder 有两个构造方法重载，一个无参构造，一个带 int 类型参数的构造。
前面StringBuilder 中都使用的是带参构造。
看到new char[capacity]，心里一下就踏实了，与String 一样，底层都是char 数组，长度就是前面传递过来的长度，不同的是这里没有使用final 关键字修饰。

对于StringBuilder 的初始化结论如下：
对于无参构造，初始大小为：16
对于传入 int 类型的构造，初始大小为：指定的 int 值
对于传入String 类型和CharSequence 类型的构造，初始大小为：字符序列长度 + 16

4. 扩容机制

添加新字符时可能会导致原数组溢出，这时需要对原数组进行扩容，确保新的数组能够容纳新添加的字符序列。
扩容是发生在添加操作前的动作，所以不得不提append() 方法，如下图：
有许多重载方法，针对不同类型做不同处理，都大同小异，这里使用添加 String 类型作为示例，定义如下：
@Overridepublic StringBuilderappend(String str){super.append(str);returnthis;}
这里重写了父类的方法，但真正调用的，还是父类中的方法，定义如下：
public AbstractStringBuilderappend(String str){if(str== null)returnappendNull();int len= str.length();ensureCapacityInternal(count+ len);
   str.getChars(0, len, value, count);
   count+= len;returnthis;}
先处理了 String 为 null 的情况，调用的是 appendNull() 方法，
private AbstractStringBuilderappendNull(){int c= count;ensureCapacityInternal(c+4);finalchar[] value=this.value;
   value[c++]='n';
   value[c++]='u';
   value[c++]='l';
   value[c++]='l';
   count= c;returnthis;}
可以发现，不管是append() 还是appendNull() 方法，里面都有一个方法ensureCapacityInternal()，且传递的参数都是count + 字符长度，这个就是用于扩容的方法，它内部的实现如下：
privatevoidensureCapacityInternal(int minimumCapacity){// overflow-conscious codeif(minimumCapacity- value.length>0){
       value= Arrays.copyOf(value,newCapacity(minimumCapacity));}}
参数minimumCapacity 就是count + 待添加字符序列的长度，如果这个值比原数组的长度小，说明还未存满，不做任何处理。
反之则需要扩容了，可以看到扩容操作是基于Arrays.copyOf() 实现的，新数组的长度由newCapacity() 获取，在进入这个方法之前，需要先对参数minimumCapacity 做进一步的解释。
前面提到minimumCapacity 是count + 待添加字符序列的长度，关于 count，它在AbstractStringBuilder 中的有声明，表示的是字符数组value 中有效字符的个数，即已存储字符的个数。
令人费解的是，基本类型必须初始化才能使用，但我未能找到count 初始化相关的代码，只好将它作为默认值 0 处理。【已解决】
【基本类型作为成员变量时，Java 会自动为其设置默认值】
知道minimumCapacity 的参数的含义后，继续看newCapacity(minimumCapacity) 方法，它的定义如下：
privateintnewCapacity(int minCapacity){// overflow-conscious codeint newCapacity=(value.length<<1)+2;if(newCapacity- minCapacity<0){
       newCapacity= minCapacity;}return(newCapacity<=0|| MAX_ARRAY_SIZE- newCapacity<0)?hugeCapacity(minCapacity): newCapacity;}
进入方法的第一件事就是定义新数组的大小int newCapacity = (value.length << 1) + 2;
value.length<<1 等价于value.length *= 2，所以扩容后数组的大小为原数组的大小(value.length) * 2 + 2。
众所周知， int 类型指的是 10 进制的整数，但在计算机中，它是以二进制存储的。
还记得初学 Java 时，老师教的 int 类型占 4 个字节大小吗？
4 byte == 32 bit，所以 int 的取值范围 $2^{31} ,{2^{31} - 1}]$
说了一堆，就是为了铺垫出 int 表面上是 10 进制，背地里却是二进制，可以将其当作二进制处理。
所以value.length<<1 是将整体像高位移动了一位，就如同十进制的 10 变成了 100，扩大的 10 倍，同理二进制的 0010 变成 0100，扩大了 2 倍，由此得出每次扩容后的大小为原数组的长度 * 2 + 2

5. 总结

1、 StringBuilder 或 StringBuffer 的初始化分配的空间大小取决于调用的构造方法：
无参构造默认大小为 16
调用 int 类型参数构造，初始化大小为指定的 int 值。（更推荐这种方式，可以减少扩容次数，提高效率。）
调用 String 类型或 CharSequence 类型参数的构造，初始化大小为：字符序列的长度 + 16

2、扩容机制每次扩容大小为：原数组大小 * 2 + 2

3、补充：
StringBuilder 调用 length() 方法时，返回值为有效字符个数，它的源码如下：
@Overridepublicintlength(){return count;}