Fichier PDF

Partagez, hébergez et archivez facilement vos documents au format PDF

Partager un fichier Mes fichiers Boite à outils PDF Recherche Aide Contact



13 java collections framework .pdf



Nom original: 13-java collections framework.pdf
Auteur: Bruno Quoitin

Ce document au format PDF 1.4 a été généré par Impress / LibreOffice 3.6, et a été envoyé sur fichier-pdf.fr le 04/06/2013 à 22:00, depuis l'adresse IP 91.177.x.x. La présente page de téléchargement du fichier a été vue 892 fois.
Taille du document: 339 Ko (42 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Programmation
et
Algorithmique
II
Ch.13 – Java Collections
Framework
Bruno Quoitin
(bruno.quoitin@umons.ac.be)

(c) 2010, Bruno Quoitin (UMons)

1

Table des Matières
1. Introduction
1. Collection
2. Map

2. Itérateur
3. Conversion de / vers tableau
4. Table de hachage

(c) 2010, Bruno Quoitin (UMons)

2

Java Collections Framework


Introduction


Une Collection est un terme générique désignant une structure
de données abstraite destinée à conserver un ensemble d'autres
objets (ou les références vers ces objets)



Une collection possède des méthodes qui permettent
typiquement





d'ajouter un objet à la collection



de supprimer un objet de la collection



de récupérer un objet ou tous les objets de la collection.

Il existe plusieurs types de collections. Ceux-ci diffèrent selon les
opérations disponibles et les contraintes imposées sur
l'ensemble d'objets.

(c) 2010, Bruno Quoitin (UMons)

3

Java Collections Framework


Types de collections


Les collections peuvent être classées selon leurs
comportements et propriétés. On distingue souvent les
collections selon les axes suivants :



Ordre




Type des éléments




tous les éléments de la collection sont-ils du même type
(collections homogènes) / de types différents (collections
hétérogènes) ?

Duplication




la collection garde-t-elle les éléments dans un certain ordre /
dans n'importe quel ordre ?

les éléments dupliqués sont-ils admis ?

Méthodes d'accès


accès séquentiel / aléatoire ?

(c) 2010, Bruno Quoitin (UMons)

4

Java Collections Framework


Introduction


La bibliothèque Java fournit le Java Collections Framework
(JCF), un ensemble important d'interfaces, classes et méthodes
destinés à manipuler des collections d'objets. Le JCF comprend



Interfaces de collections







décrivent les services fournis par différentes collections



p.ex. List, Map, ...

Implémentations de collections


classes concrètes



p.ex. ArrayList, LinkedList, ...

Algorithmes



travaillant sur les collections
p.ex. des algorithmes de tri, de recherche, ... (sort,
binarySearch, shuffle, ...)

(c) 2010, Bruno Quoitin (UMons)

5

Table des Matières
1. Introduction
1. Collection
2. Map

2. Itérateur
3. Conversion de / vers tableau
4. Table de hachage

(c) 2010, Bruno Quoitin (UMons)

6

Java Collections Framework


Interface Collection


Le plus petit élément commun aux collections du JCF est
l'interface Collection (java.util). Cette interface définit les
opérations liées à la gestion d'un ensemble quelconque
d'éléments.
public interface Collection<E>
extends Iterable<E>
{
boolean
add(E o);
boolean
addAll(Collection<? extends E> c);
void
clear();
boolean
contains(E o);
boolean
isEmpty();
Iterator<E> iterator();
boolean
remove(E o);
boolean
removeAll(Collection<?> c);
int
size();
Object []
toArray();
<T> T[]
toArray(T[] a);
/* ... */
}

(c) 2010, Bruno Quoitin (UMons)

7

Java Collections Framework


Hiérarchie de classes Collection
Collection
List

Queue

AbstractList

AbstractQueue

Interfaces

Set
SortedSet

AbstractSequentialList

HashSet
ArrayList

(c) 2010, Bruno Quoitin (UMons)

Vector
Stack

LinkedList
PriorityQueue

Classes
concrètes

TreeSet

Classes
abstraites

AbstractSet

8

Java Collections Framework


Hiérarchie de classes Collection


Brève description des classes et de leurs caractéristiques



TreeSet




HashSet




ensemble, duplication non autorisée, implémentation basée sur
table de hachage.

ArrayList




ensemble trié (ordre défini par Comparable), duplication non
autorisée, implémentation basée sur un arbre.

séquence, accès aléatoire.

LinkedList


séquence, accès aléatoire possible mais peu performant.



permet des insertions et suppressions à des positions quelconques

(c) 2010, Bruno Quoitin (UMons)

9

Java Collections Framework


Hiérarchie de classes Collection


Brève description des classes et de leurs caractéristiques (suite)



PriorityQueue




Vector




permet de retirer efficacement le plus petit élément
similaire à ArrayList, thread safe, historique

Stack


pile implémentée sur base de Vector, historique

(c) 2010, Bruno Quoitin (UMons)

10

Table des Matières
1. Introduction
1. Collection
2. Map

2. Itérateur
3. Conversion de / vers tableau
4. Table de hachage

(c) 2010, Bruno Quoitin (UMons)

11

Java Collections Framework


Associations (Map)


Le JCF définit également des classes permettant de conserver
l'association entre des paires d'éléments clés (keys) et valeurs
(values). Il est possible d'accéder aux valeurs d'une association
à l'aide de leurs clés (et pas seulement à l'aide d'un index
comme dans certaines collections).



