Java Avancé

Les Collections d’objets

Youssef Saadi

@[Link]@[Link]

ISGA Casablanca

AU: 2024/2025
 Introduction
 Définition: « Une collection de données est un conteneur d’éléments de même type
qui possède un protocole particulier pour l’ajout, le retrait et la recherche
d’éléments ».
 Exemples: pile, queue (file d’attente), séquence, ensemble et multi-ensemble,
fonction (tableau associatif ou map en anglais).
 Ordre dans les collections:
 Les ensembles et les multi-ensembles n’ont pas d’ordre.
 Les autres collections ont un ordre « naturel » lié à l’ordre dans lequel les éléments ont
été insérés dans la collection.
 Les classes collection sont définies dans le package [Link] et sont définies à partir
de deux Interfaces Java:
❖ Collection
❖ Map

2 Collections (Youssef Saadi / v1.1)

 Introduction
- Collection: un groupe d'objets où la duplication peut-être autorisée.
- Set: est ensemble ne contenant que des valeurs et ces valeurs ne sont pas
dupliquées. Par exemple l'ensemble A = {1,2,4,8}. Set hérite donc de Collection,
mais n'autorise pas la duplication. SortedSet est un Set trié.
- List: hérite aussi de Collection, mais autorise la duplication. Dans cette
interface, un système d'indexation a été introduit pour permettre l'accès
(rapide) aux éléments de la liste.
- Map: est un groupe de paires contenant une clé et une valeur associée à cette
clé. Cette interface n'hérite ni de Set ni de Collection. La raison est que
Collection traite des données simples alors que Map des données composées
(clé,valeur). SortedMap est un Map trié.

3 Collections (Youssef Saadi / v1.1)

 Framework collection

4 Collections (Youssef Saadi / v1.1)

 Framework collection
 Le framework définit aussi des interfaces pour faciliter le
parcours des collections:
 Iterator : interface pour le parcours des collections
 ListIterator : pour le parcours des listes dans les deux sens et modifier
les éléments lors du parcours
 La framework utilise des interfaces pour le tri des collections
 Comparable : interface pour définir un ordre de tri naturel pour un
objet
 Comparator : interface pour définir un ordre de tri quelconque

5 Collections (Youssef Saadi / v1.1)

 Les collections implémentant Collection
Toutes ces classes sont disponible à l’adresse suivante :
[Link]

6 Collections (Youssef Saadi / v1.1)

 Méthode de l’interface Collection
 boolean add(Object): ajoute l'élément fourni en paramètre à la collection.
La valeur de retour indique si la collection a été mise à jour
 boolean addAll(Collection): ajoute à la collection tous les éléments de la
collection fournie en paramètre
 void clear(): supprime tous les éléments de la collection
 boolean contains(Object): indique si la collection contient au moins un
élément identique à celui fourni en paramètre
 boolean containsAll(Collection): indique si tous les éléments de la
collection fournie en paramètre sont contenus dans la collection
 boolean isEmpty(): indique si la collection est vide
 Iterator iterator(): renvoie un objet qui permet de parcourir l'ensemble
des éléments de la collection.
7 Collections (Youssef Saadi / v1.1)
 Méthode de l’interface Collection
 boolean remove(Object): supprime l'élément fourni en paramètre de la
collection. La valeur de retour indique si la collection a été mise à jour
 boolean removeAll(Collection): supprime tous les éléments de la
collection qui sont contenus dans la collection fournie en paramètre
 boolean retainAll(Collection c): permet de retirer tous les éléments de la
collection qui ne se trouvent pas dans la collection passée en paramètre.
Cette opération réalise l'intersection des deux collections.
 int size(): renvoie le nombre d'éléments contenus dans la collection
 Object[] toArray(): renvoie d'un tableau d'objets qui contient tous les
éléments de la collection.

8 Collections (Youssef Saadi / v1.1)

 L’interface Set<E>
 L'interface Set représente une collection ne contenant aucun éléments en
double. Autrement dit, les ensembles ne doivent contenir que des
éléments uniques.
 La méthode equals() appliquée entre chaque objet d'une implémentation
