String #

En Java, le type String représente une séquence de caractères. Il est très utilisé pour manipuler du texte : noms, messages, fichiers, etc. Une particularité essentielle à comprendre est que les objets de type String sont immuables : une fois créés, ils ne peuvent pas être modifiés. Toute opération qui semble modifier une chaîne (comme la concaténation, le remplacement ou la suppression de caractères) crée en réalité un nouvel objet String en mémoire, sans changer l’original.

Par exemple :

String s = "Bonjour";
s = s + " le monde"; // Crée un nouvel objet String

Ici, la chaîne “Bonjour” n’est pas modifiée : une nouvelle chaîne “Bonjour le monde” est créée et la variable s pointe vers ce nouvel objet. L’ancienne chaîne reste inchangée (et sera éventuellement libérée par le ramasse-miettes).

Cette immuabilité rend les String sûres et efficaces pour le partage, mais peut entraîner des problèmes de performance si on fait beaucoup de modifications : dans ce cas, il vaut mieux utiliser StringBuilder.

En Java, les chaînes de caractères (String) sont représentées en mémoire selon l’encodage UTF-16. Cela signifie que chaque élément du tableau interne d’une chaîne est un « code unit » de 16 bits (un char Java), mais tous les caractères Unicode ne tiennent pas forcément dans un seul char.

L’UTF-16 est un encodage qui permet de représenter tous les caractères Unicode. La plupart des caractères courants (latin, accentués, etc.) sont codés sur un seul char (16 bits), mais certains caractères spéciaux ou emojis, appelés « supplémentaires », nécessitent deux char consécutifs (appelés une paire de substitution ou surrogate pair).

La méthode charAt(int index) retourne le char à la position donnée dans la chaîne, mais ce char ne correspond pas toujours à un caractère complet pour l’utilisateur. Si la chaîne contient un caractère supplémentaire (hors du plan multilingue de base), charAt peut retourner seulement une partie de ce caractère (un des deux éléments de la paire de substitution).

Pour manipuler correctement les caractères Unicode, il faut utiliser les méthodes codePointAt, codePoints() ou les classes de l’API Character, qui tiennent compte des paires de substitution et permettent de traiter chaque caractère Unicode comme une entité logique.

String s = "A😊B";
System.out.println(s.length());      // Affiche 4 (car 😊 occupe deux char)
System.out.println(s.charAt(1));     // Affiche un char de la paire surrogate, pas le smiley complet
System.out.println(s.codePointAt(1));// Affiche le code Unicode complet du smiley

Ainsi, il faut être vigilant lors du traitement de chaînes contenant des emojis ou des caractères spéciaux, car la longueur d’une chaîne (length) et l’accès par charAt ne correspondent pas toujours au nombre réel de caractères.

Utilisez l’application suivante pour explorer la représentation des chaînes de caractères en format UTF-16. Vous pouvez taper des caractères et voir comment la chaîne de caractère est représentée en mémoire.

Voici un exemple en Java qui illustre la plupart des propriétés et méthodes de la classe String.

La méthode split de la classe String en Java est utilisée pour diviser une chaîne en un tableau de sous-chaînes en fonction d’un délimiteur spécifié, qui peut être une chaîne simple ou une expression régulière. Par exemple, split("\\s+") divise une chaîne sur un ou plusieurs espaces, tandis que split(",") utilise une virgule comme séparateur. L’expression \\s+ signifie ‘un ou plusieurs espaces. Nous pourrions utiliser split(";") pour diviser sur un point-virgule.

Nous donnons plus loin un aperçu des expressions régulières. La notion n’est toutefois pas approfondie dans ce cours.

Les principales méthodes de la classe String #

La classe String offre plusieurs dizaines de méthodes. Les tableaux qui suivent décrivent les plus courantes et indiquent, lorsque la question se pose, leur complexité algorithmique, c’est-à-dire l’ordre de grandeur du nombre d’opérations effectuées.

Dans tout ce qui suit :

• \(n\) désigne la longueur de la chaîne sur laquelle la méthode est appelée ;
• \(m\) désigne la longueur de la chaîne passée en argument, lorsqu’il y en a une.

Rappelons qu’intuitivement \(O(1)\) signifie « un temps constant, indépendant de la taille de la chaîne », et que \(O(n)\) signifie « un temps proportionnel à la longueur de la chaîne ».

