(30) 剖析StringBuilder / 计算机程序的思维逻辑
(30) 剖析StringBuilder / 计算机程序的思维逻辑
上节介绍了String，提到如果字符串修改操作比较频繁，应该采用StringBuilder和StringBuffer类，这两个类的方法基本是完全一样的，它们的实现代码也几乎一样，唯一的不同就在于，StringBuffer是线程安全的，而StringBuilder不是。
线程以及线程安全的概念，我们在后续章节再详细介绍。这里需要知道的就是，线程安全是有成本的，影响性能，而字符串对象及操作，大部分情况下，没有线程安全的问题，适合使用StringBuilder。所以，本节就只讨论StringBuilder。
StringBuilder的基本用法也是很简单的，我们来看下。
基本用法
创建StringBuilder
StringBuilder sb = new StringBuilder();
添加字符串，通过append方法
sb.append("老马说编程");
sb.append(",探索编程本质");获取构建后的字符串，通过toString方法
System.out.println(sb.toString());
输出为：
老马说编程,探索编程本质
大部分情况，使用就这么简单，通过new新建StringBuilder，通过append添加字符串，然后通过toString获取构建完成的字符串。
StringBuilder是怎么实现的呢？
基本实现原理
内部组成和构造方法
与String类似，StringBuilder类也封装了一个字符数组，定义如下：
char[] value;
与String不同，它不是final的，可以修改。另外，与String不同，字符数组中不一定所有位置都已经被使用，它有一个实例变量，表示数组中已经使用的字符个数，定义如下：
int count;StringBuilder继承自AbstractStringBuilder，它的默认构造方法是：
public StringBuilder() {
super(16);
}
调用父类的构造方法，父类对应的构造方法是：
AbstractStringBuilder(int capacity) {
value = new char[capacity];
}也就是说，new StringBuilder()这句代码，内部会创建一个长度为16的字符数组，count的默认值为0。
append的实现
来看append的代码：
public AbstractStringBuilder append(String str) {
if (str == null) str = "null";
int len = str.length();
ensureCapacityInternal(count + len);
str.getChars(0, len, value, count);
count += len;
return this;
}
append会直接拷贝字符到内部的字符数组中，如果字符数组长度不够，会进行扩展，实际使用的长度用count体现。具体来说，ensureCapacityInternal(count+len)会确保数组的长度足以容纳新添加的字符，str.getChars会拷贝新添加的字符到字符数组中，count+=len会增加实际使用的长度。
ensureCapacityInternal的代码如下：
private void ensureCapacityInternal(int minimumCapacity) {
// overflow-conscious code
if (minimumCapacity - value.length > 0)
expandCapacity(minimumCapacity);
}
如果字符数组的长度小于需要的长度，则调用expandCapacity进行扩展，expandCapacity的代码是：
void expandCapacity(int minimumCapacity) {
int newCapacity = value.length * 2 + 2;
if (newCapacity - minimumCapacity < 0)
newCapacity = minimumCapacity;
if (newCapacity < 0) {
if (minimumCapacity < 0) // overflow
throw new OutOfMemoryError();
newCapacity = Integer.MAX_VALUE;
}
value = Arrays.copyOf(value, newCapacity);
}
扩展的逻辑是，分配一个足够长度的新数组，然后将原内容拷贝到这个新数组中，最后让内部的字符数组指向这个新数组，这个逻辑主要靠下面这句代码实现：
value = Arrays.copyOf(value, newCapacity);下节我们讨论Arrays类，本节就不介绍了，我们主要看下newCapacity是怎么算出来的。
参数minimumCapacity表示需要的最小长度，需要多少分配多少不就行了吗？不行，因为那就跟String一样了，每append一次，都会进行一次内存分配，效率低下。这里的扩展策略，是跟当前长度相关的，当前长度乘以2，再加上2，如果这个长度不够最小需要的长度，才用minimumCapacity。
比如说，默认长度为16，长度不够时，会先扩展到16*2+2即34，然后扩展到34*2+2即70，然后是70*2+2即142，这是一种指数扩展策略。为什么要加2？大概是因为在原长度为0时也可以一样工作吧。
为什么要这么扩展呢？这是一种折中策略，一方面要减少内存分配的次数，另一方面也要避免空间浪费。在不知道最终需要多长的情况下，指数扩展是一种常见的策略，广泛应用于各种内存分配相关的计算机程序中。
那如果预先就知道大概需要多长呢？可以调用StringBuilder的另外一个构造方法：
public StringBuilder(int capacity)
toString实现
字符串构建完后，我们来看toString代码：
public String toString() {
// Create a copy, don't share the array
return new String(value, 0, count);
}基于内部数组新建了一个String，注意，这个String构造方法不会直接用value数组，而会新建一个，以保证String的不可变性。
更多构造方法和append方法
String还有两个构造方法，分别接受String和CharSequence参数，它们的代码分别如下：
public StringBuilder(String str) {
super(str.length() + 16);
append(str);
}
public StringBuilder(CharSequence seq) {
this(seq.length() + 16);
append(seq);
}
逻辑也很简单，额外多分配16个字符的空间，然后调用append将参数字符添加进来。
append有多种重载形式，可以接受各种类型的参数，将它们转换为字符，添加进来，这些重载方法有：
public StringBuilder append(boolean b)
public StringBuilder append(char c)
public StringBuilder append(double d)
public StringBuilder append(float f)
public StringBuilder append(int i)
public StringBuilder append(long lng)
public StringBuilder append(char[] str)
public StringBuilder append(char[] str, int offset, int len)
public StringBuilder append(Object obj)
public StringBuilder append(StringBuffer sb)
public StringBuilder append(CharSequence s)
public StringBuilder append(CharSequence s, int start, int end)具体实现比较直接，就不赘述了。
还有一个append方法，可以添加一个Code Point：
public StringBuilder appendCodePoint(int codePoint)
如果codePoint为BMP字符，则添加一个char，否则添加两个char。如果不清楚Code Point的概念，请参见剖析包装类 (下)。
其他修改方法
除了append, StringBuilder还有一些其他修改方法，我们来看下。
插入
public StringBuilder insert(int offset, String str)
在指定索引offset处插入字符串str，原来的字符后移，offset为0表示在开头插，为length()表示在结尾插，比如说：
StringBuilder sb = new StringBuilder();
sb.append("老马说编程");
sb.insert(0, "关注");
sb.insert(sb.length(), "老马和你一起探索编程本质");
sb.insert(7, ",");
System.out.println(sb.toString());
输出为
关注老马说编程,老马和你一起探索编程本质
来看下insert的实现代码：
public AbstractStringBuilder insert(int offset, String str) {
if ((offset < 0) || (offset > length()))
throw new StringIndexOutOfBoundsException(offset);
if (str == null)
str = "null";
int len = str.length();
ensureCapacityInternal(count + len);
System.arraycopy(value, offset, value, offset + len, count - offset);
str.getChars(value, offset);
count += len;
return this;
}
这个实现思路是，在确保有足够长度后，首先将原数组中offset开始的内容向后挪动n个位置，n为待插入字符串的长度，然后将待插入字符串拷贝进offset位置。
挪动位置调用了System.arraycopy方法，这是个比较常用的方法，它的声明如下：
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);将数组src中srcPos开始的length个元素拷贝到数组dest中destPos处。这个方法有个优点，即使src和dest是同一个数组，它也可以正确的处理，比如说，看下面代码：
int[] arr = new int[]{1,2,3,4};
System.arraycopy(arr, 1, arr, 0, 3);
System.out.println(arr[0]+","+arr[1]+","+arr[2]);
这里，src和dest都是arr，srcPos为1，destPos为0，length为3，表示将第二个元素开始的三个元素移到开头，所以输出为：
2,3,4
arraycopy的声明有个修饰符native，表示它的实现是通过Java本地接口实现的，Java本地接口是Java提供的一种技术，用于在Java中调用非Java语言实现的代码，实际上，arraycopy是用C++语言实现的。为什么要用C++语言实现呢？因为这个功能非常常用，而C++的实现效率要远高于Java。
其他插入方法
与append类似，insert也有很多重载的方法，如下列举一二
public StringBuilder insert(int offset, double d)
public StringBuilder insert(int offset, Object obj)删除
删除指定范围内的字符
public StringBuilder delete(int start, int end)
其实现代码为：
public AbstractStringBuilder delete(int start, int end) {
if (start < 0)
throw new StringIndexOutOfBoundsException(start);
if (end > count)
end = count;
if (start > end)
throw new StringIndexOutOfBoundsException();
int len = end - start;
if (len > 0) {
System.arraycopy(value, start+len, value, start, count-end);
count -= len;
}
return this;
}
也是通过System.arraycopy实现的，System.arraycopy被大量应用于StringBuilder的内部实现中，后文就不再赘述了。
删除一个字符
public StringBuilder deleteCharAt(int index)
替换
public StringBuilder replace(int start, int end, String str)如
StringBuilder sb = new StringBuilder();
sb.append("老马说编程");
sb.replace(3, 5, "Java");
System.out.println(sb.toString());
程序输出为：
老马说Java
替换一个字符
public void setCharAt(int index, char ch)
翻转字符串
public StringBuilder reverse()这个方法不只是简单的翻转数组中的char，对于增补字符，简单翻转后字符就无效了，这个方法能保证其字符依然有效，这是通过单独检查增补字符，进行二次翻转实现的。比如说：
StringBuilder sb = new StringBuilder();
sb.append("a");
sb.appendCodePoint(0x2F81A);//增补字符：?
sb.append("b");
sb.reverse();
System.out.prrrintln(sb.toString());
即使内含增补字符"?"，输出也是正确的，为：
b?a
长度方法
StringBuilder中有一些与长度有关的方法
确保字符数组长度不小于给定值
public void ensureCapacity(int minimumCapacity)返回字符数组的长度
public int capacity() 返回数组实际使用的长度
public int length()注意capacity()方法与length()方法的的区别，capacity返回的是value数组的长度，length返回的是实际使用的字符个数，是count实例变量的值。
直接修改长度
public void setLength(int newLength)
代码为：
public void setLength(int newLength) {
if (newLength < 0)
throw new StringIndexOutOfBoundsException(newLength);
ensureCapacityInternal(newLength);
if (count < newLength) {
for (; count < newLength; count++)
value[count] = '\0';
} else {
count = newLength;
}
}count设为newLength，如果原count小于newLength，则多出来的字符设置默认值为'\0'。
缩减使用的空间
public void trimToSize()代码为：
public void trimToSize() {
if (count < value.length) {
value = Arrays.copyOf(value, count);
}
}减少value占用的空间，新建了一个刚好够用的空间。
与String类似的方法
StringBuilder中也有一些与String类似的方法，如：
查找子字符串
public int indexOf(String str)
public int indexOf(String str, int fromIndex)
public int lastIndexOf(String str)
public int lastIndexOf(String str, int fromIndex)
取子字符串
public String substring(int start)
public String substring(int start, int end)
public CharSequence subSequence(int start, int end)获取其中的字符或Code Point
public char charAt(int index)
public int codePointAt(int index)
public int codePointBefore(int index)
public int codePointCount(int beginIndex, int endIndex)
public void getChars(int srcBegin, int srcEnd, char[] dst, int dstBegin)以上这些方法与String中的基本一样，本节就不再赘述了。
String的+和+=运算符
Java中，String可以直接使用+和+=运算符，这是Java编译器提供的支持，背后，Java编译器会生成StringBuilder，+和+=操作会转换为append。比如说，如下代码：
String hello = "hello";
hello+=",world";
System.out.println(hello);背后，Java编译器会转换为：
StringBuilder hello = new StringBuilder("hello");
hello.append(",world");
System.out.println(hello.toString());
既然直接使用+和+=就相当于使用StringBuilder和append，那还有什么必要直接使用StringBuilder呢？在简单的情况下，确实没必要。不过，在稍微复杂的情况下，Java编译器没有那么智能，它可能会生成很多StringBuilder，尤其是在有循环的情况下，比如说，如下代码：
String hello = "hello";
for(int i=0;i<3;i++){
hello+=",world";
}
System.out.println(hello);
Java编译器转换后的代码大概如下所示：
String hello = "hello";
for(int i=0;i<3;i++){
StringBuilder sb = new StringBuilder(hello);
sb.append(",world");
hello = sb.toString();
}
System.out.println(hello);
在循环内部，每一次+=操作，都会生成一个StringBuilder。
所以，结论是，对于简单的情况，可以直接使用String的+和+=，对于复杂的情况，尤其是有循环的时候，应该直接使用StringBuilder。
小结
本节介绍了StringBuilder，介绍了其用法，实现原理，数组长度扩展策略，以及String的+和+=操作符的实现原理。
字符串操作是计算机程序中最常见的操作，理解了String和StringBuilder的用法及实现原理，我们就对字符串操作建立了一个坚实的基础。
上节和本节，我们都提到了一个类Arrays，它包括很多数组相关的方法，数组操作也是非常常见的操作，让我们下节来详细讨论。