计算机程序的思维逻辑 (30) - 剖析StringBuilder

本系列文章经补充和完善,已修订整理成书《Java编程的逻辑》,由机械工业出版社华章分社出版,于2018年1月上市热销,读者好评如潮!各大网店和书店有售,欢迎购买,京东自营链接http://item.jd.com/12299018.html

计算机程序的思维逻辑 (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方法

StringBuilder还有两个构造方法,分别接受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);//增补字符:
上一篇:(十)Python装饰器


下一篇:python装饰器学习详解-函数部分