L’intérêt des collections

• Importance des structures de données :
  • Choisir des structures de données adaptées est crucial lors du développement.
  • Permet de stocker, parcourir et retrouver des objets efficacement.
• Types de structures de données :
  • Tableaux, listes, arbres, tables de hachage, etc.
• Ressources supplémentaires :
  • Un tutoriel
  • La javadoc

Les collections

• Définition : En Java, une collection est un objet qui permet de contenir des références vers d’autres objets.
• Comparaison avec les tableaux :
  • Les tableaux sont une structure de données qui contient des références.
  • Les collections offrent plus de flexibilité et de fonctionnalités.
• Le JDK propose :
  • Interfaces : Définissent les grands types de collections (List, Set, Map, etc.).
  • Classes abstraites : Implantent partiellement ces interfaces (AbstractList, AbstractSet, etc.).
  • Classes concrètes : Précisent les implantations (ArrayList, HashSet, HashMap, etc.).
  • Paquetage java.util : Contient toutes les interfaces et classes de collections.
  • Itérateurs : Mécanisme de parcours général des collections.
  • Outils de tri et de recherche : Méthodes utilitaires pour trier et rechercher dans les collections.

Une hiérarchie d’Interfaces

En Java, les collections se distinguent en plusieurs types principaux :

• Collections (Collection)
  • Ensembles (Set)
    • Ensembles triés (SortedSet)
  • Listes (List)
  • Files (Queue)
• Dictionnaires (Map)
  • Maps triées (SortedMap)

Un premier exemple

Le programme suivant ajoute trois chaînes de caractères (“Medor”, “Rex” et “Brutus”) à la liste maListe et l’affiche.

import java.util.*; // Importation de toutes les classes du paquetage java.util
List maListe = new ArrayList(); // Création d'une nouvelle liste de type ArrayList
maListe.add("Medor"); // Ajout de l'élément "Medor" à la liste
maListe.add("Rex"); // Ajout de l'élément "Rex" à la liste
maListe.add("Brutus"); // Ajout de l'élément "Brutus" à la liste

System.out.println(maListe); // Affichage du contenu de la liste

[Medor, Rex, Brutus]

Administration des collections

• Tri, recherche, min, max : Méthodes statiques pour gérer les collections.
• Classe Collections :
  • Algorithmes polymorphes pour manipuler les collections.
  • Wrappers pour créer de nouvelles collections basées sur des collections existantes.
  • Exemple : Collections.sort(maListe); pour trier une liste.
• Classe Arrays :
  • Méthodes pour manipuler les tableaux (tri, recherche).
  • Fabrique statique pour voir les tableaux comme des listes.
  • Exemple : Arrays.sort(monTableau); pour trier un tableau.

• Classe Arrays :
  • Méthodes pour manipuler les tableaux (tri, recherche).
  • Fabrique statique pour voir les tableaux comme des listes.
  • Exemple : Arrays.sort(monTableau); pour trier un tableau.

Des collections “génériques” ?

• Les collections représentent des ensembles d’objets (cf. type de retour de l’interface).
• Un objet ou un ensemble d’objets extraits sont donc du type Object.
• La conséquence est donc que les objets extraits doivent être transtypés.
• De plus les fonctions prennent en paramètres des instances de Object, il est donc difficile de contrôler la consistance.

Un exemple de transtypage 1/2

// Classe abstraite représentant un animal
public abstract class Animal { 
    // Méthode abstraite que chaque animal doit implémenter pour définir son cri
    public abstract String crier(); 
}

public class Chien extends Animal {
    // Implémentation de la méthode crier pour les chiens
    @Override
    public String crier() {
        return System.identityHashCode(this) + " aboie.";
    }

    // Méthode spécifique aux chiens
    public void sePromenerEnLaisse() {
        // Logique pour promener le chien en laisse
    }
}

public class Chat extends Animal {
    // Implémentation de la méthode crier pour les chats
    @Override
    public String crier() {
        return System.identityHashCode(this) + " miaule.";
    }
}

Un exemple de transtypage 2/2

import java.util.*;
List l = new ArrayList();
l.add(new Chien());
l.add(new Chien());
l.add(new Chat());
System.out.println("Taille de la liste: "+l.size());

Taille de la liste: 3

l.get(0).crier();

CompilationException: 
l.get(0).crier();
cannot find symbol
  symbol:   method crier()

