Resolvi responder porque uma das respostas está certa em sua essência mas dá um motivo errado para a lentidão.
Como é formada uma string
Está correta a ideia que uma string em Java (o mesmo vale para C# e várias outras linguagens) internamente é representada por um array de chars, sendo que este tipicamente possui 2 bytes (que individualmente não necessariamente representam caracteres, mas isso é outro assunto). Veja comentário abaixo do hkotsubo que há otimização em versões mais recentes que pode ocupar apenas 1 byte.
Imutabilidade
Inicialmente um array, que tem tamanho fixo, é alocado para guardar o texto da string. Acontece que uma string é imutável. Toda vez que você vai alterar qualquer parte da string, precisa ocorrer outra alocação de memória. Imagine que fazer 100 mil alocações de memória não é nada barato. E pior, não é só a alocação que ocorre, todos os elementos do array anterior precisam ser copiados para o novo array alocado, com a devida alteração ocorrendo no meio deste processo.
Alocações em demasia
Isto se torna especialmente problemático quando você está aumentando o tamanho da string sucessivamente. Isto é chamado de Shlemiel the painter's algorithm(en). Onde um pintor vai pintando a faixa de ultrapassem de uma rodovia. Ele começa muito bem, com alta produtividade. Mas cada dia ele produz menos, até que seu trabalho fica inviável. Isto ocorre porque ele mantém a lata de tinta em lugar fixo, então ele pinta uma porção da faixa e tem que voltar ao ponto inicial para molhar o pincel. Cada dia ele está mais afastado da lata e demora mais tempo no trajeto do que na pintura.
O problema é o garbage collector?
Claro que um volume de alocações enorme que logo em seguida já não possuem referências vivas permitem que o garbage collector possa coletá-las. Isso é uma possibilidade que pode aumentar ainda mais a lentidão. Mas note que o garbage colletor faz a coleta de uma vez só, então esta coleta não consome tanto tempo assim. E isto normalmente só ocorre quando você realmente está com falta de memória. É possível que nenhuma coleta ocorra até seu término, em um programa simples.
Portanto o GC não é o motivo para a lentidão e sim as alocações e cópias na memória. 100 mil alocações com cópia custam absurdamente mais que todo o algoritmo do GC liberando a memória, já que ele é otimizado para fazer isso de uma vez em cada chamada usando um método generacional de coleta(en).
Usando o StringBuilder
O StringBuilder resolve isso fazendo pré-alocações de memória e permitindo que o conteúdo seja mutável. Ou seja, ele evita muitas alocações quando você está apenas querendo mudar uma porção da string e principalmente quando está aumentando seu tamanho sucessivamente.
Ele já possui uma porção de memória alocada minimizando bastante a quantidade de alocações necessárias. O algoritmo mais comum usado para determinar o tamanho é que toda vez que o novo texto não caiba na alocação atual, ele cria uma nova com o dobro do tamanho da anterior. Isto já minimiza muito a quantidade de alocações e consequentemente a cópia de dados.
Adicionalmente você pode determinar o tamanho inicial do array utilizado pelo StringBuilder
através do construtor StringBuilder(int capacity)
quando já tem uma noção do tamanho que a string terá. Obviamente também pode mudar o tamanho da alocação no meio do processo com o método expandCapacity(int minimumCapacity)
, quando se justifique.
A grosso modo a string é um algoritmo O(n), o StringBuilder
é O(log n).
Por ser uma estrutura mutável e pré-alocada, não ocorre o problema do pintor de rodovia. A lata está sempre próxima do pintor.
Existem outras técnicas para evitar alocações extras, mas a mais conhecida e mais universal é o StringBuilder
. Não sei se o Java faz alguma otimização, mas o C#, por exemplo, pode otimizar um código string texto = "abc" + "def" + "ghi" + "jkl";
. Mesmo um string texto = str1 + str2 + str3 + str4;
pode ser otimizado pelo compilador como string texto = string.concat(str1, str2, str3, str3);
onde a alocação ocorrerá uma única vez.
Escolhendo a melhor estrutura de dados
Por padrão usamos a string normal, e em casos de otimização o StringBuilder
passa ser útil. Pode dar vontade de usar sempre ele, mas ele tem seus malefícios (já citados pelo Math e utluiz). Não devemos fazer otimização prematura.
Padrões de projeto são criados para facilitar o trabalho de algo que se repete com frequência. Desde "sempre" adotamos padrões de projeto. Alguns padrões de projeto são apenas recomendações, são exemplos que devem ser seguidos. Outros se transformam em biblioteca, como é o caso do StringBuilder
. Outros são tão úteis que se transformam em construções de linguagem.
Como isto parece não estar claro para todos, respondi outra pergunta já existente sobre o assunto.
Coloquei no GitHub para referência futura.