de l'interface Set, doit retourner obligatoirement false.
 L'interface Set est implémentée par les classes HashSet et AbstractSet.
De même, elle est étendue par l'interface SortedSet qui permet un tri sur
un ensemble.
 L'autre classe TreeSet n'implémente pas directement
l'interface Set puisqu'elle s'appuie sur l'interface SortedSet.

9 Collections (Youssef Saadi / v1.1)

 Les méthodes de l’interface Set
 int size(): retourne le nombre d'éléments de l'ensemble
 boolean isEmpty(): retourne true si l'ensemble ne contient aucun élément
 boolean contains(Object o): retourne true si l'élément spécifié est
contenu dans l'objet Set
 boolean add(Object o): ajoute l'élément spécifié au sein de l'objet Set, s'il
n'est pas déjà présent
 boolean remove(Object o): supprime l'élément spécifié de la
collection Set, s'il est présent
 Iterator iterator(): retourne un itérateur sur les éléments de l'ensemble
 boolean containsAll(Collection c): retourne true si l'objet Set contient
tous les éléments de la collection spécifiée

10 Collections (Youssef Saadi / v1.1)

 Les méthodes de l’interface Set
 boolean addAll(Collection c): ajoute tous les éléments de la collection
spécifiée au sein de l'objet Set, s'ils ne sont pas déjà présents.
 boolean removeAll(Collection c): supprime tous les éléments contenus
dans la collection spécifiée, de l'objet Set, s'ils y sont présents.
 boolean retainAll(Collection c): retient seulement les éléments de
l'objet Set, qui ne sont pas contenus dans la collection spécifiée.
 void clear(): supprime tous les éléments de la collection Set.
 Object[] toArray(): retourne un tableau contenant tous les éléments de
l'objet Set.

11 Collections (Youssef Saadi / v1.1)

 L’interface Map <K, V>
 Ce type de collection gère les éléments avec deux entités : une clé et une valeur
associée.
 La clé doit être unique donc il ne peut y avoir de doublons. En revanche la même
valeur peut être associée à plusieurs clés différentes.
 Avant l'apparition du framework collections, la classe dédiée à cette gestion était la
classe Hashtable.
 Les collections de type fonction (Map) ou tableau associatif en Java, sont définies à
partir de la racine Interface Map <K, V> (et non Collection <E> )
 La raison est qu’une telle collection est un ensemble de paires d’objets, chaque paire
associant un objet de l’ensemble de départ K à un objet de l’ensemble d’arrivée V ; on
parle de paires (clé, valeur)
 Les classes Map:
AbstractMap, Attributes, AuthProvider, ConcurrentHashMap,
ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, IdentityHashMap,
LinkedHashMap, PrinterStateReasons, Properties, Provider, RenderingHints,
SimpleBindings, TabularDataSupport, TreeMap, UIDefaults, WeakHashMap

12 Collections (Youssef Saadi / v1.1)

 Les méthodes de l’interface Map
 Object put(Object key, Object value): associe la valeur spécifiée à la clé donnée
au sein de la collection
 Object get(Object key): retourne la valeur correspondant à la clé spécifiée.
 Object remove(Object key): supprime la paire clé/valeur correspondant à la clé
spécifiée
 boolean containsKey(Object key): retourne true si la collection contient une
paire clé/valeur correspondant à la clé spécifiée
 boolean containsValue(Object value): retourne true si la collection contient une
ou plusieurs clés pointant la valeur spécifiée.
 boolean isEmpty(): retourne true si la collection ne contient aucune entrée.
 void putAll(Map t): copie toutes les paires clé/valeur de la collection spécifiée
au sein de l'objet Map.
 void clear(): supprime toutes les paires clé/valeur de la collection

13 Collections (Youssef Saadi / v1.1)

 Les méthodes de l’interface Map
 boolean equals(Object o): teste l'égalité entre l'objet Map et un autre objet.
 public Set keySet(): retourne un objet Set contenant les clés de l'objet Map
 public Collection values(): retourne un objet Collection contenant les valeurs
de l'objet Map.
 public Set entrySet(): retourne un objet Set contenant toutes les entrées de la
