String和StringBuilder操作在内存使用方面的比较

Question

根据KathySierra的SCJP研究指南：

java.lang.StringBuffer和java.lang.SStringBuilder类应该当您必须对字符串进行修改时使用。正如我们所讨论的，String对象是不可变的，所以如果您选择使用String对象进行大量操作，最终会得到很多字符串池中已放弃的字符串对象的数量

为了澄清这一点，我在这里浏览了String类和StringBuilder源代码。

字符串的简化代码如下：

public final class String(){
     private final char [] value; //Final helps in immutability, I guess.
     public String (String original){
         value = original.value;
      }
}

StringBuilder的简化版本如下：

public final class StringBuilder{
    char [] value;
    public StringBuilder(String str) {
        value = new Char[(str.length() + 16)]; // 16 here is implementation dependent.
    append(str);
}
public StringBuilder append(String str){
            //Add 'str' characters in value array if its size allows,
        else
            // Create new array of size newCapacity and copy contents of 'value' in that.
            //value = Arrays.copyOf(value, newCapacity);// here old array object is lost.
        return this;
    }
}

假设我们有一个案例如下：

使用字符串类：

String s1 = "abc"; // Creates one object on String pool.
s1 = s1+"def"; // Creates two objects - "def " on String pool
// and "abcdef" on the heap.

如果我使用StringBuilder，代码将变为：

 StringBuilder s1 = StringBuilder("abc");
 // Creates one String object "abc " on String pool.
 // And one StringBuilder object "abc" on the heap.
 s1.append("def");
 // Creates one string object "def" on String pool.
 // And changes the char [] inside StringBuilder to hold "def" also.

在StringBuilder s2 = s1.append("def");中，包含字符串的char数组被新的char数组替换的可能性相等。旧数组现在是无引用的，将被垃圾回收。

我的查询是：

使用简单的String串联和StringBuilder append()方法，进入String池的String对象的数量是相同的。

根据上面列出的代码，StringBuilder首先使用了更大的char数组，而String对象包含的char数组的长度与其所持有的字符串的长度相同。

1. StringBuilder的使用如何比正常情况更有效率用于字符串操作的String类
2. SCJP Guide中的陈述是否错误

Answer 1

关键是expandCapacity函数：

void expandCapacity(int minimumCapacity) {
    int newCapacity = (value.length + 1) * 2; //important part here
    if (newCapacity < 0) {
        newCapacity = Integer.MAX_VALUE;
    } else if (minimumCapacity > newCapacity) {
        newCapacity = minimumCapacity;
    }
    value = Arrays.copyOf(value, newCapacity);
}

通过每次需要调整大小时将基础数组的大小调整为2倍，可以最大限度地减少追加1个字符所需的分摊时间。

维基百科有一个很好的解释：

当插入n个元素时，容量形成几何级数。按任何恒定比例扩展数组可以确保插入n个元素总共需要O（n）时间，这意味着每次插入都需要分摊的恒定时间。这个比例a的值导致了时间-空间的权衡：每次插入操作的平均时间约为a/（a−1），而浪费单元的数量在上面以（a−2）n为界。a的选择取决于库或应用程序：有些教科书使用a=2，但Java的ArrayList实现使用a=3/2，Python列表数据结构的C实现使用a=9/8。

如果底层存储的大小下降到某个阈值以下（例如容量的30%），许多动态阵列还会释放一些底层存储。该阈值必须严格小于1/a，以支持具有摊余恒定成本的插入和移除的混合序列。

在教授摊销分析时，动态数组是一个常见的例子。

现在，对于您的特定示例，这不会有什么不同，但您将看到添加大量字符时的效果：

public static void main(String[] args){
    int numAppends = 200000;
    int numRepetitions = 3;
    long[] time1 = new long[numRepetitions];
    long[] time2 = new long[numRepetitions];
    long now;
    for (int k = 0; k < numRepetitions; k++){
        String s = "";
        now = System.nanoTime();
        for(int i = 0; i < numAppends ; i++) {
            s = s + "a";
        }
        time1[k] = (System.nanoTime() - now) / 1000000;
        StringBuilder sb = new StringBuilder();
        now = System.nanoTime();
        for(int i = 0; i < numAppends ; i++) {
            sb.append("a");     
        }
        time2[k] = (System.nanoTime() - now) / 1000000;
        System.out.println("Rep "+k+", time1: "+time1[k]+ " ms, time2: " + time2[k] + " ms");
    }
}

