Programmation Orient´ee 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´ees
Introduction
Les collections
Les HashMaps
§ D´efinition: ‘’Une collection de donn´ees est un conteneur
d’´el´ements de mˆeme type qui poss`ede un protocole particulier
pour l’ajout, le retrait et la recherche d’´el´ements”
§ Exemples: pile, file, s´equence, ensemble et multi-ensemble,
fonction (tableau associatif ou map en anglais)
§ En Java, il existe 3 sortes de structures de donn´ees:
§ Les tableaux: Structure de taille fixe, acc`es direct aux ´elements
§ Les Collections:Structure modifiable, diff´erents algorithmes de
stockage
§ Les Map:Structure modifiable, stocke des couples cl´e, 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´efinies dans le package
java.util
§ D´efinies `a 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´efinies `a partir de la racine Interface Collection.
§ Les classes collection (qui impl´ementent 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’´el´ements) du tableau n’est
pas fixe et peut varier en cours d’ex´ecution
§ L’acces a ses ´el´ements est direct, comme dans un tableau
§ L’op´eration d’ajout et de suppression n´ecessitent un
r´earrangement des ´el´ements (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´eclaration / construction:
§ ArrayList ăEą v1 = new ArrayListăEą(); // vecteur
dynamique vide
§ ArrayList ăEą v2 = new ArrayList ăEą(c); /* vecteur
dynamique contenant tous les ´el´ements de la collection c */
§ Exemple:
ArrayList ăStringą A1=new ArrayList ăStringą();
ArrayList ăStringą A2=new ArrayList ăStringą (A1);//A2
contient les mˆemes ´el´ements que A1
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
6/29
ArrayList: m´ethodes usuelles
Introduction
Les collections
Les HashMaps
§ Ajout d’un ´el´ement en fin de vecteur:
v1.add(elem);
§ Acces au ieme ´el´ement:
e = v1.get( n ); // acces au neme ´el´ement du vecteur v1
§ Suppression du i`eme ´el´ement du vecteur (avec retour dans e)
E e = v1.remove( n ); // suppression du n`eme ´el´ement
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
7/29
Exemple
Publicité
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ą();
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´ees
§ D´eclaration / construction
§ LinkedListăEą l1 = new LinkedListăEą (); // liste vide
§ LinkedListăEą l2 = new LinkedListăEą (l1); /* liste
contenant tous les ´el´ements de la collection c */
§ Exemple:
LinkedList ăPersonneą L1=new LinkedList ăPersonneą();
LinkedList ăPersonneą L2=new LinkedList
ăPersonneą(L1);//L2 contient les mˆemes ´el´ements que L1
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
9/29
LinkedList: Ajout, acc`es et suppr´ession
Introduction
Les collections
Les HashMaps
§ Ajout d’un ´el´ement elem de type E au d´ebut / fin de la liste
§ l1.addFirst(elem);
§ l1.addLast(elem);
§ Acc`es au premier / dernier ´el´ement de la liste
§ E elem = l1.getFirst();
§ elem = l1.getLast();
§ Suppression du premier / i`eme / dernier ´el´ement
§ 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´esultat de l’ex´ecution:
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
Publicité
Les collections
Les HashMaps
§ La liste peut ˆetre parcourue par un it´erateur bidirectionnel
ListIterator
IteratorăEą iter = l1.iterator() //iter d´esigne le d´ebut de
la liste
§ Avancer / reculer d’un ´el´ement et retourner l’´el´ement
§ e = iter.next();
§ e = iter.previous();
§ Ajout d’un ´el´ement `a la position courante
iter.add(elem); // si fin de liste: ajout `a la fin
§ Suppression de l’´el´ement `a la position courante
iter.remove(); // supprime le dernier ´el´ement retourn´e 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´esultat de l’ex´ecution:
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´ee d’´el´ements de
type E, aucun ´el´ement ne peut apparaˆıtre plus d’une fois dans
un ensemble
§ Probl`eme: comme deux objets distincts ont des r´ef´erences
diff´erentes, on ne pourra jamais avoir deux objets ´egaux mˆeme
si toutes leurs valeurs sont identiques -ą Il faudra d´efinir un
comparateur qui sera capable de tester l’´egalit´e 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´efinir, pour l’utilisation d’un:
§ HashSet -ą les m´ethodes hashCode et equals dans la classe
des ´el´ements E
§ TreeSet -ą la m´ethode 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´ethodes usuelles
Introduction
Les collections
Les HashMaps
§ contains: test d’appartenance
Publicité
boolean appartient = e.contains(elem); // elem
appartient-il `a e ?
§ remove: suppression d’un ´el´ement
boolean trouve = e.remove(elem); //false si elem
n’appartient pas `a e
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
18/29
HashSet: parcours
Introduction
Les collections
Les HashMaps
§ Parcours `a l’aide d’un it´erateur
HashSetăEą e = new HashSetăEą (); // ajouts
d’´el´ements `a l’ensemble
Iterator ăEą iter = e.iterator();
while (iter.hasNext()) {
E elem = iter.next();
System.out.println(elem);
}
§ Remarques
§ Les ´el´ements d’un ensemble n’´etant pas ordonn´ees, aucun
ordre d’it´eration n’est assur´e
§ L’ordre d’it´eration 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´efinies `a 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´epart K `a un objet de
l’ensemble d’arriv´ee V ; on parle de paires (cl´e, valeur)
§ Application: chaque fois qu’il faut retrouver une valeur en
fonction d’une cl´e. Exemple: dans un dictionnaire: mot -ą
d´efinition du mot; dans un annuaire: nom de personne -ą
adresse et n˚de t´el; localisation: avion -ą a´eroport, 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
§ Fonction (Map ) = ensemble de paires (cl´e, valeur)
§ Notion proche de la fonction au sens math´ematique
§ En informatique, la fonction est aussi appel´ee tableau
associatif ou encore dictionnaire
§ En Java, les collections de type fonction, sont d´efinies `a partir
de la racine Interface Map ăK, Vą
§ Techniquement r´ealis´e par une table de hachage sur le
domaine des cl´es
§ Tout comme pour un HashSet, l’utilisateur doit d´efinir les
m´ethodes hashCode et equals dans la classe des cl´es K
§ Remarque: si K est String, hashCode et equals sont d´ej`a
d´efinies dans la classe String -ą l’utilisateur n’a pas besoin de
les d´efinir
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
23/29
HashMap: construction
et m´ethodes usuelles
Introduction
Les collections
Les HashMaps
§ D´eclaration / construction:
HashMap ăK, Vą m = new HashMap ăK, Vą (); //
map vide
Publicité
Exemple: HashMap ăString,Integerą m = new HashMap
ăString,Integerą();
§ put: ajout d’une paire (ou mise `a jour de la valeur si la cl´e
existe)
// map vide
Exemple: m.put(cle, val); // o`u cl´e objet de type K, val
objet de type V
§ Cas particulier: val peut ˆetre 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´ethodes usuelles (2/2)
Introduction
Les collections
Les HashMaps
§ get: r´ecupere la valeur associ´ee a une cl´e.
Exemple:
String cle = ”occident”;
Integer val = m.get(cle);
if (val == null) System.out.println(”cette cl´e n’existe pas !
”);
§ remove: suppression d’une paire en fonction de la cl´e.
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´eorie une map ne dispose pas d’it´erateur
§ En pratique, on utilise la m´ethode entrySet() d´efine dans la
classe HashMap pour cr´eer un ensemble `a partir du map
(l’ensemble des paires du map); puis on cr´ee un it´erateur 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´erateur
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´e
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´eclaration du HashMap persAge /
HashMapăString, Integerą persAge = new HashMapăString,
Integerą();
/ Ajouter des entr´ees 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´erateur /
Set paires = persAge.entrySet(); // cr´ee en ensemble de paires `a
partir du HashMap
Iterator ăMap.EntryăString,Integerąą iter = paires.iterator();
while (iter.hasNext()) {
Map.Entry paire = iter.next();
System.out.println( paire.getKey() + ” ˆage ” + paire.getValue());
}
/ Retrouver une valeur en donnant la cl´e / System.out.println(
”Myriam a ” + persAge.get( ”Myriam”) + ” ans”);
/ Mettre a jour la valeur associ´ee a une cl´e /
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 ˆage: ” +
persAge.get(”Mohamed”));
/ Supprimer une entr´ee /
persAge.remove(”Mohamed”); // Mohamed est mort . . .
}
}
Chapitre 5 - Les collections, M. Chebbah
Semestre 1, 2020
29/29