collection.
 int size(): retourne le nombre d'entrées dans la collection.
public interface Entry {
Object getKey();
Object getValue();
Object setValue(Object value);
}

14 Collections (Youssef Saadi / v1.1)

 Digression : la généricité en Java
 A partir de JDK 5.0, les collections sont définies par le biais de classes génériques
 Une classe générique est une classe qui définit ses méthodes de manipulation de
structure de données sans préciser le type de ses éléments. Idée: un ensemble de
X, une liste d’Y, …
 Par exemple, on pourrait définir une classe Pile<E> qui définit les méthodes void
empile(E e), E sommet(), void depile()
 Le type E est définit au moment de la déclaration d’un objet de la classe Pile, p.e.
Pile<int> p1 // une pile d’entiers
Pile<String> p2 // une pile de chaîne de caractères
❖ Instanciation
p1 = new Pile<int>;
p2 = new Pile<String>;

15 Collections (Youssef Saadi / v1.1)

 Les tableaux dynamiques : ArrayList
 Tableaux dynamiques (anciennement Vector, classe qui existe toujours)
 Dynamique = la taille (nombres d’éléments) du tableau n’est pas fixe et peut
varier en cours d’exécution
 L’accès à ses éléments est direct, comme dans un tableau
 Déclaration / construction
 ArrayList <E> v1 = new ArrayList <E> (); // vecteur dynamique vide
ou
 ArrayList <E> v2 = new ArrayList <E> (c);
/* vecteur dynamique contenant tous les éléments de la collection c */

16 Collections (Youssef Saadi / v1.1)

 Les tableaux dynamiques : ArrayList
 Ajout d’un élément en fin de vecteur:
[Link](elem);
 Accès au ième élément:
e = [Link]( 3 ); // accès au 3ème élément du vecteur v1
 Suppression du ième élément du vecteur (avec retour dans e)
E e = [Link]( 3 ); // suppression du 3ème élément
 Parcours: exemple, afficher tous les éléments
public static void affiche (ArrayList <E> v) {
for (E e : v) [Link] ( e + « » );
[Link]();
}

17 Collections (Youssef Saadi / v1.1)

 Les itérateurs
 Les itérateurs sont des objets qui permettent de "parcourir" un par un les
différents éléments d’une collection. Ils ressemblent à des pointeurs (tels que
ceux de C ou C++) sans en avoir exactement les mêmes propriétés.
 Il existe deux sortes d’itérateurs :
 Monodirectionnels : le parcours de la collection se fait d’un début vers une fin
; on ne passe qu’une seule fois sur chacun des éléments ;
 Bidirectionnels : le parcours peut se faire dans les deux sens ; on peut avancer
et reculer à sa guise dans la collection.

18 Collections (Youssef Saadi / v1.1)

 Itérateurs monodirectionnels
 Chaque classe collection dispose d’une méthode nommée iterator fournissant
un itérateur monodirectionnel, c’est-à-dire un objet d’une classe
implémentant l’interface Iterator<E> (Iterator avant le JDK 5.0). Associé à une
collection donnée, il possède les méthodes suivantes :
 boolean hasNext(): retourne true si l'itérateur a encore des éléments.
 Object next(): retourne le prochain élément de l'itérateur.
 void remove(): supprime de la collection sous-jacente le dernier élément
retourné par l'itérateur.
Iterator itr = [Link]();
while([Link]()){
[Link]();
….
}

19 Collections (Youssef Saadi / v1.1)

 Itérateurs bidirectionnels : listIterator
 Certaines collections (listes chaînées, vecteurs dynamiques) peuvent, par nature, être
parcourues dans les deux sens. Elles disposent d’une méthode nommée listIterator qui
fournit un itérateur bidirectionnel.
 Il dispose des méthodes héritées de Iterator et aussi d’autres méthodes permettant
d’exploiter son caractère bidirectionnel, à savoir :
 boolean hasPrevious(): Retourne vrai si l’élément courant à un élément précédant
 Object previous(): Retourne l’élément précédant.
 int nextIndex(): Retourne l’indice de l’élément qui serait retourné par un appel de next
 int previousIndex(): Retourne l’indice de l’élément qui serait retourné par un appel
