实现StringBuilder

Question

我昨天在一次采访中被问到这个问题。我可以添加任何我想要的方法、成员和构造函数，但是我不能更改提供的toString和附加方法的签名。

我实现了这样的东西：

import java.util.ArrayList;
import java.util.List;

public class StringBuilder {

  private List<Character> characterBuffer;

  public StringBuilder() {
    characterBuffer = new ArrayList<Character>();
  }

  public void append(String anotherString) {
    if(anotherString != null) {
      char[] charArray = anotherString.toCharArray();
      for(int i=0;i<charArray.length; i++) {
        characterBuffer.add(charArray[i]);
      }
    }
  }

  public String toString() {
    char[] charArray = new char[characterBuffer.size()];
    for(int i=0; i<charArray.length; i++) {
      charArray[i] = characterBuffer.get(i);
    }
    return new String(charArray);
  }

}

当被问及是否有可能采取的另一种方法时，我建议使用一个基元char数组缓冲区，如果存在溢出，该缓冲区可以增长。不喜欢留下未完成的事情，当我回到家时，我实现了这个解决方案：

import java.util.Arrays;

public class StringBuilder {

  private char[] characterBuffer;
  private int curIndex;

  public StringBuilder() {
    characterBuffer = new char[5];
    curIndex = 0;
  }

  public void append(String anotherString) {
    if(anotherString != null) {
      char[] charArray = anotherString.toCharArray();
      int charArrayLength = charArray.length;
      if(overflow(charArrayLength)) {
        characterBuffer = Arrays.copyOf(characterBuffer, newLength(charArrayLength));
      } 
      for(int i=0;i<charArray.length; i++) {
        characterBuffer[curIndex++] = charArray[i];
      }
    }
  }

  private int newLength(int arrayLength) {
    return (characterBuffer.length + arrayLength) + 10;
  }

  private boolean overflow(int arrayLength) {
    return (arrayLength + curIndex) > characterBuffer.length;
  }

  public String toString() {
    return new String(characterBuffer, 0, curIndex);
  }

}

我希望这两种方法都能得到审查。

Answer 1

为此目的使用列表不是符合人体工程学的，这在您的两种方法的toString实现中非常明显(第二种方法是现场的)。对于一个相当快的解决方案，char[]显然是可行的。

不需要将其命名为characterBuffer，通常不会将类型的名称放在名称中。因此，buffer在这方面是很好的和简单的。无论如何，StringBuilder实现可能不需要任何其他类型的缓冲区。

正如@maaartinus所指出的，两种实现中最大的问题是丢弃char[]分配。小心点，这是个大错误。

也许他们正在寻找的方法是的StringBuilder实现所采用的技术:使用String.getChars将字符从源字符串复制到目标char[]中，在一定的偏移量和长度下，如下所示：

    if (str == null) str = "null";
    int len = str.length();
    ensureCapacityInternal(count + len);
    str.getChars(0, len, value, count);
    count += len;
    return this;

现在，就性能而言，这似乎是无与伦比的。