Вопрос по эффективности конкатенации в Java

Question

Я встречал это утверждение в одной из книг «Структуры данных» об анализе алгоритмов: создание новой строки в результате конкатенации требует времени, пропорционального длине полученной строки.

На самом деле, интуитивно это может быть правдой, но как конкатенация соотносится с длиной строки, разве мы не можем просто добавить символ в конец строки? Прошу прощения, если это глупый вопрос, просто новичок в Java!

Answer 1

Предположим, я хочу объединить строку `X длины a и другую строку Y длины b.

В Java вы не можете изменить строку после ее создания («строки неизменны»), поэтому я должен создать новую строку. Это также то, о чем говорит ваша книга: «... создание новой строки в результате конкатенации ...».

Сначала я должен выделить область памяти достаточно большой, чтобы хранить строку длины (a + b). Первые a символов новой строки будут иметь те же символы, что и X. Последние b символов новой строки будут иметь те же символы, что и Y. Поэтому я должен скопировать каждый символ из X и каждый символ из Y в вновь выделенная память.

Теперь представьте, что X и Y - очень длинные строки. Этот процесс копирования займет много времени, не так ли? Если копирование одного символа занимает n единиц времени, то создание новой строки займет (a + b) * n единиц времени плюс накладные расходы.

Answer 2

Java Строки являются неизменяемыми; это означает, что объединение (также просто добавление одного символа в конец строки) требует создания новой строки, которая состоит из комбинации из содержимого старой строки и содержимого добавленной строки.

Поскольку для этого потребуется скопировать содержимое, время создания новой объединенной строки зависит от тома, который необходимо скопировать.

В качестве примера - реализация String.concat() из Java 7:

public String concat( String str )
{
    int otherLen = str.length();
    if( otherLen == 0 ) 
    {
        return this;
    }
    int len = value.length;
    char buf[] = Arrays.copyOf( value, len + otherLen ); // *1
    str.getChars( buf, len ); // *2
    return new String( buf, true ); // *3
}

Конечно, не самый интуитивно понятный, но показывает, как исходная строка копируется в новый буфер (* 1), а затем добавленная строка копируется в этот буфер в ( * 2) до создания новой строки (* 3).

Реализации из более поздних версий Java выглядят по-разному, но в основном они будут делать то же самое.