de previous
 void add(Object o) : Ajoute un élément dans la liste
 void set(Object o): Remplace le dernier élément retourné par next ou previous par o

20 Collections (Youssef Saadi / v1.1)

 Les listes : LinkedList
Listes doublement chaînées
• La liste peut être parcourue par un itérateur bidirectionnel ListIterator
• Ajout et suppression d’un élément à une position donnée
• Accès d’un élément en fonction de sa valeur: nécessite le parcours de la liste
Utilisation :
la classe LinkedList se prête bien à l’implémentation des collections ordonnées,
c’est-à-dire :
❖ pile
❖ queue (file d’attente)
❖ séquence

21 Collections (Youssef Saadi / v1.1)

 Les listes : LinkedList
 Déclaration / construction
 LinkedList<E> l1 = new LinkedList<E> (); // liste vide
 ou
 LinkedList<E> l2 = new LinkedList<E> (c); /* liste contenant tous les éléments
de la collection c */
 Ajout d’un élément E e au début / fin de la liste
 [Link](elem); [Link](elem);
 Accès au premier / dernier élément de la liste
 E e = [Link](); e = [Link]();
 Suppression du premier / ième / dernier élément
 e = [Link](); e = [Link](i); e = [Link]()

22 Collections (Youssef Saadi / v1.1)

 Les listes : LinkedList et Iterateur
 Notion de position courante dans la liste avec l’itérateur de liste
ListIterator <E> iter = [Link]() //iter désigne le début de la liste
 Avancer / reculer d’un élément et retourner l’élément
e = [Link](); e = [Link]();
 Ajout d’un élément à la position courante
[Link](elem); // si fin de liste: ajout à la fin
 Suppression de l’élément à la position courante
[Link](); // suppression du dernier élément retourné par next ou previous
 Parcours: exemple, afficher tous les éléments de la liste
ListIterator <E> iter = [Link]();
while ([Link]()) {
E elem = [Link]();
[Link](elem);
}

23 Collections (Youssef Saadi / v1.1)

 Accès concurrent des itérateurs
Comme les itérateurs sont utilisés pour parcourir et mettre à jour des
collections, une exception de type CurrentModificationException est levée
si une mise à jour apparait dans un autre itérateur alors que l’itérateur
courant parcours la liste en même temps.

24 Collections (Youssef Saadi / v1.1)

 Les ensembles: HashSet
 Un ensemble est une collection non ordonnée d’éléments de type E, aucun élément
ne peut apparaître plus d’une fois dans un ensemble
 Problème: comme deux objets distincts ont des références différentes, on ne pourra
jamais avoir deux objets égaux même si toutes leurs valeurs sont identiques
-> Il faudra définir un comparateur qui sera capable de tester l’égalité de deux
objets (equals et compareTo)
 Même s’il n’existe pas d’ordre dans un ensemble, l’implémentation informatique
s’appuie sur une organisation des éléments afin de garantir un accès efficace.
 L’utilisateur devra définir, pour l’utilisation d’un
❖ HashSet -> les méthodes hashCode et equals dans la classe des éléments E
❖ TreeSet -> la méthode compareTo dans la classe E

25 Collections (Youssef Saadi / v1.1)

 Les ensembles: HashSet
 Déclaration / construction
HashSet<E> e1 = new HashSet<E> (); // ensemble vide
ou
HashSet<E> e2 = new HashSet<E> (c); /* ensemble contenant tous les éléments de la collection c */
 add – ajout d’un élément s’il n’appartient pas encore à l’ensemble (sinon état de l’ensemble
inchangé)
HashSet<E> e = new HashSet<E> ();
E elem = new E();
boolean nouveau = [Link](elem); // true si elem a été ajouté
if (nouveau) [Link](elem + « ajouté à l’ensemble »);
else [Link](elem + « existait déjà dans l’ensemble »);
 contains – test d’appartenance
boolean appartient = [Link](elem); // elem appartient-il à e ?
 remove – suppression d’un élément
