Java CharAt() 和 deleteCharAt() 性能

Question

我一直想知道java中String/StringBuilder/StringBuffer的charAt函数的实现 那有多复杂？ 还有 StringBuffer/StringBuilder 中的 deleteCharAt() 怎么样？

Answer 1

对于 String、StringBuffer 和 StringBuilder，charAt() 是常量时间操作。

对于 StringBuffer 和 StringBuilder，deleteCharAt() 是线性时间操作。

StringBuffer 和StringBuilder 具有非常相似的性能特征。主要区别在于前者是同步的（因此是线程安全的），而后者不是。

Answer 2

让我们依次看看每个方法对应的实际java实现（仅相关代码）。这本身就会回答他们的效率。

String.charAt ：

public char charAt(int index) {
    if ((index < 0) || (index >= value.length)) {
        throw new StringIndexOutOfBoundsException(index);
    }
    return value[index];
}

正如我们所看到的，这只是一个恒定时间操作的单个数组访问。

StringBuffer.charAt ：

public synchronized char charAt(int index) {
  if ((index < 0) || (index >= count))
    throw new StringIndexOutOfBoundsException(index);
  return value[index];
}

同样，单个数组访问，因此是恒定时间操作。

StringBuilder.charAt ：

public char charAt(int index) {
    if ((index < 0) || (index >= count))
        throw new StringIndexOutOfBoundsException(index);
    return value[index];
}

同样，单个数组访问，因此是恒定时间操作。尽管这三种方法看起来相同，但还是有一些细微的差别。例如，只有 StringBuffer.charAt 方法被同步，而其他方法则不被同步。同样，String.charAt 的 if check 略有不同（猜猜为什么？）。仔细观察这些方法实现本身，我们会发现它们之间还存在其他细微差别。

现在，让我们看看 deleteCharAt 的实现。

String没有deleteCharAt方法。原因可能是它是一个不可变的对象。因此，公开一个明确指示此方法修改对象的 API 可能不是一个好主意。

StringBuffer 和 StringBuilder 都是 AbstractStringBuilder 的子类。这两个类的deleteCharAt方法将实现委托给其父类本身。

StringBuffer.deleteCharAt :

  public synchronized StringBuffer deleteCharAt(int index) {
        super.deleteCharAt(index);
        return this;
    }

StringBuilder.deleteCharAt :

 public StringBuilder deleteCharAt(int index) {
        super.deleteCharAt(index);
        return this;
    }

AbstractStringBuilder.deleteCharAt :

  public AbstractStringBuilder deleteCharAt(int index) {
        if ((index < 0) || (index >= count))
            throw new StringIndexOutOfBoundsException(index);
        System.arraycopy(value, index+1, value, index, count-index-1);
        count--;
        return this;
    }

仔细观察 AbstractStringBuilder.deleteCharAt 方法会发现它实际上是在调用 System.arraycopy。在最坏的情况下，这可能是 O(N)。所以deleteChatAt方法的时间复杂度是O(N)。

Answer 3

charAt 方法的复杂度为O(1)。

假设您要删除随机字符，StringBuilder 和 StringBuffer 上的 deleteCharAt 方法平均时间为 O(N)来自 N 字符 StringBuffer / StringBuilder。 （平均而言，它必须移动一半的剩余字符来填充已删除字符留下的“洞”。没有多次操作的摊销；请参见下文。）但是，如果您删除最后一个字符，成本将为O(1)。

String 没有 deleteCharAt 方法。

---

理论上，StringBuilder 和 StringBuffer 可以针对通过缓冲区“传递”插入或删除多个字符的情况进行优化。他们可以通过在缓冲区中维护一个可选的“间隙”并在其中移动字符来实现这一点。 （IIRC，emacs 以这种方式实现其文本缓冲区。）这种方法的问题是：

• 它需要更多的空间，用于表示间隙位置的属性以及间隙本身。
• 它使代码变得更加复杂，并减慢了其他操作的速度。例如，charAt在获取字符数组元素之前，必须将offset与间隙的起点和终点进行比较，并对实际索引值进行相应的调整。
• 仅当应用程序在同一缓冲区上执行多次插入/删除时，它才会有帮助。

毫不奇怪，这种“优化”尚未在标准 StringBuilder / StringBuffer 类中实现。但是，自定义 CharSequence 类可以使用此方法。

Answer 4

charAt 速度非常快（并且可以使用 String 的内部函数），它是数组的简单索引。 deleteCharAt 需要一个数组副本，因此删除一个字符不会很快。

Answer 5

因为我们都知道字符串在JDK中是作为字符数组来实现的，它实现了randomAccess接口。因此charAt的时间复杂度应该是int O(1)。与其他数组一样，删除操作的时间复杂度为 O(n)。

Answer 6

以上所有回复的摘要：
charAt 的复杂度为 O(1)，因为它只是访问数组的索引
在最坏的情况下，deleteCharAt 可能是 O(N)，因为它会为其复制整个数组。