Les clés et les valeurs de ces classes peuvent être récupérées
indépendamment comme des collections.

(c) 2010, Bruno Quoitin (UMons)

12

Java Collections Framework


Interface Map


L'interface Map (java.util) définit les opérations liées à
la gestion d'une association.
public interface Map<K,V>
{
void
clear();
boolean
containsKey(Object key);
boolean
containsValue(Object value);
Set<Map.Entry<K,V>>
entrySet();
V
get(Object key);
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();
...
}

(c) 2010, Bruno Quoitin (UMons)

13

Java Collections Framework


Hiérarchie de classes Map
Map

Interfaces

SortedMap

Classes
abstraites

AbstractMap

HashMap

(trié, basé
sur arbre)

(non-trié, basé
sur table de hachage)

(c) 2010, Bruno Quoitin (UMons)

Hashtable

Classes
concrètes

TreeMap

14

Java Collections Framework


Hiérarchie de classes Map


Brève description des classes


HashMap : une structure de données permettant d'associer
des clés à des valeurs



TreeMap : HashMap dans laquelle les clés sont triées



Hashtable : similaire à HashMap, thread-safe, historique

(c) 2010, Bruno Quoitin (UMons)

15

Table des Matières
1. Introduction
1. Collection
2. Map

2. Itérateur
3. Conversion de / vers tableau
4. Table de hachage

(c) 2010, Bruno Quoitin (UMons)

16

Itérateur


Introduction


Il existe deux modes typiques pour parcourir les éléments d'une
collection.



Accès aléatoire






Chaque élément est accédé indépendamment sur base de son
index.
Cet accès est possible grâce aux méthodes get() et set() de
l'interface List par exemple.

Accès séquentiel





L'ensemble des éléments de la collection est parcouru.
L'ordre dans lequel les éléments sont parcourus dépend tu type de
données (p.ex. index croissants pour les listes, ordre de
Comparable pour TreeSet, ordre non défini pour HashSet).
L'accès séquentiel peut être réalisé en passant par un itérateur.

(c) 2010, Bruno Quoitin (UMons)

17

Itérateur


Principe


Un itérateur (iterator) est un objet capable de parcourir une
collection sans en révéler ni la structure interne ni
l'implémentation.



Un itérateur repose sur les deux primitives suivantes


Tester s'il y a encore des éléments à parcourir



Récupérer le prochain élément à parcourir





Ces deux primitives sont typiquement définies dans une interface
que de multiples collections peuvent supporter, indépendamment
de leur fonctionnement interne.

L'itérateur est un design pattern courant.

(c) 2010, Bruno Quoitin (UMons)

18

Itérateur


Principe


Dans le JCF, un itérateur prend la forme d'une implémentation
de l'interface Iterator
public interface Iterator<T> {
public boolean hasNext();
public T
next();
}



Indique s'il y a encore des
éléments à parcourir.
Retourne l'élément suivant à
parcourir. Ne doit être appelée
que si hasNext() a retourné
true.

Les classes qui supportent un itérateur implémentent l'interface
Iterable.


Cette interface définit une seule méthode qui permet de récupérer
une instance d'itérateur
public interface Iterable<T> {
public Iterator<T> iterator();
}



