引言

前一篇文章讲解了java中的String类，String类最重要的特性就是不可变性，很多需要对其字符序列进行修改的方法都会创建新的字符串对象，这样保证了字符串的线程安全，但是对于一些操作，例如大量的字符串拼接，可能会消耗性能，StringBuilder和StringBuffer作为可变字符序列的实现，在很多操作上可以替代String，在讲解StringBuilder之前，我们先讲解整个类层次结构中的几个重要的类。

StringBuilder和StringBuffer类的层次结构

StringBuilder类的定义如下：

public final class StringBuilder
    extends AbstractStringBuilder
    implements java.io.Serializable, CharSequence

它继承了AbstractStringBuilder这个抽象类，实现了Serializable和CharSequence接口。再看AbstractStringBuilder这个类，这是一个抽象类，实现了Appendable和CharSequence两个接口，所以整个的层次是这样的：
其实StringBuffer也是这样的类层次结构，所以图中把StringBuffer也加上了。
StringBuffer和StringBuilder中的大部分方法都是在AbstractStringBuilder中实现的。我们重点来看一下这个抽象类。

AbstractStringBuilder

/**
 * A mutable sequence of characters.
 * <p>
 * Implements a modifiable string. At any point in time it contains some
 * particular sequence of characters, but the length and content of the
 * sequence can be changed through certain method calls.
 */
abstract class AbstractStringBuilder implements Appendable, CharSequence {}

AbstractStringBuilder代表一个可变的字符数组。它实现了一个可修改的字符串，在任何时间它都包含一些特定的字符序列，但是这个序列的长度和内容都可以通过特定的方法调用被修改。
在分析String的文章中，我们介绍了CharSequence这个接口，它提供了对字节序列的只读访问，而Appendable就提供了对字节数组的可写访问，实现了这两个接口之后，AbstractStringBuilder就能对字节数组进行读和写操作了，我们首先来看Appendable的实现。

Appendable接口

/**
 * An object to which <tt>char</tt> sequences and values can be appended.  The
 * <tt>Appendable</tt> interface must be implemented by any class whose
 * instances are intended to receive formatted output from a {@link
 * java.util.Formatter}.
 */

Appendable代表一个可以执行追加（append）操作的字节数组对象。它只有三个方法：

Appendable append(CharSequence csq) throws IOException;
Appendable append(CharSequence csq, int start, int end) throws IOException;
Appendable append(char c) throws IOException;

这些方法对字符数组进行添加操作。AbstractStringBuilder中就需要对这几个方法进行实现来达到修改字符序列的目的。

成员变量

AbstractStringBuilder中有三个变量：

    /**
     * The value is used for character storage.
     */
    char[] value;
    /**
     * The count is the number of characters used.
     */
    int count;
    /**
     * The maximum size of array to allocate (unless necessary).
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

其中，value用来存储字符序列，count表示使用的字符的数量，这里你可能会有疑问，value的length应该就可以返回字符数组的数量，为什么还要有一个count单独来记录数量。其实这两个不是一个值，在可变性字节序列中，很多操作例如append和insert都会改变value这个字节序列，这就要求value有扩容的功能，但是扩容之后数组中并不是每个位置都会被字符填充，比如我扩大到之前长度的两倍，但是添加的字符串的长度不到之前的一倍，这样字符数组中就会有位置虽然被初始化了，却没有被真正填充，所以需要记录数组中真正字符的数量，也就是，value.length返回的是整个数组的长度，count记录的是字符数组中真正被字符填充的数量。关于具体的扩容策略，我们之后会讲到。
MAX_ARRAY_SIZE限制了数组可以锁定的最大容量。如果尝试锁定更大的数组会导致OutOfMemoryError: Requested array size exceeds VM limit。注意这个长度是字符数组的长度而不是真正填充字符的长度，我们看下面的例子：

public static void main(String[] args) {
        StringBuilder sb = new StringBuilder(Integer.MAX_VALUE);
    }
Exception in thread "main" java.lang.OutOfMemoryError: Requested array size exceeds VM limit
    at java.lang.AbstractStringBuilder.<init>(AbstractStringBuilder.java:68)
    at java.lang.StringBuilder.<init>(StringBuilder.java:101)
    at person.andy.concurrency.string.TrimTest.main(TrimTest.java:5)

StringBuilder是AbstractStringBuilder的子类，有下面的构造方法：

public StringBuilder(int capacity) {
        super(capacity);
    }

调用的就是父类AbstractStringBuilder的构造方法，我传入了一个大于MAX_ARRAY_SIZE的参数，就会抛出java.lang.OutOfMemoryError: Requested array size exceeds VM limit的错误。
实际上，如果没有给定一个较大的堆内存，即使构造方法中的参数小于MAX_ARRAY_SIZE，也会出现堆溢出的问题因为Integer.MAX_VALUE已经接近4G了，看下面的例子：

public static void main(String[] args) {
        StringBuilder sb = new StringBuilder(Integer.MAX_VALUE-100);
    }
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.lang.AbstractStringBuilder.<init>(AbstractStringBuilder.java:68)
    at java.lang.StringBuilder.<init>(StringBuilder.java:101)
    at person.andy.concurrency.string.TrimTest.main(TrimTest.java:5)

所以在使用AbstractStringBuilder或者其子类时，要注意这个初始容量值。

构造方法

    AbstractStringBuilder() {
    }
    /**
     * Creates an AbstractStringBuilder of the specified capacity.
     */
    AbstractStringBuilder(int capacity) {
        value = new char[capacity];
    }

