<!-- Slide number: 9 -->

Collections : Architecture

9


<!-- Slide number: 10 -->

Collections : Architecture

10

• Les java.util.List (listes) sont une suite d'éléments ordonnés accessibles par leur indice (leur place dans la liste). Les listes ne garantissent pas l'unicité des éléments.

Les java.util.Set (ensembles) sont un groupe d'éléments uniques

• Les java.util.Map (associations) mémorisent une collection de couples clé-valeur. Si vous avez une clé, l'association retrouvera la valeur associée à cette clé. Les clés sont uniques, mais la même valeur peut-être associée à plusieurs clés.

<!-- Slide number: 11 -->

Interface Collection

11

Un objet qui est un groupe d'objets

Principales méthodes :

boolean add(Object obj)

boolean contains(Object obj)

boolean containsAll(Collection collection)

int size()

Object[] toArray()

Object[] toArray(Object[] tableau)

<!-- Slide number: 12 -->

12

List

12

<!-- Slide number: 13 -->

List

13

Les objets appartenant à la catégorie List sont des tableaux extensibles à volonté. On y trouve les objets « Vector »,  « LinkedList » et « ArrayList ».

Vous pouvez y insérer autant d'éléments que vous le souhaitez sans craindre de dépasser la taille de votre tableau.

<!-- Slide number: 14 -->

Classe ArrayList<E> Vs vector

14

java.util.Vector

java.util.ArrayList

utilise un tableau en interne pour ranger les données,

fournit un accès aux éléments par leur indice très performant et est optimisé pour des opérations d'ajout/suppression d'éléments en fin de liste,

Les emplacements sont repérés par des nombres entiers (à partir de 0)

Synchronisé par défaut (4x plus lent que ArrayList)

est une classe dite "thread-safe", c'est-à-dire que plusieurs processus peuvent l'utiliser en même temps sans risque de perte de données.

<!-- Slide number: 15 -->

ArrayList

15

La classe « ArrayList » implémente un tableau d’objets qui peut grandir ou rétrécir à la demande, ce qui débarrasse le programmeur de la gestion de la taille du tableau.

Comme pour un tableau on peut accéder à un élément du « ArrayList », par un indice.

<!-- Slide number: 16 -->

ArrayList(Exemple)

16

import java.util.ArrayList;

public class Test {

public static void main(String[] args) {

ArrayList al = new ArrayList();

al.add(12);

al.add("Une chaîne de caractères !");

al.add(12.20f);

al.add('d');

for(int i = 0; i < al.size(); i++) {

System.out.println("donnée à l'indice " + i + " = " + al.get(i)); }

}}

<!-- Slide number: 17 -->

17

Tri et recherchedans une LIST

<!-- Slide number: 18 -->

Classe Collections

18

Cette classe ne contient que des méthodes static, utilitaires pour travailler avec des collections pour effectuer des opérations de :

trie (sur listes)

recherches (sur listes)

copies

minimum et maximum

<!-- Slide number: 19 -->

Tri

19

Afin de trier une liste, :

Collections.sort(l);

Pour que La liste soit correctement triée, il faut que les éléments de la liste soient mutuellement comparables

Plus exactement, la méthode sort() ne fonctionnera que si tous les éléments de la liste sont d’une classe qui implémente l’interface java.lang.Comparable<? super E>

<!-- Slide number: 20 -->

Tri

20

Il est possible d’utiliser la méthode sort de la classe Collections , dans le cas ou souhaite préciser le critère de tri à adopter, comme suit :

sort(List<T> list, Comparator<? Super T> c)

<!-- Slide number: 21 -->

Interface Comparable<T>

21

Cette interface correspond à l’implantation d’un ordre naturel dans les instances d’une classe

Redéfinir la méthode

public int compareTo (Object o) avec

a.compareTo (b) == 0 si a.equals To(b)

a.compareTo (b) < 0 si a plus « petit »que b

a.compareTo (b) > 0 si a plus « grand » que b

<!-- Slide number: 22 -->

Interface Comparator<T>

22

C’est possible de trier la liste d’une autre manière, en créant classe qui implantera l’interface java.util.Comparator, afin de comparer deux éléments de la collection

Il faut implémenter cette méthode:

Pour utiliser le critère de tri qui est implémenté précédemment, il faut appeler une instance de cette classe en paramètre de la méthode sort()

int compare(T o1, T o2) qui doit renvoyer

un entier positif si o1 est « plus grand » que o2

0 si o1 a la même valeur (au sens de equals) que o2

un entier négatif si o1 est « plus petit » que o2

<!-- Slide number: 23 -->

23

SET

23

<!-- Slide number: 24 -->

Set<E>

24

Set: est un ensemble ne contenant que des valeurs, 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.

Un ensemble (Set) est une collection qui n'autorise pas l'insertion de doublons.

SortedSet est un Set trié.

<!-- Slide number: 25 -->

Set<E>

25

Méthodes de Set<E>

sens du hashCode à l’objet passé en paramètre sera enlevé

la méthode add n’ajoute pas un élément si un élément égal est déjà dans l’ensemble

Set : TreeSet et HashSet

Le choix entre ces deux objets est lié à la nécessité de trier les éléments :

les éléments d'un objet HashSet ne sont pas triés : l'insertion d'un nouvel élément est rapide

les éléments d'un objet TreeSet sont triés : l'insertion d'un nouvel élément est plus long

<!-- Slide number: 26 -->

Interface SortedSet

26

Cette interface définit une collection de type ensemble triée par un comparateur.