Note : l'interface Collection hérite d'Iterable.

(c) 2010, Bruno Quoitin (UMons)

19

Itérateur


Exemple


Exemple : utilisation « manuelle » d'un itérateur.

Collection<Carre> carres= ...;
Iterator<Carre> iter= carres.iterator();
while (iter.hasNext()) {
Carre c= iter.next();
/* Fait qquechose avec le carré */
}

(c) 2010, Bruno Quoitin (UMons)

20

Itérateur


Boucle for améliorée


Depuis la version 5.0 de Java, le langage fournit une structure
de boucle for supplémentaire appelée la boucle for-each ou
boucle for améliorée (enhanced for).



L'objectif de cette boucle est de parcourir séquentiellement
l'ensemble des éléments d'un tableau ou d'une Collection.
Elle permet de rendre le code plus compact et plus lisible.



La syntaxe de la boucle for améliorée est la suivante
for ( nomType nomVariable : tableau/collection )
blocInstructions



La boucle for améliorée ne peut être utilisée que sur une
instance qui supporte l'interface Iterable.

(c) 2010, Bruno Quoitin (UMons)

21

Itérateur


Boucle for améliorée


Exemple

Collection<Carre> carres= ...;
for (Carre c : carres) {
/* Fait qquechose avec le carré */
}



Note : il s'agit d'un simple « sucre syntaxique » (une
simplification syntaxique). En effet, le code suivant est traduit par
le compilateur de façon à utiliser un itérateur, de la même façon
que le code montré ci-dessous.

Collection<Carre> carres= ...;
Iterator<Carre> iter= carres.iterator();
while (iter.hasNext()) {
Carre c= iter.next();
/* Fait qquechose avec le carré */
}
(c) 2010, Bruno Quoitin (UMons)

22

Itérateur


Autres itérateurs


Certaines collections peuvent fournir des itérateurs plus
spécifiques. Par exemple, ListIterator fourni par
LinkedList permet d'avancer mais également de reculer lors du
parcours d'une liste chaînée.
public interface ListIterator<E>
{
void
add(E e);
boolean hasNext();
boolean hasPrevious();
E
next();
E
previous();
void
remove();
void
set(E e);
}



Dans le passé, l'API Java a également utilisé un itérateur appelé
Enumeration qui fournissait des méthodes hasMoreElements()
et nextElement().

(c) 2010, Bruno Quoitin (UMons)

23

Itérateur


Implémenter un itérateur


Soit la classe MyLinkedList qui implémente l'ADT Liste avec
une liste chaînée. Comment implémenter un itérateur pour
MyLinkedList ?



Résumé de la classe MyLinkedList
public class MyLinkedList<T>
implements Iterable<T>
{
private MyNode head;

Référence vers la tête de liste.

public void add(T o) { ... }
public void remove(T o) { ... }
public Iterator<T> iterator() { ... }
...
private class MyNode {
public T data;
public MyNode next;
}
}

(c) 2010, Bruno Quoitin (UMons)

Classe interne qui représente
un noeud de la liste chaînée.

24

Itérateur


Implémentation


La classe MyLinkedList fournit sa propre implémentation de
l'interface itérateur comme classe privée.

private class MyIteratorImpl implements Iterator<T> {
private MyNode next;
public MyIteratorImpl(MyLinkedList l) {
this.next= l.head;
}

Cette variable d'instance
représente l'état actuel
de l'itérateur (sa position
dans la liste).

public boolean hasNext() {
return (next != null);
}

}

public T next() {
T o= next.data;
next= next.next;
return o;
}

(c) 2010, Bruno Quoitin (UMons)

25

Itérateur


Implémentation


Une instance de MyLinkedList peut retourner une instance de
la classe itérateur interne et privée en utilisant le design pattern
factory.

public class MyLinkedList<T>
implements Iterable<T> {
...
public Iterator<T> iterator() {
return new MyIteratorImpl(this);
}
...
}
MyLinkedList<String> l= new MyLinkedList<String>();
...
for (String s: l)
System.out.println(s);

(c) 2010, Bruno Quoitin (UMons)

26

Visiteur


Parcours avec visiteur


Autre moyen de parcourir une structure de données sans en
révéler l'implémentation : le design pattern visiteur (visitor).



