Java CharAt() 和 deleteCharAt() 性能

Question

我一直想知道 charAt 函数的实现 String/StringBuilder/StringBuffer 在 Java 中它的复杂性是什么？还有 deleteCharAt() 在 StringBuffer/StringBuilder 中呢？

原文由 Jimmar 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

适用于 String charAt() - ， StringBuffer 和—-和 StringBuilder

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

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

原文由 Matt Ball 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

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

字符串.charAt：

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

如我们所见，这只是一个 常数时间 操作的单个数组访问。

字符串缓冲区.charAt：

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

同样，单个数组访问，因此是一个 常量时间 操作。

字符串生成器.charAt ：

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

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

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

字符串没有 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) 时间复杂度。

原文由 Nagakishore Sidde 发布，翻译遵循 CC BY-SA 3.0 许可协议