我们主要看第二个：给定一个int类型的参数，这个构造方法会初始化value为一个大小是capacity的数组。此时我们应该能想到，count是0，value.length为capaticy。

获取容量和真实字节数量

AbstractStringBuilder提供了两个方法用来获取字符数组的容量和真实的字节数量：

/**
     * Returns the length (character count).
     *
     * @return  the length of the sequence of characters currently
     *          represented by this object
     */
    @Override
    public int length() {
        return count;
    }
    /**
     * Returns the current capacity. The capacity is the amount of storage
     * available for newly inserted characters, beyond which an allocation
     * will occur.
     *
     * @return  the current capacity
     */
    public int capacity() {
        return value.length;
    }

length方法返回的是count，也就是真实的字符数量。capacity返回的是value.length也就是我们所说的容量。
这里我们可以用一个StringBuilder的例子来看一下这两个数量：
StringBuilder是AbstractStringBuilder的子类，它有下面的构造方法：

public StringBuilder() {
        super(16);
    }

调用了父类AbstractStringBuilder的构造方法，但是传的值是16。也就是说，value会被初始化成容量为16的数组，但是由于没有添加字符串，count的值仍然为零。
可以看下面代码的输出：

public static void main(String[] args) {
        StringBuilder stringBuilder = new StringBuilder();
        System.out.println(stringBuilder.capacity());
        System.out.println(stringBuilder.length());
    }

输出结果是：16，0。
证明了我们的分析是正确的。

append方法

AbstractStringBuilder提供了很多append方法，我们这里重点分析三个:

public AbstractStringBuilder append(String str) {
        if (str == null)
            return appendNull();
        int len = str.length();
        //count+len可能就会超过Integer.MAX_VALUE而发生溢出导致结果是个负数
        ensureCapacityInternal(count + len);
        str.getChars(0, len, value, count);
        count += len;
        return this;
    }

先不看str为null的情况，首先获取str的长度，然后调用ensureCapacityInternal()，传的参数是当前字符数组中实际的字符数量加上str的长度，也就是执行添加操作需要的最小字节容量，从这个方法开始，就是AbstractStringBuilder及其子类的扩容机制，我们来重点分析一下：

扩容策略

/**
     * For positive values of {@code minimumCapacity}, this method
     * behaves like {@code ensureCapacity}, however it is never
     * synchronized.
     * If {@code minimumCapacity} is non positive due to numeric
     * overflow, this method throws {@code OutOfMemoryError}.
     */
private void ensureCapacityInternal(int minimumCapacity) {
        // overflow-conscious code
        if (minimumCapacity - value.length > 0) {
            value = Arrays.copyOf(value,
                    newCapacity(minimumCapacity));
        }
    }

我们得从append方法调用ensureCapacityInternal的参数说起：

ensureCapacityInternal(count + len);

这个参数是当前value中的实际字符数量加上要添加的字符串的长度，这个是扩容要求满足的最小容量，也就是我们的value的长度最小需要是这个值。这里有一个值得注意的地方，就是count+len这个值可能已经发生了溢出，也就是需要满足的最小容量已经超过了Integer的最大值，在分析后面的方法时，你需要一直记得这种情况。
之后，调用ensureCapacityInternal方法，首先进行了这样的校验：

if (minimumCapacity - value.length > 0)

我们需要分析几种情况：
第一，minimumCapacity也就是count+len没有发生溢出，此时如果minimumCapacity - value.length > 0，说明需要满足的最小容量是比当前字符数组的长度大的，就需要扩容，否则，说明不用扩容。
第二：minimumCapacity也就是count+len发生了溢出，此时minimumCapacity肯定是负数，这个时候minimumCapacity - value.length的值肯定是大于0的，至于为什么，你需要理解计算机中补码的运算，这里不做很多解释了。
所以，minimumCapacity - value.length > 0为false只会在minimumCapacity没有发生溢出并且minimumCapacity继续我们的逻辑，如果minimumCapacity - value.length > 0这个条件成立，就会调用

