Сколько строк создается в памяти при объединении строк в Java?

Меня спросили об неизменных строках в Java. Мне было поручено написать функцию, которая объединяет несколько символов «a» в строку.

То, что я написал:

public String foo(int n) {
    String s = "";
    for (int i = 0; i < n; i++) {
        s = s + "a"
    }
    return s;
}

Затем меня спросили, сколько строк сгенерирует эта программа, предполагая, что сборка мусора не происходит. Мои мысли для п = 3 было

1. «»
2. «А»
3. «А»
4. «Аа»
5. «А»
6. «Ааа»
7. «А»

По сути, 2 строки создаются в каждой итерации цикла. Однако ответ был n ² . Какие строки будут создаваться в памяти этой функцией и почему?

Затем меня спросили, сколько строк сгенерирует эта программа, предполагая, что сборка мусора не происходит. Мои мысли для п = 3 было (7)

Строки 1 ( "") и 2 ( "a") являются константами в программе, они не создаются как часть вещей, а являются «интернированными», потому что они являются константами, о которых знает компилятор. Узнайте больше об этом в String interning в Википедии.

Это также удаляет строки 5 и 7 из подсчета, так как они совпадают со "a"строкой # 2. Это оставляет строки № 3, № 4 и № 6. Ответ: «3 строки созданы для n = 3» с использованием вашего кода.

Подсчет n ² , очевидно, неверен, потому что при n = 3 это будет 9, и даже по вашему наихудшему ответу это будет только 7. Если ваши не интернированные строки были правильными, ответ должен был быть 2n + 1.

Итак, вопрос, как вы должны это сделать?

Поскольку строка является неизменяемой , вам нужна изменяемая вещь, которую вы можете изменить, не создавая новые объекты. Это StringBuilder .

Первое, на что нужно обратить внимание - это конструкторы. В этом случае мы знаем, какой длины будет строка, и есть конструктор, StringBuilder(int capacity) который означает, что мы выделяем ровно столько, сколько нам нужно.

Далее, "a"не обязательно быть строкой , скорее это может быть персонаж 'a'. Это немного повышает производительность при вызове append(String)vs append(char)- с помощью append(String)метода необходимо выяснить, какова длина строки, и поработать над этим. С другой стороны, charвсегда ровно один символ в длину.

Различия в коде можно увидеть в StringBuilder.append (String) против StringBuilder.append (char) . Это не то, о чем нужно слишком беспокоиться, но если вы пытаетесь произвести впечатление на работодателя, лучше всего использовать лучшие практики.

Итак, как это выглядит, когда вы сложите это вместе?

public String foo(int n) {
    StringBuilder sb = new StringBuilder(n);
    for (int i = 0; i < n; i++) {
        sb.append('a');
    }
    return sb.toString();
}

Один StringBuilder и одна строка были созданы. Никаких дополнительных строк не требуется для интернирования.

Напишите несколько других простых программ в Eclipse. Установите pmd и запустите его на код, который вы пишете. Обратите внимание, на что он жалуется, и исправьте эти вещи. Он нашел бы модификацию String с + в цикле, и если бы вы изменили его на StringBuilder, он, возможно, нашел бы начальную емкость, но он наверняка поймал бы разницу между .append("a")и.append('a')

На каждой итерации, новый Stringсоздаются +оператором и назначено s. После возвращения все они, кроме последнего, собираются в мусор.

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

Для эффективного объединения строк используйте StringBuilder.

Как объясняет MichaelT в своем ответе, ваш код выделяет O (n) строк. Но он также выделяет O (n ² ) байтов памяти и выполняется за O (n ² ) времени.

Он распределяет O (n ² ) байтов, потому что строки, которые вы выделяете, имеют длины 0, 1, 2,…, n-1, n, которые суммируются в (n ² + n) / 2 = O (n ² ).

Время также равно O (n ² ), поскольку выделение i-й строки требует копирования (i-1) -й строки, которая имеет длину i-1. Это означает, что каждый выделенный байт должен быть скопирован, что займет O (n ² ) времени.

Может быть, это то, что имели в виду интервьюеры?