使用 '+' 运算符的 Java 字符串连接

当我们使用+操作符将大小为Y的字符串S2连接到大小为X的字符串S1(已经存在于堆上)时，实际发生了什么?

我是这么想的:

如果我执行以下函数:

class StringConcatenation{
String S1;
String concat(String S2){
this.S1 = this.S1 + S2;
}
}

如果S1存在于字符串池中(存储在堆中)，并且执行concat方法，则该方法将在堆栈上执行。

因此，CPU需要复制堆栈中的S1=>readS1

由于字符串是不可变的，Java必须创建一个新对象(让我们将其引用命名为S3)。

现在，S1和S2的内容在new object =>copyS1+ copyS2

则引用S1指向新对象。

因此，总时间复杂度为0 (READS1)复制S1+复制S2) =O(X + X + Y)=O(2*X + Y).

我的思维过程正确吗?

在文档中您可以阅读:

Java语言提供了对字符串连接操作符(+)和将其他对象转换为字符串的特殊支持。字符串连接是通过StringBuilder(或StringBuffer)类及其append方法实现的。

a = a + b is the equivalent of a += b or:
a = new StringBuilder()
.append(a)
.append(b)
.toString();

免责声明:String类经过多次更改，以提高性能和空间利用率。JIT编译代码时发生的事情完全没有定义。以下是一个简化，并忽略了可能应用或不应用的任何优化。

String是一个封装了char[]的类。数组长度总是恰好是字符串的length()。类和底层数组是不可变的。

class String {
private final char[] arr;
}

StringBuilder(和StringBuffer)是封装char[]的另一个类，但是数组几乎总是大于数组中的字符数。类和数组都是可变的。

class StringBuilder {
private char[] arr;
private int len;
}

当您使用+操作符进行字符串连接时，编译器将生成:

// Java code
s = s1 + s2 + s3;
// Generated code
s = new StringBuilder().append(s1).append(s2).append(s3).toString();

StringBuilder将最初创建长度为16的数组，并在需要时重新分配数组。最坏的情况是s1、s2和s3对于当前数组来说都太大了，所以每次调用append()都需要重新调整数组的大小。

这意味着将按照如下方式进行:

new StringBuilder()- createchar[16].
append(s1)-调整arr的大小，然后从s1.arr复制字符到数组。
append(s2)-调整arr的大小，复制现有内容(s1中的字符)到新的数组，然后复制s2.arr中的字符到数组。
append(s3)-调整arr大小，复制现有内容(s1和s2中的字符)到新数组，然后复制s3.arr中的字符到数组。
toString()-创建新的String,char[]的大小正好适合StringBuilder中的字符，然后将内容(s1,s2和s3的字符)复制到新的String。

所有来自s1的字符最终被复制了4次。

如果字符串连接为S1 + S2，则复制S1中的字符2或3次，复制S2中的字符2次。

由于时间复杂度通常是最坏的情况，这意味着O(3m + 2n)，而不是问题中建议的O(2m + n)。当然，大O消除了常数因子，所以它实际上是O(m + n)。

相关内容