value = Arrays.copyOf(value,
                    newCapacity(minimumCapacity));

，这里的重点是newCapacity方法:

/**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by the same amount + 2 if
     * that suffices.
     * Will not return a capacity greater than {@code MAX_ARRAY_SIZE}
     * unless the given minimum capacity is greater than that.
     *
     * @param  minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero or
     *         greater than Integer.MAX_VALUE
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int newCapacity = (value.length << 1) + 2;
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        return (newCapacity <= 0 || MAX_ARRAY_SIZE - newCapacity < 0)
            ? hugeCapacity(minCapacity)
            : newCapacity;
    }
    private int hugeCapacity(int minCapacity) {
        if (Integer.MAX_VALUE - minCapacity < 0) { // overflow
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE)
            ? minCapacity : MAX_ARRAY_SIZE;
    }

这里直接给出结论：
（1）如果当前的真实字节数量也就是count值+需要添加的字符串的字节数量得到的结果大于Integer.MAX_VALUE，也就是发生了溢出，直接抛出OutOfMemoryError异常，因为肯定为不能这样大小的字节序列分配容量了。
（2）如果（1）中计算的结果不大于Integer.MAX_VALUE，说明这个容量是可以满足的（不管一些VM的限制）。这个时候，将value的长度扩大为原来的两倍加2，用这个值跟前面计算出来的值进行比较，取最大值，如果这个最大值没有大于MAX_ARRAY_SIZE，新的容量就是这个值。如果这个最大值大于MAX_ARRAY_SIZE，不管这个最大值是minCapacity还是value*2+2，都取minCapacity和MAX_ARRAY_SIZE的最大值来作为新的容量。

在完成了扩容操作之后，append方法调用的是String的getChars方法将需要添加的字符序列添加到原有字符序列后面，这个逻辑比较简单。

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;
    }

insert方法将一个字节序列插入到当前字节序列的offset开始的位置，这个方法同样会调用扩容策略，这里面值得关注的是下面这两行代码：

System.arraycopy(value, offset, value, offset + len, count - offset);
str.getChars(value, offset);

第一段代码将当前字节序列从offset开始的字节序列复制到offset+len开始的字节序列，保留出中间len长度的字节，第二段代码将要插入的字节序列复制到中间留出的位置部分。

indexOf方法

在AbstractStringBuilder中indexOf的实现值得关注：

public int indexOf(String str, int fromIndex) {
        return String.indexOf(value, 0, count, str, fromIndex);
    }

是通过String.indexOf方法实现的，这个方法我们在String源码中已经分析过了，当时就看到源码中说明这个方法会被String和StringBuffer用来做字符串查找，实际上在AbstractStringBuilder中就用到了。

StringBuilder

StringBuilder继承了AbstractStringBuilder，在AbstractStringBuilder的构造方法中，会根据传入的capacity的参数来初始化字符数组。如下：

AbstractStringBuilder(int capacity) {
        value = new char[capacity];
    }

而在StringBuilder中，构造方法会有些不同：

    public StringBuilder() {
        super(16);
    }
    public StringBuilder(int capacity) {
        super(capacity);
    }
    public StringBuilder(String str) {
        super(str.length() + 16);
        append(str);
    }

在默认情况下，StringBuilder的容量会被设置成16，如果提供了初始容量，就是该容量的值，如果构造方法中给了一个字符串，那么容量会是字符串的长度+16。
StringBuidler中的大多数方法都是直接使用的AbstractStringBuilder的实现，所以明白了AbstractStringBuilder的方法逻辑之后，就能知道StringBuider的实现了：

@Override
    public StringBuilder append(Object obj) {
        return append(String.valueOf(obj));
    }
    @Override
    public StringBuilder append(String str) {
        super.append(str);
        return this;
    }

StringBuffer

StringBuffer作为StringBuilder的线程安全版本，在很多方法上的实现同样是通过调用父类AbstractStringBuilder的对应方法来完成的，只不过对于需要修改状态的方法，都加上了Synchronized关键字来进行同步访问：

@Override
    public synchronized StringBuffer append(Object obj) {
        toStringCache = null;
        super.append(String.valueOf(obj));
        return this;
    }
    @Override
    public synchronized StringBuffer append(String str) {
        toStringCache = null;
        super.append(str);
        return this;
    }

这里就不需要详细介绍了。

Java重点难点

三：AbstractStringBuilder、StringBuilder和StringBuffer

引言