Dans l'itérateur, c'est le client qui récupère chaque élément
séquentiellement (avec hasNext() et next()). Avec le visiteur,
le client fournit une instance de classe qui est invoquée pour
chaque élément par la structure de données.

public interface MyVisitor {
public void visit(Object o);
}
public void walk(MyVisitor v) {
MyNode temp= head;
while (temp != null) {
v.visit(temp.data);
temp= temp.next;
}
}
(c) 2010, Bruno Quoitin (UMons)

27

Visiteur


Parcours avec visiteur


Exemple d'utilisation avec une classe visiteur anonyme.

MyLinkedList l= new MyLinkedList();
l.add("Titi");
l.add("Tutu");
l.add("Toto");
l.walk(new MyVisitor() {
public void visit(Object o) {
System.out.println(o);
}
});

(c) 2010, Bruno Quoitin (UMons)

28

Table des Matières
1. Introduction
1. Collection
2. Map

2. Itérateur
3. Conversion de / vers tableau
4. Table de hachage

(c) 2010, Bruno Quoitin (UMons)

30

Java Collections Framework


Conversion vers un tableau


L'interface Collection définit des méthodes permettant la
récupération des éléments d'une collection sous forme d'un
tableau.



La méthode de base permettant cette conversion est
Object [] toArray()



Exemple

Collection<Carre> carres= ...;
Object [] tableauCarres= carres.toArray();


Problème : il n'est pas possible d'effectuer la conversion
suivante (le compilateur accepte, mais la VM génère une
ClassCastException).

Collection<Carre> carres= ...;
Carre [] tableauCarres= (Carre []) carres.toArray();
(c) 2010, Bruno Quoitin (UMons)

31

Java Collections Framework


Conversion vers un tableau


Le JCF fournit une méthode alternative pour convertir une
collection vers un tableau correctement typé
<T> T [] toArray(T [] array)



Cette méthode utilise le tableau passé en argument pour
déterminer le type du tableau retourné.






Si le tableau passé en argument a une taille suffisante, les
éléments de la collection sont copiés dans ce tableau.
Sinon, un nouveau tableau est automatiquement alloué.

Note : il existe encore d'autres alternatives comme
Arrays.copyOf(...)

(c) 2010, Bruno Quoitin (UMons)

32

Java Collections Framework


Conversion vers un tableau


Exemple

Collection<Carre> carres= ...;
Carre [] tableauCarres= carres.toArray(new Carre [0]);
Deux allocations de tableaux sont
nécessaires : celui passé en argument et
celui créé par toArray.


Exemple

Collection<Carre> carres= ...;
Carre [] tableauCarres= carres.toArray(new Carre[carres.size()]);

Une seule allocation est effectuée.
Attention, le tableau retourné par
toArray est égal à celui passé en
argument.
(c) 2010, Bruno Quoitin (UMons)

33

Java Collections Framework


Conversion à partir d'un tableau




La conversion d'un tableau vers une instance de Collection
est également possible. La méthode de classe asList de la
classe utilitaire Arrays permet de créer une instance de List
sur base d'un tableau


static List asList(Object [] a)



static <T> List<T> asList(T ... a) depuis Java 1.5

Exemple

Carre [] tableauCarres= ...;
Collection carres= Arrays.asList(tableauCarres);
Carre [] tableauCarres= ...;
Collection<Carre> carres= Arrays.asList(tableauCarres);

(c) 2010, Bruno Quoitin (UMons)

34

Java Collections Framework


Conversion à partir d'un tableau


La plupart des implémentations de Collection fournissent un
constructeur permettant de créer une instance de la collection à
partir d'une autre instance.



Par exemple, TreeSet offre le constructeur




TreeSet(Collection c)

Exemple

Carre [] tableauCarres= ...;
Collection<Carre> carres=
new TreeSet(Arrays.asList(tableauCarres));

(c) 2010, Bruno Quoitin (UMons)

35

Table des Matières
1. Introduction
1. Collection
2. Map

2. Itérateur
3. Conversion de / vers tableau
4. Table de hachage

(c) 2010, Bruno Quoitin (UMons)

36

Table de hachage


Introduction


Une table de hachage(1) est une implémentation de l'ADT
association (map). Pour rappel, une association maintient des
paires clés / valeurs (k, v).



Une table de hachage utilise typiquement



