StringBuffer和摊销

Question

在ArrayList中，加法操作是分期操作。因此，在阅读StringBuffer时，我突然想到了为什么StringBuffer没有摊销。假设我在字符串缓冲区对象上使用append操作，那么它应该能够在其底层数组实现中添加那么多个字符。但是我在源代码中发现我们有

System.arraycopy(chars, 0, value, count, chars.length);

在字符串缓冲区追加操作中。所以我的问题是，StringBuffer不能被摊销，这样它就不会给我们带来O(N)的复杂度吗？

Answer 1

最后，您仍然需要将N个引用从某个内存位置A移动到另一个内存位置B。然而，我相信System.arraycopy的速度足够快，因此StringBuffer提供了分期的性能。但是，这取决于您是使用append还是insert。

回想一下，ArrayList可以通过两种方式执行add：使用单个对象，或者将元素从特定索引点下移。两者都有不同的表现。

为了解决这个问题，(最终) StringBuffer将调用System.arraycopy()。这个实现实际上是依赖于JVM的(它是一个本机调用)，但它可能非常快。除此之外，除了要复制的非常大的非连续内存区域之外，没有太多因素会真正降低StringBuffer.append()的性能。

ArrayList.add(E element)将花费O(1)的时间，但可能会变成O(N)，因为它可能需要增长支持数组来容纳更多的元素；如果它不必这样做，那么插入时间大约是O(1)的数量级(它将元素添加到数组的末尾)。

在最好的情况下，ArrayList.add(int index, E element)可能是O(1)，但在平均和最坏的情况下，它可能是O(N索引)，这是因为它必须向下移动以放置E的元素数量。

总结一下：

• StringBuffer.append()的代码可以看作是分段的O(N)，因为它确实复制了数组。
• StringBuffer.insert()的代码是不同的，在最好的情况下很容易是O(1)，在最坏的情况下是O(N) (因为它对System.arraycopy()进行了两次调用)。在给定点插入元素意味着您必须将其他所有内容向下移动，无论您的代码有多快，这都不是一个廉价的操作。

我相信，根据你使用的方法，你确实有分期的表现。你只需要确定你正在做的操作，就能知道性能会是什么。

Answer 2

实际上，StringBuffer和ArrayList的工作方式是一样的，正如您所指出的，ArrayList中的add操作是O(1) amortized。

在ArrayList中，当您添加一个元素时，也有一个ensureCapacity方法，这样如果容量不足，就会分配一个新的数组，并将数据复制到其中。然而，这种重新分配的操作很少发生，所以你可以考虑加法需要O(1)，即使1次超过K，也需要O(n)。

Answer 3

如果你进一步研究源代码：

public AbstractStringBuilder append(char[] str) {
    int len = str.length;
    ensureCapacityInternal(count + len);  // expand array if needed
    System.arraycopy(str, 0, value, count, len); 
    count += len;
    return this;
}

这正是arraylist的工作原理。

    System.arraycopy(str, 0, value, count, len);

告诉我们从字符串复制到从计数开始的值(stringBuffer中的当前结束位置)。仅复制作为附加字符串长度的len。