由于字符串在 Java 中是immutable的，因此将项目逐个附加到空字符串将花费O(n^2)时间。String.join("/", arrayList);方法的执行方式相同，还是线性时间运行？
它在Java 8的摊销O(n)时间内运行。
这是String.join的源代码：
public static String join(CharSequence delimiter,
Iterable<? extends CharSequence> elements) {
Objects.requireNonNull(delimiter);
Objects.requireNonNull(elements);
StringJoiner joiner = new StringJoiner(delimiter);
for (CharSequence cs: elements) {
joiner.add(cs);
}
return joiner.toString();
}
如您所见，只需要一个循环。
joiner.add调用StringBuilder.append，它以摊销O(1)时间运行，因为它只需要设置数组的一个元素。但是，如果大小变得太大，它将不得不扩展其内部数组并复制已附加的所有元素。请参阅下面的相关源代码以获取AbstractStringBuilder。
@Override
public AbstractStringBuilder append(CharSequence s) {
if (s == null)
return appendNull();
if (s instanceof String)
return this.append((String)s);
if (s instanceof AbstractStringBuilder)
return this.append((AbstractStringBuilder)s);
return this.append(s, 0, s.length());
}
@Override
public AbstractStringBuilder append(CharSequence s, int start, int end) {
if (s == null)
s = "null";
if ((start < 0) || (start > end) || (end > s.length()))
throw new IndexOutOfBoundsException(
"start " + start + ", end " + end + ", s.length() "
+ s.length());
int len = end - start;
ensureCapacityInternal(count + len);
for (int i = start, j = count; i < end; i++, j++)
value[j] = s.charAt(i);
count += len;
return this;
}
private void ensureCapacityInternal(int minimumCapacity) {
// overflow-conscious code
if (minimumCapacity - value.length > 0) {
value = Arrays.copyOf(value,
newCapacity(minimumCapacity));
}
}
StringJoiner.toString调用StringBuilder.toString，它O(n)时间内运行，因为它必须复制字符数组才能创建新String。
这是StringBuilder.toString的源代码：
@Override
public String toString() {
// Create a copy, don't share the array
return new String(value, 0, count);
}
String构造函数在O(n)时间内使用Arrays.copyOfRange复制char数组的元素：
public String(char value[], int offset, int count) {
if (offset < 0) {
throw new StringIndexOutOfBoundsException(offset);
}
if (count <= 0) {
if (count < 0) {
throw new StringIndexOutOfBoundsException(count);
}
if (offset <= value.length) {
this.value = "".value;
return;
}
}
// Note: offset or count might be near -1>>>1.
if (offset > value.length - count) {
throw new StringIndexOutOfBoundsException(offset + count);
}
this.value = Arrays.copyOfRange(value, offset, offset+count);
}
这是 Java 8 中 String.join(( 的源代码。
public static String join(CharSequence delimiter, CharSequence... elements) {
Objects.requireNonNull(delimiter);
Objects.requireNonNull(elements);
// Number of elements not likely worth Arrays.stream overhead.
StringJoiner joiner = new StringJoiner(delimiter);
for (CharSequence cs: elements) {
joiner.add(cs);
}
return joiner.toString();
}
这是 StringJoiner.add(( 的源代码
public StringJoiner add(CharSequence newElement) {
// prepareBuilder() returns a StringBuilder
prepareBuilder().append(newElement);
return this;
}
正如我们所看到的，join(( 调用 add(( n 次，add在常量时间内运行(创建 StringBuilder 的时间 + 追加 1 个项目(，所以 String.join((应该在 O(n( 时间内运行。
Java 14
查看当前的源代码(Java 14(，正确的答案是它以未摊销但O(n)摊销O(n^2)运行(参见维基百科#摊销分析(。
以下是相关片段：
- String#join - 数组中所有条目的简单循环，使用
StringJoiner调用joiner.add(...) - StringJoiner#add - 对内部数组
elts[size++] = elt;的简单设置调用，但它必须确保数组有足够的容量，最终将其Arrays.copyOf(elts, 2 * size);翻倍(动态数组( - 数组#copyOf - 这显然在调用时
O(n)运行，它必须将整个旧数组复制到新数组中。尽管此调用从典型的数组优化、缓存局部性和类似功能中受益匪浅。
此代码表示动态数组的一个非常常见的标准实现(参见维基百科(，例如ArrayList。加法在技术上是O(n)运行，但如果我们考虑摊销分析，它是O(1)的，因为只需要很少进行调整大小，从而增加数学潜力，直到必须进行下一次调整大小。
Java 8
有趣的是，该类的源代码已更改。在Java 8中，StringJoiner是建立在StringBuilder之上的，请参阅add方法：
- StringJoiner#add -
prepareBuilder().append(newElement);
但是，StringBuilder内部也基于动态数组工作：
- StringBuilder#append - forward to superclass
- AbstractStringBuilder#append - 再次调用
ensureCapacityInternal(count + len);以确保内部数组有足够的容量 - AbstractStringBuilder#ensureCapacityInternal - 如果需要，调用
expandCapacity - AbstractStringBuilder#expandCapacity - 这是我们的罪犯，
int newCapacity = value.length * 2 + 2;然后Arrays.copyOf(value, newCapacity);
String.join()内部使用StringBuilder。StringBuilder内部使用可调整大小的数组和指示数组中使用的最后一个单元格位置的索引。追加新字符串时，其字符将复制到数组的末尾，索引将向右移动。如果内部数组已满，则其大小将加倍。
当数组已满时，偶尔会执行数组扩展和关联的字符副本。渐近地将尺寸加倍作为膨胀系数，调整大小操作不会经常发生，因此StringBuilder#append(String)需要O(1)摊销时间。因此，项目的整个连接列表在O(n)上具有复杂性。
所以，这是O(n)