Accéder au contenu #

Comparer #

Rechercher #

Transformer #

Toutes ces méthodes retournent une nouvelle chaîne : la chaîne d’origine n’est jamais modifiée.

Découper et assembler #

Dans ce cours, il n’est pas nécessaire de mémoriser ces complexités. Retenez surtout deux choses : l’accès à un caractère (charAt) est immédiat, alors que presque toute autre opération parcourt la chaîne au complet. C’est pourquoi il faut éviter de reconstruire des chaînes à répétition à l’intérieur d’une boucle.

La recherche de sous-chaîne : indexOf #

La méthode indexOf(String) répond à une question simple : à quelle position le motif apparaît-il dans le texte ? L’approche la plus directe consiste à essayer chaque position possible, l’une après l’autre :

// Recherche naïve : à ne pas utiliser en pratique, mais facile à comprendre.
static int rechercheNaive(String texte, String motif) {
    int n = texte.length(), m = motif.length();
    for (int position = 0; position + m <= n; position++) {
        int j = 0;
        while (j < m && texte.charAt(position + j) == motif.charAt(j)) {
            j++;
        }
        if (j == m) return position;   // le motif entier a concordé
    }
    return -1;
}

Sur du texte ordinaire, cette boucle s’arrête presque toujours dès la première lettre : le coût est alors d’environ \(n\) comparaisons. Mais si le texte et le motif se ressemblent beaucoup, chaque essai peut aller très loin avant d’échouer. Avec un texte formé d’un million de a et un motif formé de 4096 a suivis d’un seul b, chacun des \(n\) essais compare 4096 caractères avant d’échouer : on obtient \(n\,m\) comparaisons, soit un comportement quadratique.

On pourrait croire que la bibliothèque standard de Java échappe à ce problème. Ce n’est pas le cas : la mise en œuvre de String.indexOf est très optimisée. Mais elle a tout de même une complexité de \(n\,m\) comparaisons dans le pire des cas. Voir à ce sujet Java’s String.indexOf can be slow (quadratic).

Conséquence pratique : si votre programme cherche dans un texte un motif fourni par l’utilisateur, un motif très long peut suffire à le paralyser. La parade la plus simple est de refuser les motifs démesurément longs.

L’algorithme de Horspool #

Peut-on faire mieux que d’essayer chaque position ? Oui, et l’idée est étonnamment simple. Elle est due à Nigel Horspool (1980), qui a proposé une version simplifiée de l’algorithme de Boyer-Moore. Les mises en œuvre efficaces de la recherche de sous-chaîne — dans les bibliothèques standard de plusieurs langages, dans les éditeurs de texte, dans les outils comme grep — reposent souvent sur cet algorithme ou sur l’un de ses proches parents.

L’algorithme de Horspool tient en deux observations :

1. On compare le motif de la droite vers la gauche, alors qu’on le fait glisser vers la droite.
2. Lorsqu’une comparaison échoue, on regarde le caractère du texte qui était aligné avec la dernière lettre du motif. Ce caractère nous dit de combien on peut glisser sans risquer de rater une occurrence : si ce caractère n’apparaît nulle part dans le motif, on peut glisser de toute la longueur du motif d’un seul coup.

On prépare donc, avant la recherche, une petite table de décalage : pour chaque caractère c, decalage[c] vaut la distance entre la dernière occurrence de c dans le motif (sa dernière lettre exclue) et la fin du motif ; et vaut la longueur du motif si c n’y figure pas.

Voyons l’algorithme à l’œuvre sur un petit exemple.

Trois alignements suffisent là où la recherche naïve en aurait essayé cinq. Surtout, l’algorithme n’a jamais lu les caractères des positions 0 et 1 du texte : il les a survolés. Sur un exemple aussi court le gain est modeste, mais il devient spectaculaire quand le motif s’allonge, comme nous le verrons.

Voici une mise en œuvre complète en Java. Le programme compte les comparaisons afin de rendre le travail effectué visible.

Un algorithme qui lit tout le texte fait au moins \(n\) opérations. Horspool, lui, peut en faire moins : c’est ce qu’on appelle un comportement sous-linéaire. La raison est qu’il ne lit pas tous les caractères du texte ; il en saute.

