Choix des structures de données (List, Set, Map)

1. Les trois questions fondamentales

Le choix d'une collection se résume presque toujours à répondre à trois questions clés concernant vos données :

1. Unicité : Avez-vous besoin de garantir que chaque élément est unique ?
2. Ordre : L'ordre dans lequel les éléments sont stockés ou parcourus est-il important ?
3. Accès : Comment allez-vous accéder aux éléments ? Par un index numérique, par une clé spécifique, ou simplement en les parcourant tous ?

Pour commencer à visualiser les différences, la vidéo suivante, que nous avons déjà abordée, met bien en évidence le premier critère : l'unicité des doublons qui sépare List et Set.

De même, la vidéo suivante illustre le cas d'usage des Map où l'accès se fait par une clé.

Ces vidéos nous donnent l'intuition de base. Maintenant, systématisons ce processus de décision.

2. Le Guide de Sélection des Collections

La meilleure façon de choisir est d'analyser les caractéristiques et les performances de chaque implémentation. Le document suivant est une excellente "cheatsheet" (aide-mémoire) que beaucoup de développeurs gardent à portée de main.

3. Arbre de décision : un modèle mental

En nous basant sur cette lecture, nous pouvons construire un arbre de décision simple pour nous guider.

Étape 1 : Quel est le type d'association de données ?

• Ai-je besoin d'associer une clé unique à une valeur ? (ex: un ID utilisateur à un objet Utilisateur, une chaîne de configuration à sa valeur).

  • Oui -> Utilisez Map.
    • L'ordre des clés n'a pas d'importance et la performance est maximale ? -> HashMap (le choix par défaut).
    • L'ordre d'insertion des clés doit être conservé ? -> LinkedHashMap.
    • Les clés doivent être triées (alphabétiquement, numériquement) ? -> TreeMap.

• Non, j'ai juste besoin de stocker une collection d'éléments. -> Passez à l'étape 2.

Étape 2 : Les éléments doivent-ils être uniques ?

• Oui, je veux éviter les doublons. (ex: une liste d'emails d'inscrits, les tags d'un article).

  • Utilisez Set.
    • L'ordre n'a pas d'importance et la performance est maximale ? -> HashSet (le choix par défaut).
    • L'ordre d'insertion doit être conservé ? -> LinkedHashSet.
    • Les éléments doivent être triés ? -> TreeSet.

• Non, les doublons sont autorisés. (ex: un historique de navigation, les articles d'un panier).

  • Utilisez List.
    • Allez-vous souvent accéder aux éléments par leur index (ex: maListe.get(5)) ? -> ArrayList (le choix par défaut, performant en $O(1)$ pour l'accès).
    • Allez-vous souvent ajouter ou supprimer des éléments au début ou à la fin de la liste ? -> LinkedList (performant en $O(1)$ pour ces opérations, mais lent pour l'accès par index $O(n)$).

Ce modèle mental, combiné à la cheatsheet, vous permettra de faire un choix éclairé dans la plupart des situations.

4. Mise en situation : Appliquer le modèle

Appliquons cette logique à deux scénarios concrets.

Scénario 1 : Panier d'achat d'un site e-commerce

Vous devez implémenter un panier. Un utilisateur peut ajouter plusieurs fois le même produit (ex: 3 T-shirts bleus). L'ordre dans lequel les produits sont ajoutés doit être visible pour l'utilisateur.

1. Type d'association ? Pas de clé-valeur. On stocke juste des objets Produit. -> Pas une Map.
2. Unicité ? Non, un utilisateur peut ajouter plusieurs fois le même produit. Les doublons sont autorisés. -> Pas un Set.
3. Conclusion : On a besoin d'une List.
4. Quelle implémentation ? On va probablement afficher les produits dans l'ordre, donc on va itérer. On peut aussi vouloir accéder au 3ème produit du panier (get(2)). Les ajouts se font toujours à la fin. ArrayList est parfait pour l'accès par index et l'ajout à la fin est efficace. C'est le choix le plus logique.

   List<Produit> panier = new ArrayList<>();
   

Scénario 2 : Gestion des permissions d'un utilisateur

Vous devez stocker les rôles d'un utilisateur ("ADMIN", "USER", "EDITOR"). Un utilisateur ne peut pas avoir deux fois le même rôle. Pour des raisons de sécurité, vous voulez vérifier très rapidement si un utilisateur a un certain rôle. L'ordre des rôles n'a aucune importance.

1. Type d'association ? Pas de clé-valeur. On stocke juste des chaînes de caractères (les rôles). -> Pas une Map.
2. Unicité ? Oui, un utilisateur ne peut pas avoir deux fois le rôle "ADMIN". Les doublons sont interdits. -> On se dirige vers un Set.
3. Conclusion : On a besoin d'un Set.
4. Quelle implémentation ? L'ordre n'est pas important. La priorité est la performance pour vérifier la présence d'un rôle (avec la méthode contains()). HashSet offre la meilleure performance (en moyenne $O(1)$) pour cette opération. C'est le choix idéal.

   Set<String> roles = new HashSet<>();
   

Conclusion

Félicitations, vous avez maintenant terminé le module sur les structures de données en Java ! Choisir la bonne collection est une compétence qui distingue un développeur débutant d'un professionnel. Un mauvais choix peut entraîner des bugs subtils ou des performances désastreuses.

Points clés à retenir :

• Votre décision doit être guidée par trois critères : l'unicité, l'ordre et le mode d'accès.
• Map pour les associations clé-valeur.
• Set pour les collections d'éléments uniques.
• List pour les collections ordonnées où les doublons sont permis.
• En cas de doute, les implémentations par défaut sont souvent un bon point de départ : HashMap, HashSet, et ArrayList.
• Une bonne pratique est de toujours déclarer vos variables avec le type de l'interface (List<String> noms = new ArrayList<>();). Cela rend votre code plus flexible si vous devez changer d'implémentation plus tard.

Jusqu'à présent, nous avons manipulé des collections de types simples comme String ou Integer. Mais la véritable puissance de Java réside dans la capacité à créer nos propres types de données complexes. Dans le prochain module, nous allons plonger au cœur de la Programmation Orientée Objet (POO) pour apprendre à définir nos propres classes et objets, comme Produit, Utilisateur ou Article, afin de construire des applications bien plus riches et structurées.