Quantas strings são criadas na memória ao concatenar strings em Java?

Me perguntaram sobre strings imutáveis ​​em Java. Fui encarregado de escrever uma função que concatenou um número de "a" s em uma string.

O que eu escrevi:

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

Perguntaram-me quantas seqüências de caracteres esse programa geraria, assumindo que a coleta de lixo não ocorra. Meus pensamentos para n = 3 foram

1. ""
2. "uma"
3. "uma"
4. "aa"
5. "uma"
6. "aaa"
7. "uma"

Essencialmente, duas strings são criadas em cada iteração do loop. No entanto, a resposta foi n ² . Quais seqüências de caracteres serão criadas na memória por essa função e por que é assim?

Perguntaram-me quantas seqüências de caracteres esse programa geraria, assumindo que a coleta de lixo não ocorra. Meus pensamentos para n = 3 foram (7)

As strings 1 ( "") e 2 ( "a") são as constantes do programa, elas não são criadas como parte das coisas, mas são 'internadas' porque são constantes que o compilador conhece. Leia mais sobre isso em String interning na Wikipedia.

Isso também remove as seqüências 5 e 7 da contagem, pois são as mesmas "a"que a seqüência 2. Isso deixa as seqüências 3, 4 e 6. A resposta é "3 cadeias são criadas para n = 3" usando seu código.

A contagem de n ² está obviamente errada, porque em n = 3, isso seria 9 e, até mesmo, na sua pior resposta, isso era apenas 7. Se suas seqüências não internadas estavam corretas, a resposta deveria ser 2n + 1.

Então, a questão de como você deve fazer isso?

Como a String é imutável , você deseja algo mutável - algo que pode ser alterado sem criar novos objetos. Esse é o StringBuilder .

A primeira coisa a olhar são os construtores. Nesse caso, sabemos quanto tempo a string será e existe um construtor StringBuilder(int capacity) que significa que alocamos exatamente o quanto precisamos.

Em seguida, "a"não precisa ser uma String , mas pode ser um personagem 'a'. Isso tem um pequeno aumento no desempenho ao chamar append(String)vs append(char)- com o append(String), o método precisa descobrir quanto tempo a String é e fazer algum trabalho nisso. Por outro lado, charsempre tem exatamente um caractere.

As diferenças de código podem ser vistas em StringBuilder.append (String) vs StringBuilder.append (char) . Não é algo para se preocupar muito , mas se você estiver tentando impressionar o empregador, é melhor usar as melhores práticas possíveis.

Então, como fica isso quando você o reúne?

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

Um StringBuilder e um String foram criados. Nenhuma string extra precisava ser internada.

Escreva alguns outros programas simples no Eclipse. Instale o pmd e execute-o no código que você escreve. Observe o que se queixa e corrija essas coisas. Teria encontrado a modificação de uma String com + em um loop, e se você a alterasse para StringBuilder, talvez tivesse encontrado a capacidade inicial, mas certamente perceberia a diferença entre .append("a")e.append('a')

Em cada iteração, um novo Stringé criado pelo +operador e atribuído a s. Após o retorno, todos eles, exceto o último, são coletados no lixo.

As constantes de string gostam ""e "a"não são criadas sempre, são cadeias internas . Como as cordas são imutáveis, elas podem ser compartilhadas livremente; isso acontece com constantes de string.

Para concatenar seqüências de caracteres com eficiência, use StringBuilder.

Como MichaelT explica em sua resposta, seu código aloca O (n) strings. Mas também aloca O (n ² ) bytes de memória e é executado no tempo O (n ² ).

Aloca O (n ² ) bytes, porque as seqüências que você está alocando têm comprimentos 0, 1, 2,…, n-1, n, que soma (n ² + n) / 2 = O (n ² ).

O tempo também é O (n ² ), porque a alocação da i-ésima sequência requer a cópia da (i-1) -ésima sequência, que tem o comprimento i-1. Isso significa que cada byte alocado deve ser copiado, o que levará tempo O (n ² ).

Talvez seja isso que os entrevistadores quiseram dizer?