Prenons le cas le plus net. Le motif est xyz (trois lettres) et le texte ne contient que des a. À chaque essai :

• on compare la dernière lettre du motif, z, avec un caractère du texte, a : désaccord dès la première comparaison ;
• le caractère a n’apparaît pas dans le motif, donc decalage['a'] vaut 3 : on glisse de trois positions d’un seul coup.

Chaque comparaison fait donc avancer de trois caractères. Pour un texte de \(n\) caractères, il n’en faut que \(n/3\). Plus généralement, avec un motif de longueur \(m\) dont les lettres sont rares dans le texte, le coût descend vers \(n/m\) comparaisons : plus le motif est long, plus la recherche est rapide. C’est exactement l’inverse de la recherche naïve.

Il existe des algorithmes dont le pire cas est garanti linéaire, c’est-à-dire \(O(n+m)\) : Knuth-Morris-Pratt (1977) et l’algorithme Two-Way de Crochemore et Perrin (1991), ce dernier étant utilisé par plusieurs bibliothèques C. Ils ne sont toutefois pas toujours plus rapides en pratique : sur du texte ordinaire, leur surcoût les rend souvent plus lents qu’une recherche simple. Il n’existe pas de meilleur algorithme dans l’absolu, seulement des compromis.

Les expressions régulières #

Une expression régulière (ou regex) est un petit langage qui sert à décrire une forme de texte plutôt qu’un texte précis. Au lieu de chercher le mot exact « 2026-08-26 », on décrit « quatre chiffres, un tiret, deux chiffres, un tiret, deux chiffres ». Plusieurs méthodes de String acceptent une expression régulière en argument.

Voici les éléments de syntaxe les plus courants. Attention : en Java, l’expression régulière est écrite dans une chaîne de caractères, et la barre oblique inverse doit donc être doublée. Pour exprimer « un chiffre », on écrit \d en notation regex, ce qui donne "\\d" dans le code Java.

Les méthodes concernées de la classe String sont les suivantes.

Ces quatre méthodes recompilent l’expression régulière à chaque appel. Dans une boucle, il vaut donc mieux compiler le motif une seule fois avec Pattern.compile et le réutiliser. La classe Matcher permet en outre de récupérer les portions reconnues, ce que String ne sait pas faire.

Le moteur d’expressions régulières de Java procède par retour sur trace (backtracking) : quand une piste échoue, il revient en arrière et en essaie une autre. Sur certains motifs, le nombre de pistes explose et le temps de calcul devient exponentiel. L’exemple classique est le motif (a+)+b confronté à une chaîne formée uniquement de a :

// À NE PAS EXÉCUTER tel quel : le temps de calcul double à chaque « a » ajouté.
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".matches("(a+)+b");

Comme pour indexOf, la leçon est la même : méfiez-vous des motifs et des textes fournis par l’utilisateur. Ce défaut porte un nom, ReDoS (déni de service par expression régulière).

StringBuilder #

Le type StringBuilder en Java permet de construire et de modifier efficacement des chaînes de caractères. Contrairement à la classe String, qui est immuable (chaque modification crée un nouvel objet), StringBuilder permet d’ajouter, de modifier ou de supprimer des caractères sans créer de nouveaux objets à chaque opération. Cela le rend particulièrement utile lorsqu’on doit faire de nombreuses modifications ou concaténations de chaînes, par exemple lors de la lecture d’un fichier ou la construction dynamique d’un texte.

L’utilisation de StringBuilder améliore considérablement les performances, surtout dans les boucles : concaténer des chaînes avec + dans une boucle crée à chaque fois une nouvelle chaîne, ce qui consomme beaucoup de mémoire et ralentit le programme. StringBuilder évite ce problème en travaillant sur une seule zone mémoire.

Exemple :

StringBuilder sb = new StringBuilder();
for (int i = 0; i < 5; i++) {
    sb.append("Ligne ").append(i).append("\n");
}
String resultat = sb.toString();
System.out.println(resultat);

Dans cet exemple, toutes les lignes sont ajoutées efficacement à la même chaîne. Pour des opérations répétées ou sur de gros volumes de texte, StringBuilder est donc le choix recommandé pour de bonnes performances.

Voici un exemple en Java qui illustre la plupart des propriétés et méthodes de la classe StringBuilder.

CharSequence et subSequence() #