un tableau de N cellules pour stocker les associations.
une fonction de hachage pour déterminer dans quelle cellule du
tableau une association doit être stockée.

(1) note : Les tables de hachage seront discutées en détails en BAC2 (« Structures de Données »). Cependant,
il est déjà utile d'en connaître le principe de fonctionnement.
(c) 2010, Bruno Quoitin (UMons)

37

Table de hachage


Fonction de hachage


Une fonction de hachage prend une clé k (de type Object) en
argument et retourne un entier h(k).




h : Object → int : k → h(k)

L'index dans le tableau d'une paire (k, v) est typiquement
obtenue par h(k) mod N

paire clé-valeur
(k, v)
index=h(k) mod N



Tableau
v
N cellules

Cette organisation permet d'effectuer des accès en temps
constant : O(1)

(c) 2010, Bruno Quoitin (UMons)

38

Table de hachage


Collisions


La fonction de hachage n'est généralement pas injective.



Par conséquent, il est possible que deux clés k1 et k2 donnent la
même position dans le tableau, i.e. h(k1) mod N = h(k2) mod N.



Cette situation est appelée collision.

(k1, v1)

index=h(k1) mod N

(k2, v2) index=h(k2) mod N

(c) 2010, Bruno Quoitin (UMons)

Tableau
???
N cellules

39

Table de hachage


Gestion des collisions


Une table de hachage gère les collisions en stockant les
associations dont la clé donne la même position dans une liste
de collisions (bucket).
(k1, v1)

Tableau
index=h(k1) mod N

(k2, v2) index=h(k2) mod N



Liste chaînée
(k1, v1)
(k2, v2)

La performance de l'accès à un élément de la table de hachage
peut alors dépendre de la longueur de la liste de collisions, et
par conséquent O(M) dans le pire des cas, où M est le nombre
d'éléments dans la table de hachage.

(c) 2010, Bruno Quoitin (UMons)

40

Table de hachage


Fonction de hachage en Java


En Java, une fonction de hachage est associée à chaque
instance. Cette fonction est définie par la classe Object sous la
forme de la méthode


int hashCode()



Par défaut, la méthode hashCode() retourne l'adresse en
mémoire de l'object.



Il est parfois nécessaire de surcharger la méthode hashCode()




Par exemple, la classe String, surcharge hashCode() de façon
que deux chaînes de même contenu mais situées à des adresses
différentes donnent la même valeur de hachage.
La valeur retournée par hashCode() est basée sur le contenu de
la chaîne. La fonction de hachage utilisée est la suivante
s.length−1

h(s)=

∑ ( 31i
i=0



(c) 2010, Bruno Quoitin (UMons)

× s.charAt (i))
41

Table de hachage


Table de hachage


L'exemple suivant illustre l'utilisation d'une table de hachage
sous la forme d'une instance de la classe HashMap.

Map<String,Integer> resultatsExamen=
new HashMap<String,Integer();
resultatsExamen.put("Bruno", 18);
resultatsExamen.put("Véronique", 16);
resultatsExamen.put("Jef", 12);
resultatsExamen.put("Hadrien", 17);
resultatsExamen.put("Tom", 17);
String key= "Tom";
System.out.println("Résultat de \""+key+"\" : "+
resultatsExamen.get(key));


Rappel: une clé est associée à une valeur unique !


utiliser 2 fois put() avec la même clé effectue un remplacement

(c) 2010, Bruno Quoitin (UMons)

42

Table de hachage


Table de hachage


L'exemple suivant illustre la récupération de l'ensemble des clés
et de l'ensemble des valeurs d'une association avec les
méthodes keySet() et values().

Map<String,Integer> resultatsExamen=
new HashMap<String,Integer();
/* ... */
Set<String> keys= resultatsExamen.keySet();
for (String s: keys)
System.out.println("Clé=\""+s+"\"");
Collection<Integer> values= resultatsExamen.values();
for (Integer i: values)
System.out.println("Valeur=\""+i+"\"");

(c) 2010, Bruno Quoitin (UMons)

43


Documents similaires


Fichier PDF 13 java collections framework
Fichier PDF structures repetitives 5
Fichier PDF notesdecours
Fichier PDF cahier des charges lpp
Fichier PDF check aiguilles
Fichier PDF reconnaitre des triangles des carres d es rectangles des disques et des angles droits


Sur le même sujet..