boolean trouve = [Link](elem); //false si elem n’appartient pas à e

26 Collections (Youssef Saadi / v1.1)

 Les ensembles: HashSet
Parcours à l’aide d’un itérateur
HashSet<E> e = new HashSet<E> ();
… // ajouts d’éléments à l’ensemble
Iterator <E> iter = [Link]();
while ([Link]()) {
E elem = [Link]();
[Link](elem);
}
Remarques:
 Les éléments d’un ensemble n’étant pas ordonnées, aucun ordre d’itération
n’est assuré
 L’ordre d’itération peut varier dans le temps.

27 Collections (Youssef Saadi / v1.1)

 L’interface SortedSet
 Cette interface définit une collection de type ensemble trié.
 Le tri de l’ensemble peut être réalisé par deux façons :
 Les éléments contenus dans l’ensemble implémentant l’interface
Comparable pour définir leur ordre naturel
 Il faut fournir au constructeur de l’ensemble un objet Comparator qui
définit l’ordre de tri à utiliser.
 Elle définit les méthodes suivantes :
 Object first(): renvoie le premier élément de l’ensemble
 SortedSet headSet(Object) : renvoie un sous ensemble contenant tous les
éléments inférieurs à celui fourni en paramètre.
 Object last(): renvoie le dernier élément de l’ensemble
…

28 Collections (Youssef Saadi / v1.1)

 Les ensembles: TreeSet
 Il s’agit d’un arbre qui représente un ensemble trié des éléments
 Cette classe permet d’insérer des éléments dans n’importe quel ordre et
de restituer ces éléments dans un ordre précis lors de son parcours.
 L’implémentation de cette classe insère un nouvel élément dans l’arbre à
la position correspondante à celle déterminée par l’ordre de tri.
 L’insertion dans un objet TreeSet est plus lente mais le tri est directement
effectué.
 L’ordre est indiqué soit par les objets insérés (s’ils implémente l’interface
Comparable pour définir leur ordre de tri naturel) soit par un objet
implémentant Comparator qui est passé comme paramètre au
constructeur de l’objet TreeSet.

29 Collections (Youssef Saadi / v1.1)

 Les tableaux associatifs « Map » : HashMap
 Fonction (Map ) = ensemble de paires (clé, valeur)
 Notion proche de la fonction au sens mathématique
 En informatique, la fonction est aussi appelée tableau associatif
 Rappel: en Java, les collections de type fonction, sont définies à partir de
la racine Interface Map <K, V> ( et non Collection <E> )
 Accès rapide à une valeur en fonction d’une clé
 Techniquement réalisé par une table de hachage sur le domaine des clés
 Tout comme pour un HashSet, l’utilisateur doit définir les méthodes
hashCode et equals dans la classe des clés K.
 Remarque: si K est la classe String, hashCode et equals sont déjà définies
-> l’utilisateur n’a pas besoin de les redéfinir.

30 Collections (Youssef Saadi / v1.1)

 Les fonctions « Map » : HashMap
 Déclaration / construction
HashMap <K, V> m = new HashMap <K, V> (); // map vide
 Exemple: HashMap <String,Integer> m = new HashMap <String,Integer>();
 put - ajout d’une paire
[Link](cle, val); // où cle objet de K, val objet de V
 Cas particulier: val peut être de type primitif int, float, char,…(≠ objet)
exemple: [Link](« occident », 1);
 get - accès la valeur associée à une clé
V val = [Link](cle);
if (val == null) [Link](« aucune valeur associée à la clé »)
 remove - suppression d’une paire en foction de la valeur de clé
String cle = «occident»; // par exemple
V val = [Link](cle);
/*supprime l’association «occident» -> valeur; retourne la valeur si «occident» est présente dans la
map, null sinon*/

31 Collections (Youssef Saadi / v1.1)

 Les fonctions « map » : HashMap
 En théorie une map ne dispose pas d’itérateur
 En pratique, on utilise la méthode entrySet() défine dans la classe HashMap pour créer un ensemble à partir
