POO

Partie III
Les collections

Noreddine Gherabi
Les collections / Map
 Introduction

3
Noreddine GHERABI ENSA Khouribga
 Introduction

4
Noreddine GHERABI ENSA Khouribga
 Introduction

5
Noreddine GHERABI ENSA Khouribga
 Types des collections

6
Noreddine GHERABI ENSA Khouribga
 Collection List

7
Noreddine GHERABI ENSA Khouribga
 Collection List

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 */

8
Noreddine GHERABI ENSA Khouribga
 Collection List

9
Noreddine GHERABI ENSA Khouribga
 Collection List

Exemple :

10
Noreddine GHERABI ENSA Khouribga
 Collection List

Autres méthodes de ArrayList

11
Noreddine GHERABI ENSA Khouribga
 Collection List

Les itérateurs
v 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.
v 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.

12
Noreddine GHERABI ENSA Khouribga
 Collection List

Les itérateurs : Interface Iterator

v Implémentée par la plupart des collections

v permettant de parcourir une collection
v Les méthodes de Iterator :
§ hasNext() : retourne true si l’itérateur contient
d’autres éléments
§ next() : retourne l’élément suivant de l’itérateur
§ remove() : supprime le dernier objet obtenu par
next() ...

13
Noreddine GHERABI ENSA Khouribga
 Collection List

Les itérateurs : Interface Iterator

Exemple :

14
Noreddine GHERABI ENSA Khouribga
 Collection List

Exercice

Ecrire un programme qui :

§ Demande a l’utilisateur de saisir des nombres, quand il saisit 0 le programme
s’arrête
§ Demande à l’utilisateur une valeur à chercher
§ Demande à l’utilisateur une valeur à supprimer
§ Demande à l’utilisateur de saisir une valeur et le programme affiche sa position
dans la liste

15
Noreddine GHERABI ENSA Khouribga
 Collection List

LinkedList

Listes doublement chaînées

• La liste peut être parcourue par un itérateur bidirectionnel
ListIterator ( même chose que ArrayList)
• 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

16
Noreddine GHERABI ENSA Khouribga
 Collection List

LinkedList

• Pour créer une liste LinkedList

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]()

17
Noreddine GHERABI ENSA Khouribga
 Collection List

LinkedList – Construction d’une liste

• On peut utiliser la généricité pour imposer un type à la liste

LinkedList<Integer> liste = new LinkedList<Integer>();

Ou :
List<Integer> liste = new LinkedList<Integer>();

• Même chose pour ArrayList

List<Integer> liste = new ArrayList<Integer>();

• Pour convertir le tableau tab en liste

Integer [] tab = { 2, 3, 5, 1, 9 };
List<Integer> liste = new LinkedList([Link](tab));
Ou tout simplement :
List<Integer> ent = [Link](tab);

18
Noreddine GHERABI ENSA Khouribga
 Collection List

LinkedList
Exemple :

19
Noreddine GHERABI ENSA Khouribga
 Collection Set

20
Noreddine GHERABI ENSA Khouribga
 Collection Set

HashSet

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 (pas de duplication)
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

21
Noreddine GHERABI ENSA Khouribga
 Collection Set

HashSet

• Pour créer une liste HashSet

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 */

• Ajout d’un élément E elem dans la liste