输出：

Rep 0, time1: 13509 ms, time2: 7 ms
Rep 1, time1: 13086 ms, time2: 1 ms
Rep 2, time1: 13167 ms, time2: 1 ms

此外，我还计算了Arrays.copyOf()方法在extendCapacity()内部被调用的次数：第一次迭代调用了49次，但在第二次和第三次迭代中只有15次。输出如下：

newCapacity: 34
newCapacity: 70
newCapacity: 142
newCapacity: 286
newCapacity: 574
newCapacity: 1150
newCapacity: 2302
newCapacity: 4606
newCapacity: 9214
newCapacity: 18430
newCapacity: 36862
newCapacity: 73726
newCapacity: 147454
newCapacity: 294910
newCapacity: 42
Rep 2, time1: 12955 ms, time2: 134 ms

Answer 2

只有循环创建字符串时，效率才会更高。如果你有一个这样的循环：

String[] strings = { "a", "b", "c", "d" };
String result = "";
for( String s : strings) {
    result += s;
}

StringBuilder版本将生成更少的对象并导致更少的GC:

String[] strings = { "a", "b", "c", "d" };
StringBuilder builder = new StringBuilder();
for( String s : strings) {
    builder.append(s);
}

虽然第一个将导致在每次循环运行时发送一个对象用于GC，但第二个不会。

最终，由于字符串构建器数组的大小增加了一倍，因此不会发生太多分配。

Answer 3

操作不仅仅是串联。假设您想要在字符串的中间插入一个字符。既然字符串是不可变的，你会怎么做呢？您必须创建一个新的String。使用StringBuilder，您可以insert(int offset, c)

请参阅StringBuilder javadoc

你有这样的方法

delete(int start, int end)
// Removes the characters in a substring of this sequence.
replace(int start, int end, String str)
// Replaces the characters in a substring of this sequence with characters in the specified String.
reverse()
// Causes this character sequence to be replaced by the reverse of the sequence.
insert(int dstOffset, CharSequence s)
// Inserts the specified CharSequence into this sequence.

Answer 4

如何使用StringBuilder比普通的String类更有效地进行字符串操作？

当您在循环中执行许多操作时，它会大大提高效率。考虑任何需要对单个字符进行迭代的字符串转换或替换函数，例如，为XML或HTML:转义<, >, &, ", '字符的函数

public static String xmlEscape(String s) {
    StringBuilder sb = new StringBuilder(
        (int)Math.min(Integer.MAX_VALUE, s.length() * 5L / 4));
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '<') sb.append("&lt;");
        else if (c == '>') sb.append("&gt;");
        else if (c == '&') sb.append("&amp;");
        else if (c == '"') sb.append("&quot;");
        else if (c == ''') sb.append("&#039;");
        else sb.append(c);
    }
    return sb.toString();
}

StringBuilder数组最初的大小比输入字符串大一点，以便容纳原始文本和可能的替换。输出文本累积在预先分配的缓冲区中，在循环过程中很可能不需要任何额外的内存分配。

如果上面的函数将输出累积在String而不是StringBuilder中，那么每次处理单个字符时，它都会再次复制整个输出，从而使其性能降级为二次（即糟糕！）。

对于第二个问题：

SCJP指南中的陈述是错误的吗？

坦率地说，是的。说"字符串池中会有废弃的字符串对象"是非常误导人的。据我所知，术语"字符串池"仅指实习生池，例如String.intern()方法所使用的。只有当ClassLoader加载一个类并将源代码中的字符串文字常量加载到内存中时，字符串才会自动放入实习生池中。

在运行时操作String对象肯定不会在实习生池中放入额外的对象（除非您有意调用.intern()）。

SCJP指南应该说的是：

字符串对象是不可变的，因此，如果您选择对字符串对象进行大量操作，您将在堆中得到许多废弃的字符串对象。

堆中被丢弃的对象并不是最大的问题，因为垃圾收集器会很快吃掉它们。在执行多个操作时使用StringBuilders的真正原因是首先避免不必要的字符复制。这对@jmiserez的基准测试中显示的性能产生了巨大的影响。