du map (l’ensemble des paires du map); puis on crée un itérateur sur cet ensemble.
HashMap <K, V> m = new HashMap <K, V> ();
Set <[Link]<K,V>> paires = [Link](); // ensemble de paires
Iterator <[Link]<K,V>> iter = [Link](); // itérateur
while ([Link]()) {
[Link] <K, V> paire = [Link](); // paire courante
[Link](paire); // affichage de la paire courante
K cle = [Link](); // accès à la clé
V val = [Link](); // accès à la valeur
}
❖ Alternative: construire l’ensemble des clés avec la méthode keySet(); itérer sur cet ensemble et accéder aux
éléments de la map avec get.

32 Collections (Youssef Saadi / v1.1)

 L’interface SortedMap
 Elle définit une collection de type Map triée sur la clé.
 Le tri s’effectue de la même façon que pour SortedSet mais sur l’ensemble
des clés.
 Elle définit plusieurs méthodes :
 SortedMap headMap(Object) : renvoie une sous collection contenant
tous les éléments inférieurs à l’objet en paramètre.
 SortedMap subMap(Object, Object);
…

33 Collections (Youssef Saadi / v1.1)

 Le tri des collections : Comparable
 Tous les objets qui doivent définir un ordre naturel utilisé par le tri d'une
collection doivent implémenter cette interface.
 Cette interface ne définit qu'une seule méthode :
 int compareTo(Object)
 Cette méthode doit renvoyer :
 une valeur entière négative si l'objet courant est inférieur à l'objet fourni
 une valeur entière positive si l'objet courant est supérieur à l'objet fourni
 une valeur nulle si l'objet courant est égal à l'objet fourni
 Les classes wrappers, String et Date implémentent cette interface.

34 Collections (Youssef Saadi / v1.1)

 Le tri des collections : Comparator
 Cette interface représente un ordre de tri quelconque.
 Elle est utile pour permettre le tri d'objets qui n'implémentent pas l'interface
Comparable ou pour définir un ordre de tri différent de celui défini avec
Comparable ( l'interface Comparable représente un ordre naturel : il ne peut
y en avoir qu'un)
 Cette interface ne définit qu'une seule méthode :
 int compare(Object, Object)
 Cette méthode compare les deux objets fournis en paramètre et renvoie :
 une valeur entière négative si le premier objet est inférieur au second
 une valeur entière positive si le premier objet est supérieur au second
 une valeur nulle si les deux objets sont égaux.

35 Collections (Youssef Saadi / v1.1)

 Classes utilitaires : les algorithmes
 Collections (avec un s final) fournit des méthodes static pour, en
particulier,
 trier une collection
 faire des recherches rapides dans une collection triée
 Arrays fournit des méthodes static pour, en particulier,
 trier
 faire des recherches rapides dans un tableau trié
 transformer un tableau en liste.

36 Collections (Youssef Saadi / v1.1)

 Classes utilitaires
Tableau vers liste
 Pour passer d’un tableau à une liste, on peut utiliser la méthode [Link] :
 String[] mots = { "a", "b", "c" };
 List<String> l = [Link](mots);

Liste vers Tableau

 toArray() renvoie une instance de Object[] qui contient les éléments de la collection
 Si on veut un tableau d'un autre type, il faut utiliser la méthode paramétrée (généricité) <T> T[]
toArray(T[] tableau) à laquelle on passe un tableau du type voulu.
 Si le tableau est assez grand, les éléments de la collection sont rangés dans le tableau
 Sinon, un nouveau tableau du même type est créé pour recevoir les éléments de la collection
 Pour obtenir un tableau de type String[]
 String[] tableau = [Link](new String[0]);


37 Collections (Youssef Saadi / v1.1)

 Les algorithmes
 La classe Collections propose plusieurs méthodes statiques qui effectuent des
opérations sur des collections :
 void copy (List, List)
 Object max (Collection)
 Object max (Collection, Comparator)
 Object min (Collection)
 Object min(Collection, Comparator)
 void reverse(List)
 void shuffle(List)
 void sort(List)
 void sort(List, Comparator);

38 Collections (Youssef Saadi / v1.1)

 Des Questions ??

39 Collections (Youssef Saadi / v1.1)