((Animal)l.get(2)).crier();

307653971 miaule.

((Chien)l.get(2)).sePromenerEnLaisse();

EvalException: class REPL.$JShell$71$Chat cannot be cast to class REPL.$JShell$70$Chien (REPL.$JShell$71$Chat and REPL.$JShell$70$Chien are in unnamed module of loader jdk.jshell.execution.DefaultLoaderDelegate$RemoteClassLoader @706a04ae)
Execution exception
---------------------------------------------------------------------------

java.lang.ClassCastException: class REPL.$JShell$71$Chat cannot be cast to class REPL.$JShell$70$Chien (REPL.$JShell$71$Chat and REPL.$JShell$70$Chien are in unnamed module of loader jdk.jshell.execution.DefaultLoaderDelegate$RemoteClassLoader @706a04ae)
    at .(#102:5)

Les types génériques (1/2)

• Définition : Un type générique (ou type paramétré) permet de définir des classes, interfaces et méthodes avec des types variables.
• Avantages :
  • Réutilisabilité du code
  • Sécurité de type à la compilation
  • Élimination des conversions explicites

Le parcours d’une collection (1/2)

• Boucles traditionnelles :
  • Les collections indexées (Listes, etc.) peuvent être parcourues avec une boucle.
  • Limitation : Cette méthode n’est pas idéale pour l’évolutivité car elle supprime l’encapsulation des collections.
• Itérateur :
  • Une instance de l’interface Iterator permettant d’énumérer les éléments d’une collection.
  • Toutes les collections possèdent la méthode iterator() qui retourne un itérateur.
  • Les itérateurs peuvent être spécialisés en fonction des sous-classes de Collection (ex : ListIterator).
• Avantages des Itérateurs
  • Encapsulation :
    • Maintient l’encapsulation des collections.
  • Modification :
    • Permet de modifier la collection en cours de parcours.

Le parcours d’une collection - Exemple (2/2)

for (int i=0;i<animaux.size();i++)
  System.out.println(animaux.get(i).crier()) ;

196339111 aboie.
91495073 aboie.
21728983 miaule.

Iterator<Animal> itAnimaux = animaux.iterator();
while (itAnimaux.hasNext())
  System.out.println(itAnimaux.next()
                     .crier().toUpperCase());

196339111 ABOIE.
91495073 ABOIE.
21728983 MIAULE.

Trier une collection

• Les classes Collections et Arrays proposent des méthodes de classe pour traiter les collections et des tableaux.
• Elles permettent en particulier de trier et de rechercher dans des listes, de faire des copies, …
• Nous avons déjà vu que l’on pouvait trier une collection de String, en réalité pour qu’une collection puisse être triée, ses élements doivent implanter l’interface Comparable :
  • int compareTo(T o) Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.
• Attention à la consistance entre Comparable() et equals().

Recherche dans une collection

Collections.sort(l);
System.out.println(l);
int positionFigaroNom=Collections.binarySearch(l,figaro);
System.out.println("Figaro position par nom: "+positionFigaroNom);

[Animal(nom=Brutus,age=1,poids=15), Animal(nom=Figaro,age=3,poids=2), Animal(nom=Medor,age=2,poids=5)]
Figaro position par nom: 1

Collections.sort (l , new ComparateurPoidsAnimal());
System.out.println(l);
int positionFigaroPoids = Collections.binarySearch(l,figaro,new ComparateurPoidsAnimal());
System.out.println("Figaro position par poids: "+positionFigaroPoids);

[Animal(nom=Figaro,age=3,poids=2), Animal(nom=Medor,age=2,poids=5), Animal(nom=Brutus,age=1,poids=15)]
Figaro position par poids: 0

Utilisation des Set avec des arbres (TreeSet)

• Définition : TreeSet est une implémentation de l’interface Set basée sur un arbre rouge-noir.
• Caractéristiques :
  • Maintient les éléments dans un ordre trié.
  • Offre des performances logarithmiques pour les opérations de base (insertion, suppression, recherche).
• Avantages :
  • Maintien de l’ordre naturel des éléments.
  • Recherche rapide des éléments.

Utilisation des Set avec des tables de hachage (HashSet)

• Définition : HashSet est une implémentation de l’interface Set basée sur une table de hachage.
• Caractéristiques :
  • Ne maintient pas l’ordre des éléments.
  • Offre des performances moyennes constantes pour les opérations de base (insertion, suppression, recherche).
• Avantages :
  • Performances rapides pour les opérations de base.
  • Idéal pour les ensembles où l’ordre n’est pas important.

Set hashSet = new HashSet<>(); hashSet.add(“Banane”); hashSet.add(“Pomme”); hashSet.add(“Orange”); System.out.println(hashSet); // Affiche les éléments sans ordre particulier

Redéfinition de hashCode() et equals()

• Importance : Pour utiliser une classe dans une table de hachage (HashSet, HashMap)
• Règles :
  • Si deux objets sont égaux selon equals(), ils doivent avoir le même hashCode
  • Si deux objets ont le même hashCode, ils ne sont pas nécessairement égaux
  • hashCode() doit retourner la même valeur pour le même objet

Redéfinition de hashCode() et equals()

L’utilisation des Maps

• Une Map associe une clé unique à une valeur spécifique.
• Chaque clé est unique (equals() retourne false pour deux clés différentes).
• Pour les tables de hachage :
  • Utilisation de hashCode() pour générer un code de hachage.
  • Distribution uniforme des entrées pour améliorer les performances de recherche.
• Implémentation avec des arbres :
  • Arbres binaires de recherche pour maintenir les clés dans un ordre trié.
  • Opérations de recherche, d’insertion et de suppression en temps logarithmique.
• Les clés doivent implémenter l’interface Comparable pour définir un ordre naturel.
• Utilisations courantes des Maps :
  • Ajouter et supprimer des entrées.
  • Rechercher un objet par sa clé.
  • Récupérer les clés associées à une valeur.
• Les Maps sont essentielles pour organiser et accéder efficacement aux données.

• En Java, il s’agit d’une interface implémentée notamment par :
  • HashMap : Une table de hachage offrant un accès en $\mathcal{O}(1)$.
  • TreeMap : Un arbre équilibré qui ordonne les valeurs en fonction des clés :
    • L’accès est en $\mathcal{O}(\log n)$ (où $n$ est le nombre d’éléments).
    • Les objets doivent implémenter l’interface Comparable.
    • Il est également possible de fournir un comparateur externe (instance de Comparator).

L’interface Map<K,V>

void clear()
boolean containsKey(Object key)
boolean containsValue(Object value)
Set<Map.Entry<K,V>> entrySet()
boolean equals(Object o)
V get(Object key)
int hashCode()
boolean isEmpty()
Set<K> keySet()
V put(K key, V value)
void putAll(Map<? extends K,? extends V> t)
V remove(Object key)
int size()
Collection<V> values()

Fonctionnement de Map

• Par défaut, une Map stocke des instances de Object.
• L’utilisation des génériques est possible et fortement recommandée.
• Les couples clé/valeur sont manipulés via l’interface Map.Entry.
  • Trois méthodes principales : getKey(), getValue(), setValue().
• La méthode entrySet() de Map retourne un ensemble (Set) de Map.Entry.
• Pour garantir le bon fonctionnement, une clé ne peut être remplacée que par une clé égale (cf. equals()).
• Conseil : effectuer une opération d’ajout suivie d’une suppression pour tester le comportement.

Parcourir une Map

• Pour parcourir une Map :
  • Récupérer l’ensemble des clés avec keySet().
  • Parcourir cet ensemble à l’aide d’un itérateur ou d’une boucle for each.
  • Pour chaque entrée, récupérer la clé avec getKey() et la valeur avec getValue().
  • La méthode values() retourne la collection des valeurs correspondantes.

Set<Map.Entry<String,Chien>> setChiens = map1.entrySet();

for (Map.Entry<String,Chien> uneEntree : setChiens)
    System.out.print(uneEntree.getKey()+ " :" +uneEntree.getValue());

Arguments variables

• Varargs en Java :
  • Permettent de passer un nombre variable d’arguments du même type à une méthode.
  • Simplifient le passage d’arguments sans créer explicitement un tableau ou une collection.
  • Utilisation des varargs avec l’ellipse (...) après le type de l’argument.
  • Flexibilité et praticité : la méthode peut être appelée avec n’importe quel nombre d’arguments de type int.

public static int somme (int... entiers) {
  int total = 0 ;
  for (int e:entiers) total+=e;
  return total ;
}

System.out.println("1+2 = "+somme(1,2));

System.out.println("1+2+3+4 = "+somme (1,2,3,4));