boolean nouveau = [Link](elem); // true si elem a été ajouté
if (nouveau) [Link](elem + « ajouté à 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

22
Noreddine GHERABI ENSA Khouribga
 Collection Set

HashSet
Exemple :

Résultat : c
69
bonjour

23
Noreddine GHERABI ENSA Khouribga
 Collection Set

HashSet

difficiles a connaitre

Pour avoir un affichage ordonné selon l’ordre d’insertion, on peut utiliser

LinkedHashSet

24
Noreddine GHERABI ENSA Khouribga
 Collection Set

HashSet

Exemple: conversion de HashSet en tableau

Résultat : c
69
bonjour

25
Noreddine GHERABI ENSA Khouribga
 Collection Set

LinkedHashSet
LinkedHashSet est utilisée pour avoir un affichage ordonné selon l’ordre d’insertion

Exemple: conversion de LinkedHashSet en tableau

Résultat : bonjour
69
c

26
Noreddine GHERABI ENSA Khouribga
 Collection Set

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.

27
Noreddine GHERABI ENSA Khouribga
 Collection Set

TreeSet

28
Noreddine GHERABI ENSA Khouribga
 Collection Set

TreeSet
Exemple :

Affichage :
2
5
8

29
Noreddine GHERABI ENSA Khouribga
 Collection Set

Exercice

Ecrire un programme qui :

§ Demande a l’utilisateur de saisir des valeurs dans une liste (Liste1) de type Set
§ Tester si la liste est vide
§ Demande à l’utilisateur de saisir une autre liste (Liste2)
§ Tester si la liste 1 contient tous les éléments de la liste 2
§ Dans la liste 1 garder seulement les éléments en commun entre les deux listes
( Intersection entre les deux listes)
§ Dans la liste 1 supprimer tous les éléments qui appartient à liste 2

Utiliser les méthodes : RemoveAll(), containsAll(), retainAll(), isEmpty()

30
Noreddine GHERABI ENSA Khouribga
 Map

q Fonction (Map ) = ensemble de paires (clé, valeur)

q Notion proche de la fonction au sens mathématique
q En informatique, la fonction est aussi appelée tableau associatif
q En Java, les collections de type fonction, sont définies à partir de la
racine Interface Map <K, V> ( et non Collection <E> )
q Accès rapide à une valeur en fonction d’une clé
q Techniquement réalisé par une table de hachage sur le domaine des
clés
q Tout comme pour un HashSet, l’utilisateur doit définir les méthodes
hashCode et equals dans la classe des clés K.
q 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

31
Noreddine GHERABI ENSA Khouribga
 Map

HashMap : Liste non ordonée

LinkedHashMap : Liste ordonnée selon l’ordre d’insertion
TreeMap : Liste ordonnée selon l’ordre naturel

32
Noreddine GHERABI ENSA Khouribga
 Map

Hashtable

par contre hashmap accepte les valeurs null

Noreddine GHERABI ENSA Khouribga

 Map

Hashtable

Exemple :

Affichage : Remarque
C++
Pascal put ajoute la valeur si la clé n’existe pas,
PHP Sinon il modifie l’ancienne valeur.
Java

Noreddine GHERABI ENSA Khouribga

 Map

Hashtable

Autres méthode de Hashtable:

Noreddine GHERABI ENSA Khouribga

 Map

HashMap

36
Noreddine GHERABI ENSA Khouribga
 Map

HashMap – Quelques Méthodes

• Pour créer une liste HashMap

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
Exemple: [Link](‘’Ahmed’’, 1);

• get - accès la valeur associée à une clé

V val = [Link](cle);
if (val == null) [Link](« aucune valeur associée ala clé»)
remove - suppression d’une paire en foction de la valeur de clé
String cle =‘’Ahmed’’; // par exemple
V val = [Link](cle);

37
Noreddine GHERABI ENSA Khouribga
 Map

HashMap
• Fonctions :
§ 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.

Noreddine GHERABI ENSA Khouribga

 Map

HashMap
• Fonctions :
Pour afficher la clé et la valeur, on peut utiliser Entry

Exemple :

Noreddine GHERABI ENSA Khouribga

 Map

Exercice
Ecrire un programme qui :
§ Demande a l’utilisateur de saisir des valeurs dans une liste HashMap
§ Afficher la valeur d’une clé donnée
§ Supprimer un élément en donnant sa clé
§ Tester si la liste vide ou non
§ Rechercher un élément dans liste en donnant sa clé
§ Rechercher un élément dans liste en donnant sa valeur
§ Afficher toutes les valeurs de la liste
§ Afficher toutes les clés de la liste
§ Créer une deuxième liste HashTable puis afficher ses éléments en utilisation
une Enumération
§ Ajouter tous les éléments de la deuxième liste HashTable dans la première
liste HashMap
Utiliser les méthodes :
Remove, KeySet, KeyValues, isEmpty, containsKey, ContainsValue, put, putAll …

Noreddine GHERABI ENSA Khouribga