L’interface CharSequence représente une séquence de caractères lisible : elle est implémentée par plusieurs classes Java comme String, StringBuilder et StringBuffer. Cela permet d’écrire des méthodes qui acceptent n’importe quel type de séquence de caractères, et pas seulement des chaînes immuables.

La méthode subSequence(int start, int end) permet d’obtenir une portion (sous-séquence) de la séquence de caractères, allant de l’indice start (inclus) à end (exclu). C’est utile pour extraire une partie d’un texte sans créer une nouvelle chaîne si ce n’est pas nécessaire.

Exemple avec String :

String texte = "Bonjour le monde";
CharSequence sousTexte = texte.subSequence(8, 14); // "le mon"
System.out.println(sousTexte);

Exemple avec StringBuilder :

StringBuilder sb = new StringBuilder("abcdefg");
CharSequence sousSeq = sb.subSequence(2, 5); // "cde"
System.out.println(sousSeq);

Utiliser CharSequence rend le code plus flexible : on peut manipuler des chaînes, des buffers ou des builders de la même façon, et extraire facilement des sous-parties avec subSequence(). La méthode subSequence évite de faire une copie inutile.

Allocation de mémoire et ramasse-miettes #

Comprendre l’allocation de mémoire et le ramasse-miettes n’est pas obligatoire dans ce cours.

Lorsque vous créez un objet en Java, la mémoire nécessaire est automatiquement allouée dans une zone appelée le « tas » (heap). Contrairement à certains langages comme C ou C++, il n’est pas nécessaire de libérer explicitement la mémoire des objets qui ne sont plus utilisés. Java intègre un mécanisme appelé ramasse-miettes (ou garbage collector) qui se charge de détecter et de libérer automatiquement la mémoire occupée par les objets devenus inaccessibles. Il partage cette caractéristique avec d’autres langages comme C#, JavaScript et Python.

Le ramasse-miettes fonctionne en arrière-plan : il identifie les objets qui ne sont plus référencés par aucune variable ou structure de données, puis récupère la mémoire correspondante pour la rendre disponible à de nouveaux objets. Cela simplifie la gestion de la mémoire et réduit les risques de fuites de mémoire (memory leaks) ou d’erreurs de libération (comme les double free en C).

Cependant, il est important de comprendre que la libération de la mémoire n’est pas instantanée : le ramasse-miettes intervient à des moments choisis par la machine virtuelle Java (JVM), ce qui peut parfois entraîner de légères pauses dans l’exécution du programme. Pour la plupart des applications, ce fonctionnement automatique est un avantage, car il permet de se concentrer sur la logique du programme sans se soucier de la gestion manuelle de la mémoire.

L’allocation de mémoire en Java est automatique et la libération est assurée par le ramasse-miettes, ce qui contribue à la robustesse et à la sécurité des programmes Java.

Par contre, le ramasse-miettes a des inconvénients : il peut provoquer des pauses imprévisibles dans l’exécution du programme, appelées « pauses de collecte », lorsque la JVM décide de libérer la mémoire. Ces pauses sont généralement courtes, mais peuvent devenir perceptibles dans des applications nécessitant une grande réactivité (jeux, systèmes temps réel, etc.). De plus, le développeur a moins de contrôle sur le moment précis où la mémoire est libérée, ce qui peut compliquer l’optimisation des performances dans certains cas particuliers. Enfin, le ramasse-miettes consomme lui-même des ressources processeur, ce qui peut avoir un effet sur l’efficacité globale du programme.

Malgré l’existence du ramasse-miettes, il faut donc tenter de minimiser l’allocation de mémoire. Il faut éviter de créer des objets temporaires quand on peut réutiliser un objet déjà alloué.

Considérons l’exemple suivant.

• Approche 1 (String) : À chaque itération, l’opérateur += crée un nouvel objet String, car les objets String sont immuables en Java. Cela génère de nombreux objets temporaires qui doivent être gérés par le ramasse-miettes, augmentant la charge mémoire et le temps d’exécution.
• Approche 2 (StringBuilder) : En utilisant StringBuilder, un seul objet est créé et modifié à chaque itération. Cela réduit considérablement le nombre d’allocations mémoire et la charge sur le ramasse-miettes, ce qui améliore les performances.

Vidéos suggérées #