Combien de chaînes sont créées en mémoire lors de la concaténation de chaînes en Java?

On m'a posé des questions sur les chaînes immuables en Java. J'ai été chargé d'écrire une fonction qui concatène un certain nombre de «a» à une chaîne.

Ce que j'ai écrit:

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

On m'a ensuite demandé combien de chaînes ce programme générerait, en supposant que la récupération de place ne se produise pas. Mes pensées pour n = 3 étaient

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

Essentiellement, 2 chaînes sont créées à chaque itération de la boucle. Cependant, la réponse était n ² . Quelles chaînes seront créées en mémoire par cette fonction et pourquoi en est-il ainsi?

On m'a ensuite demandé combien de chaînes ce programme générerait, en supposant que la récupération de place ne se produise pas. Mes pensées pour n = 3 étaient (7)

Les chaînes 1 ( "") et 2 ( "a") sont les constantes du programme, elles ne sont pas créées dans le cadre des choses mais sont «internées» car ce sont des constantes connues du compilateur. En savoir plus sur String interning sur Wikipedia.

Cela supprime également les chaînes 5 et 7 du compte car elles sont identiques "a"à la chaîne # 2. Cela laisse les chaînes # 3, # 4 et # 6. La réponse est "3 chaînes sont créées pour n = 3" en utilisant votre code.

Le nombre de n ² est évidemment faux car à n = 3, ce serait 9 et même selon votre pire réponse, c'était seulement 7. Si vos chaînes non internées étaient correctes, la réponse aurait dû être 2n + 1.

Ainsi, la question de savoir comment devrait - vous faire cela?

Puisque la chaîne est immuable , vous voulez une chose modifiable - quelque chose que vous pouvez changer sans créer de nouveaux objets. C'est le StringBuilder .

La première chose à regarder est les constructeurs. Dans ce cas, nous savons combien de temps la chaîne sera, et il y a un constructeur StringBuilder(int capacity) qui signifie que nous allouons exactement autant que nécessaire.

Ensuite, il "a"n'est pas nécessaire que ce soit une chaîne , mais plutôt un caractère 'a'. Cela a quelques améliorations de performances mineures lors de l'appel append(String)vs append(char)- avec le append(String), la méthode doit savoir combien de temps la chaîne est et faire un peu de travail sur cela. En revanche, charest toujours exactement un caractère long.

Les différences de code peuvent être vues sur StringBuilder.append (String) vs StringBuilder.append (char) . Ce n'est pas quelque chose de trop préoccupant, mais si vous essayez d'impressionner l'employeur, il est préférable d'utiliser les meilleures pratiques possibles.

Alors, à quoi cela ressemble-t-il lorsque vous l'assemblez?

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

Un StringBuilder et une chaîne ont été créés. Aucune chaîne supplémentaire n'a dû être internée.

Écrivez d'autres programmes simples dans Eclipse. Installez pmd et exécutez-le sur le code que vous écrivez. Notez de quoi il se plaint et corrigez ces choses. Il aurait trouvé la modification d'une chaîne avec + dans une boucle, et si vous l'aviez changé en StringBuilder, il aurait peut - être trouvé la capacité initiale, mais il ferait certainement la différence entre .append("a")et.append('a')

A chaque itération, une nouvelle Stringest créée par l' +opérateur et affectée à s. Après le retour, tous sauf les derniers sont ramassés.

Les constantes de chaîne comme ""et "a"ne sont pas créées à chaque fois, ce sont des chaînes internes . Les chaînes étant immuables, elles peuvent être librement partagées; cela arrive aux constantes de chaîne.

Pour concaténer efficacement des chaînes, utilisez StringBuilder.

Comme MichaelT l'explique dans sa réponse, votre code alloue des chaînes O (n). Mais il alloue également O (n ² ) octets de mémoire et s'exécute en temps O (n ² ).

Il alloue O (n ² ) octets, car les chaînes que vous allouez ont des longueurs 0, 1, 2,…, n-1, n, qui se résument à (n ² + n) / 2 = O (n ² ).

Le temps est également O (n ² ), car l'allocation de la i-ème chaîne nécessite la copie de la (i-1) -ème chaîne, qui a la longueur i-1. Cela signifie que chaque octet alloué doit être copié, ce qui prendra du temps O (n ² ).

C'est peut-être ce que les enquêteurs voulaient dire?