Programmation Orientée Objet
Chapitre 5: Les collections
Dr. Mouna Chebbah
Dr. Mouna Chebbah
L2 BC
ESEN
Semestre 1, 2020
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
1/29
Collection de données
Introduction
Les collections
Les HashMaps
§ 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, file, séquence, ensemble et multi-ensemble,
fonction (tableau associatif ou map en anglais)
§ En Java, il existe 3 sortes de structures de données:
§ Les tableaux: Structure de taille fixe, accès direct aux élements
§ Les Collections:Structure modifiable, différents algorithmes de
stockage
§ Les Map:Structure modifiable, stocke des couples clé, valeur
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
2/29
Les collections
Introduction
Les collections
Les HashMaps
§ Les classes des collections sont définies dans le package
java.util
§ Définies à partir de deux Interfaces Java:
§ Collection
§ Map
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
3/29
Les Collections
Introduction
Les collections
Les HashMaps
§ Définies à partir de la racine Interface Collection.
§ Les classes collection (qui implémentent l’interface Collection)
sont nombreuses dans l’API Java:
AbstractCollection, AbstractList, AbstractQueue,
AbstractSequentialList, AbstractSet, ArrayBlockingQueue,
ArrayDeque, ArrayList, AttributeList,
BeanContextServicesSupport, BeanContextSupport,
ConcurrentLinkedQueue, ConcurrentSkipListSet,
CopyOnWriteArrayList, CopyOnWriteArraySet, DelayQueue,
EnumSet, HashSet, JobStateReasons, LinkedBlockingDeque,
LinkedBlockingQueue, LinkedHashSet, LinkedList,
PriorityBlockingQueue, PriorityQueue, RoleList,
RoleUnresolvedList, Stack, SynchronousQueue, TreeSet,
Vector
§ Nous verrons: ArrayList, LinkedList, HashSet
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
4/29
Les tableaux dynamique: ArrayList
Introduction
Les collections
Les HashMaps
§ Tableaux dynamiques
§ Dynamique = la taille (nombres d’éléments) du tableau n’est
pas fixe et peut varier en cours d’exécution
§ L’acces a ses éléments est direct, comme dans un tableau
§ L’opération d’ajout et de suppression nécessitent un
réarrangement des éléments (automatique) pour qu’ils soient
toujours contigus (comme dans un tableau)
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
5/29
ArrayList: construction
Introduction
Les collections
Les HashMaps
§ Déclaration / construction:
§ ArrayList ăEą v1 = new ArrayListăEą(); // vecteur
dynamique vide
§ ArrayList ăEą v2 = new ArrayList ăEą(c); /* vecteur
dynamique contenant tous les éléments de la collection c */
§ Exemple:
ArrayList ăStringą A1=new ArrayList ăStringą();
ArrayList ăStringą A2=new ArrayList ăStringą (A1);//A2
contient les mêmes éléments que A1
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
6/29
ArrayList: méthodes usuelles
Introduction
Les collections
Les HashMaps
§ Ajout d’un élément en fin de vecteur:
v1.add(elem);
§ Acces au ieme élément:
e = v1.get( n ); // acces au neme élément du vecteur v1
§ Suppression du ième élément du vecteur (avec retour dans e)
E e = v1.remove( n ); // suppression du nème élément
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
7/29
Exemple
public class Personne {
private int cin, age;
private String Nom, Prenom;
Personne(int c, String n, String
p, int a){
cin=c;
Nom=n;
Prenom=p;
age=a;
}
public void afficher(){
CIN:
System.out.println(”Le
”+cin+” Le nom: ”+Nom+”
Le
”+Prenom+
prenom:
”L’age: ”+age); }
}
Chapitre 5 - Les collections, M. Chebbah
Introduction
Les collections
Les HashMaps
public static void main(String[]
args) {
ArrayList ăPersonneą A1=new
ArrayList ăPersonneą();
Publicité
Per-
p1=new
Personne
sonne(12345678,”Salah”,”Mohamed”,23);
A1.add(p1);
ArrayList ăPersonneą A2=new
ArrayList ăPersonneą (A1);
A1.remove(0);
A2.get(0).afficher();
}
Semestre 1, 2020
8/29
LinkedList: construction
Introduction
Les collections
Les HashMaps
§ Listes doublement chaˆınées
§ Déclaration / construction
§ LinkedListăEą l1 = new LinkedListăEą (); // liste vide
§ LinkedListăEą l2 = new LinkedListăEą (l1); /* liste
contenant tous les éléments de la collection c */
§ Exemple:
LinkedList ăPersonneą L1=new LinkedList ăPersonneą();
LinkedList ăPersonneą L2=new LinkedList
ăPersonneą(L1);//L2 contient les mêmes éléments que L1
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
9/29
LinkedList: Ajout, accès et suppréssion
Introduction
Les collections
Les HashMaps
§ Ajout d’un élément elem de type E au début / fin de la liste
§ l1.addFirst(elem);
§ l1.addLast(elem);
§ Accès au premier / dernier élément de la liste
§ E elem = l1.getFirst();
§ elem = l1.getLast();
§ Suppression du premier / ième / dernier élément
§ l1.remove();
§ elem = l1.removeFirst();
§ elem = l1.remove(i);
§ elem = l1.removeLast();
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
10/29
Exemple
Introduction
Les collections
Les HashMaps
public static void main(String[] args){
LinkedList ăPersonneą L1=new LinkedList ăPersonneą();
Personne p1=new Personne(12345678,”Salah”,”Mohamed”,23);
Personne p2=new Personne(23416789,”Ali”,”Mohamed”,24);
Personne p3=new Personne(98765436,”Tounsi”,”Mohamed”,32);
L1.add(p1);
L1.addFirst(p2);
L1.add(1,p3);
LinkedList ăPersonneą L2=new LinkedList ăPersonneą(L2);
L2.remove(1);
L2.getFirst().afficher();
L2.getLast().afficher();
}
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
11/29
Exemple
Introduction
Les collections
Les HashMaps
Résultat de l’exécution:
Le CIN: 23416789 Le nom: Ali Le prenom: Mohamed L’age: 24
Le CIN: 12345678 Le nom: Salah Le prenom: Mohamed L’age: 23
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
12/29
LinkedList:Parcours
Introduction
Les collections
Les HashMaps
§ La liste peut être parcourue par un itérateur bidirectionnel
ListIterator
IteratorăEą iter = l1.iterator() //iter désigne le début de
la liste
§ Avancer / reculer d’un élément et retourner l’élément
§ e = iter.next();
§ e = iter.previous();
§ Ajout d’un élément à la position courante
iter.add(elem); // si fin de liste: ajout à la fin
§ Suppression de l’élément à la position courante
iter.remove(); // supprime le dernier élément retourné par
next ou previous
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
13/29
Exemple
Introduction
Les collections
Les HashMaps
public static void main(String[] args) {
LinkedList ăPersonneą L1=new LinkedList ăPersonneą();
Personne p1=new Personne(12345678,”Salah”,”Mohamed”,23);
Personne p2=new Personne(23416789,”Ali”,”Mohamed”,24);
Personne p3=new Personne(98765436,”Tounsi”,”Mohamed”,32);
L1.add(p1);
L1.addFirst(p2);
L1.add(1,p3);
Iterator ăPersonneą iter=L1.iterator();
while(iter.hasNext()){
iter.next().afficher();
}
}
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
14/29
Exemple
Introduction
Les collections
Les HashMaps
Résultat de l’exécution:
Le CIN: 23416789 Le nom: Ali Le prenom: Mohamed L’age: 24
Le CIN: 98765436 Le nom: Tounsi Le prenom: Mohamed L’age: 32
Le CIN: 12345678 Le nom: Salah Le prenom: Mohamed L’age: 23
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
15/29
Les ensembles: HashSet (et TreeSet)
Introduction
Les collections
Les HashMaps
§ 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
Publicité
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)
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
16/29
Les ensembles: HashSet (et TreeSet)
Introduction
Les collections
Les HashMaps
§ 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
§ Exemple:
public class Personne {
private int cin, age;
private String Nom, Prenom;
String n,
Personne(int
c,
String p, int a){
cin=c;
Nom=n;
Prenom=p;
age=a;
}
Chapitre 5 - Les collections, M. Chebbah
public void afficher(){
System.out.println(”Le
CIN:
”+cin+” Le nom: ”+Nom+”
”+Prenom+
prenom:
Le
”L’age: ”+age); }
public int hashCode(){
return
Nom.hashCode()+Prenom.hashCode();
}
}
Semestre 1, 2020
17/29
HashSet: méthodes usuelles
Introduction
Les collections
Les HashMaps
§ contains: test d’appartenance
boolean appartient = e.contains(elem); // elem
appartient-il à e ?
§ remove: suppression d’un élément
boolean trouve = e.remove(elem); //false si elem
n’appartient pas à e
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
18/29
HashSet: parcours
Introduction
Les collections
Les HashMaps
§ Parcours à l’aide d’un itérateur
HashSetăEą e = new HashSetăEą (); // ajouts
d’éléments à l’ensemble
Iterator ăEą iter = e.iterator();
while (iter.hasNext()) {
E elem = iter.next();
System.out.println(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
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
19/29
Exemple
Introduction
Les collections
Les HashMaps
public static void main(String[] args) {
HashSet ăPersonneą hset=new HashSet ăPersonneą();
Personne p1=new Personne(12345678,”Salah”,”Mohamed”,23);
Personne p2=new Personne(23416789,”Ali”,”Mohamed”,24);
Personne p3=new Personne(98765436,”Tounsi”,”Mohamed”,32);
hset.add(p1);
hset.add(p2);
hset.add(p3);
Iterator ăPersonneą iter=hset.iterator();
while(iter.hasNext()){
iter.next().afficher();
}
}
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
20/29
Introduction aux fonctions (Map)
Introduction
Les collections
Les HashMaps
§ 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ą )
§ Une Map 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)
§ Application: chaque fois qu’il faut retrouver une valeur en
fonction d’une clé. Exemple: dans un dictionnaire: mot -ą
définition du mot; dans un annuaire: nom de personne -ą
adresse et n˚de tél; localisation: avion -ą aéroport, etc.
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
21/29
Introduction aux fonctions (Map)
Introduction
Les collections
Les HashMaps
§ Les classes Map: AbstractMap, AuthProvider,
ConcurrentHashMap, ConcurrentSkipListMap, EnumMap,
HashMap, Hashtable, IdentityHashMap, LinkedHashMap,
Provider, RenderingHints, SimpleBindings,
TabularDataSupport, TreeMap, UIDefaults, WeakHashMap
§ Nous verrons: HashMap
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
22/29
Les fonctions (map): HashMap
Introduction
Les collections
Les HashMaps
Publicité
§ 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 ou encore dictionnaire
§ En Java, les collections de type fonction, sont définies à partir
de la racine Interface Map ăK, Vą
§ 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 String, hashCode et equals sont déjà
définies dans la classe String -ą l’utilisateur n’a pas besoin de
les définir
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
23/29
HashMap: construction
et méthodes usuelles
Introduction
Les collections
Les HashMaps
§ 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 (ou mise à jour de la valeur si la clé
existe)
// map vide
Exemple: m.put(cle, val); // où clé objet de type K, val
objet de type V
§ Cas particulier: val peut être de type primitif int, float, char,
. . .
Exemple: m.put(”occiden”, 1);
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
24/29
HashMap: construction
et méthodes usuelles (2/2)
Introduction
Les collections
Les HashMaps
§ get: récupere la valeur associée a une clé.
Exemple:
String cle = ”occident”;
Integer val = m.get(cle);
if (val == null) System.out.println(”cette clé n’existe pas !
”);
§ remove: suppression d’une paire en fonction de la clé.
Exemple:
§ m.remove(cle); // supprime la paire (”occident” , val )
§ Integer val = m.remove(cle); // retourne la valeur, null
”occident”
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
25/29
HashMap: parcours
Introduction
Les collections
Les HashMaps
§ 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 ăMap.EntryăK,Vąą paires = m.entrySet(); //
ensemble de paires
Iterator ăMap.EntryăK,Vąą iter = paires.iterator(); //
itérateur
while (iter.hasNext()) {
Map.Entry ăK, Vą paire = iter.next(); // paire courante
System.out.println(paire); // affichage de la paire courante
K cle = paire.getKey(); // acces a la clé
V val = paire.getValue(); // acces a la valeur
}
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
26/29
Exemple
Introduction
Les collections
Les HashMaps
import java.util.*; // HashMap, Map, Iterator, Set
public class HashMapDemo{
public static void main(String args[]) {
/ Déclaration du HashMap persAge /
HashMapăString, Integerą persAge = new HashMapăString,
Integerą();
/ Ajouter des entrées dans le HashMap persAge/
persAge.put(”Myriam”, 28);
persAge.put(”Malek”, 33);
persAge.put(”Mohamed”, 45);
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
27/29
Exemple
Introduction
Les collections
Les HashMaps
/ Afficher le contenu de persAge en utilisant un itérateur /
Set paires = persAge.entrySet(); // crée en ensemble de paires à
partir du HashMap
Iterator ăMap.EntryăString,Integerąą iter = paires.iterator();
while (iter.hasNext()) {
Map.Entry paire = iter.next();
System.out.println( paire.getKey() + ” âge ” + paire.getValue());
}
/ Retrouver une valeur en donnant la clé / System.out.println(
”Myriam a ” + persAge.get( ”Myriam”) + ” ans”);
/ Mettre a jour la valeur associée a une clé /
persAge.put(”Mohamed”, 40);
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
28/29
Exemple
Introduction
Les collections
Les HashMaps
System.out.println( ”Mohamed a rajeuni ! Nouvel âge: ” +
persAge.get(”Mohamed”));
/ Supprimer une entrée /
persAge.remove(”Mohamed”); // Mohamed est mort . . .
}
}
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
29/29