quante stringhe vengono create in memoria quando si concatenano le stringhe in Java?

I was then asked how many strings this program would generate, assuming garbage collection does not happen. My thoughts for n=3 was (7)

Le stringhe 1 ( "" ) e 2 ( "a" ) sono le costanti nel programma, non sono create come parte delle cose ma sono "internate" perché sono costanti a conoscenza del compilatore. Ulteriori informazioni su questo argomento sono disponibili all'indirizzo Internazioni di stringhe su Wikipedia.

Rimuove anche le stringhe 5 e 7 dal conteggio poiché sono lo stesso "a" di String # 2. Questo lascia le stringhe # 3, # 4 e # 6. La risposta è "3 stringhe sono create per n = 3" usando il tuo codice.

Il conteggio di n ² è ovviamente sbagliato perché in n = 3, questo sarebbe 9 e anche nella tua peggiore risposta, era solo 7. Se le tue stringhe non internate erano corrette, la risposta dovrebbe essere stata 2n + 1.

Quindi, la domanda su come dovrebbe fare questo?

Poiché String è immutabile , vuoi una cosa mutabile - qualcosa che puoi cambiare senza creare nuovi oggetti. Questo è il StringBuilder .

La prima cosa da guardare sono i costruttori. In questo caso sappiamo per quanto tempo sarà la stringa, e c'è un costruttore StringBuilder(int capacity) che significa che assegniamo esattamente quanto ci serve.

Successivamente, "a" non deve necessariamente essere una Stringa , ma può essere un carattere 'a' . Questo ha un lieve incremento delle prestazioni quando si chiama append(String) rispetto a append(char) - con append(String) , il metodo deve scoprire quanto a lungo è la stringa e lavorare su quello. D'altra parte, char ha sempre esattamente un carattere.

Le differenze di codice possono essere visualizzate su StringBuilder.append (String) rispetto a StringBuilder.append (char) . Non è qualcosa di cui essere too interessato, ma se stai cercando di impressionare il datore di lavoro è meglio usare le migliori pratiche possibili.

Quindi, come appare quando lo metti insieme?

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

Sono stati creati un StringBuilder e una stringa. Nessuna stringa aggiuntiva necessaria per essere internata.

Scrivi altri programmi semplici in Eclipse. Installa pmd ed eseguilo sul codice che scrivi. Nota cosa si lamenta e aggiusta quelle cose. Avrebbe trovato la modifica di una stringa con + in un ciclo, e se l'avessi modificata in StringBuilder, avrebbe forse trovato la capacità iniziale, ma avrebbe sicuramente catturato la differenza tra .append("a") e .append('a')

In ogni iterazione, viene creato un nuovo String dall'operatore + e assegnato a s . Dopo il ritorno, tutti tranne l'ultimo vengono raccolti.

Le costanti di stringa come "" e "a" non vengono create ogni volta, queste sono stringhe internate . Poiché le stringhe sono immutabili, possono essere liberamente condivise; questo succede alle costanti di stringa.

Per concatenare in modo efficiente le stringhe, utilizza StringBuilder .

Come MichaelT spiega nella sua risposta, il tuo codice alloca le stringhe O (n). Ma assegna anche O (n ² ) byte di memoria e funziona nel tempo O (n ² ).

Alloca i byte O (n ² ), perché le stringhe che stai allocando hanno lunghezze 0, 1, 2, ..., n-1, n, che somme a (n ² + n) / 2 = O (n ² ).

Anche il tempo è O (n ² ), perché l'allocazione della stringa i-es richiede la copia della stringa (i-1) -th, che ha lunghezza i-1. Ciò significa che ogni byte assegnato deve essere copiato, il che richiederà tempo O (n ² ).

Forse questo è ciò che intendevano gli intervistatori?