Elle hérite de l'interface Set.

Définit les méthodes suivantes:

Comparator<? super E> comparator() : Renvoie le comparateur utilisée pour définir l'ordre

E first(), last() : Renvoie le premier/dernier élément

Très peu utilisée car SortedSet ne définie pas assez de méthodes et ne possédait qu'une implémentation => TreeSet

<!-- Slide number: 27 -->

Classe HashSet<E>

27

Cette classe est un ensemble sans ordre de tri particulier.

Les éléments sont stockés dans une table de hashage : cette table possède une capacité.

Cette classe ne vérifie l’égalité que pour les objets qui ont le même hashCode

<!-- Slide number: 28 -->

Classe HashSet<E>

28

import java.util.*;

public class TestHashSet {

public static void main(String args[]) {

Set set = new HashSet();

set.add("CCCCC");

set.add("BBBBB");

set.add("DDDDD");

set.add("BBBBB");

set.add("AAAAA");

}

Resultat : {CCCCC, BBBBB, DDDDD, AAAAA }

<!-- Slide number: 29 -->

TreeSet

29

Cette classe est un arbre qui représente un ensemble trié d'éléments.

L'insertion d'un nouvel élément dans un objet de la classe TreeSet est donc plus lent mais le tri est directement effectué.

L'ordre utilisé est celui indiqué par les objets insérés s’ils implémentent l'interface Comparable pour un ordre de tri naturel ou fournir un objet de type Comparator au constructeur de l'objet TreeSet pour définir l'ordre de tri.

<!-- Slide number: 30 -->

Classe TreeSet<E>

30

import java.util.*;

public class TestHashSet {

public static void main(String args[]) {

Set ts = new TreeSet();

ts.add("one");

ts.add("two");

ts.add("three");

ts.add("four");

ts.add("three");

System.out.println("TreeSet = " + ts);

}

}

Resultat : TreeSet = [four, one, three, two]

<!-- Slide number: 31 -->

Classes Utilitaires

31

Collections (avec un s) fournit des méthodes static pour

Trier une collection

Faire des recherches rapides dans une collection triée

Arrays fournit des méthodes static pour

Trier

Faire des recherches rapides dans un tableau trié

Transformer un tableau en liste

<!-- Slide number: 32 -->

32


<!-- Slide number: 33 -->

33

MAP

33

<!-- Slide number: 34 -->

Interface Map

34

L’interface Map<K,V> correspond à un groupe de couples clés-valeurs

La clé est unique, contrairement à la valeur qui peut être associée à plusieurs clés (Dans la map il ne peut pas exister 2 clés égales)

Les deux classes qui Implemente l’interface:

HashMap<K,V>, table de hachage ; garantit un accès en temps constant

TreeMap<K,V>, arbre ordonné suivant les valeurs des clés avec accès en log(n) ;

La comparaison utilise l’ordre naturel (interface Comparable<K>) ou une instance de Comparator<? super K>

<!-- Slide number: 35 -->

Interface Map

35

<<abstrract>>

AbstractMap<K, V>

<<interface>>

Map<K, V>

<<interface>>

SortedMap <K, V>

TreeMap<K, V>

HashMap<K, V>

<!-- Slide number: 36 -->

Interface Map : les méthodes

36

ajouter et enlever des couples clé – valeur

savoir si une table contient une clé

savoir si une table contient une valeur

récupérer une référence à un des éléments donnant sa clé

récupérer les clés

récupérer les valeurs

Object put(K clé, V valeur)

void putAll(Map<? extends K, ? extends V>map)

void remove(Object key)

boolean containsKey(Object clé)

boolean containsValue(Object valeur)

Set<Map.Entry<K,V>> entrySet()

V get(Object clé)

boolean isEmpty()

Set<K> keySet()

int size()

Collection<V> values()

<!-- Slide number: 37 -->

Interface Map : les méthodes d’itération

37

Soit la Map : Map<Integer, String> map;

// iterer sur les clés

for (Integer i : map.keySet)

System.out.println("Key « +i+ "Value" +map.get(i));

// iterer sur la paire clé/valeur

for(Map.Entry<Integer, String> entry : map.entrySet())

{

System.out.println(entry.getKey());

System.out.println(entry.getValue());

}

<!-- Slide number: 38 -->

Interface Map : Map.Entry<K,V>

38

L’interface Map contient l’interface interne public Map.Entry<K,V> qui correspond à un couple clé-valeur

Cette interface contient 3 méthodes

La méthode entrySet() de Map renvoie un objet de type « ensemble (Set) de Entry »

K getKey()

V getValue()

V setValue(V valeur)

<!-- Slide number: 39 -->

Interface Map : récupération des données

39

Récupérer les clés sous forme de Set<K> avec la méthode iterator() de l’interface Set<K> pour récupérer une à une les clés

Récupère les valeurs sous forme de Collection<V> avec la méthode iterator() de l’interface Collection<V> pour récupérer un à un les éléments

Récupère les entrées (clé-valeur) sous forme de Set<Entry<K,V>> avec la méthode iterator() de l’interface Set<Entry<K,V>> pour récupérer une à une les entrées

keySet()

values()

entrySet()

<!-- Slide number: 40 -->

HashMap et hashCode()

40

La classe HashMap<K,V> utilise la structure informatique nommée « table de hachage » pour ranger les clés

La méthode hashCode() (héritée de Object ou redéfinie) est utilisée pour répartir les clés dans la table de hachage

Deux objets identiques ont le même hashCode.

Deux objets ayant le même hashCode ne sont pas forcément identiques.