Cours de programmation avec Java Collections Framework

Programmation

et

Algorithmique II

Ch.13 – Java Collections

Framework

Bruno Quoitin

()

Table des Matières

1.   Introduction

1.   Collection

2.   Map

2.    Itérateur

3.    Conversion de / vers tableau

4.    Table de hachage

? 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.

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

?     la collection garde-t-elle les éléments dans un certain ordre / dans n'importe quel 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

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

–    Méthodes d'accès

?     accès séquentiel / aléatoire ?

?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, )

Table des Matières

1.    Introduction

1.  Collection

2.   Map

2.    Itérateur

3.    Conversion de / vers tableau

4.    Table de hachage

? Interface Collection

– Le plus petit élément commun aux collections du JCF est l'interface Collection (). Cette interface définit les opérations liées à la gestion d'un ensemble quelconque d'éléments.

? Hiérarchie de classes Collection

? Hiérarchie de classes Collection

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

–    TreeSet

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

–    HashSet

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

–    ArrayList

?   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

? Hiérarchie de classes Collection

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

–    PriorityQueue

?   permet de retirer efficacement le plus petit élément

–    Vector

?   similaire à ArrayList, thread safe, historique

–    Stack

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

Table des Matières

1.    Introduction

1.   Collection

2.   Map

2.    Itérateur

3.    Conversion de / vers tableau

4.    Table de hachage

? 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.

? Interface Map

– L'interface Map () définit les opérations liées à la gestion d'une association.

? Hiérarchie de classes Map

? 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

Table des Matières

1.    Introduction

1.   Collection

2.   Map

2.    Itérateur

3.    Conversion de / vers tableau

4.    Table de hachage

? 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.

? Principe

–    Un itérateur (iterator) est un objet capable de parcourir une collection sans en révéler ni la structure interne nil'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.

? Principe

–    Dans le JCF, un itérateur prend la forme d'une implémentation de l'interface Iterator

Indique s'il y a encore des

public interfaceIterator<T> {       éléments à parcourir.

public booleanhasNext();

publicTnext(); 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

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

? Exemple

– Exemple : utilisation « manuelle » d'un 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 (enhancedfor).

–    L'objectif de cette boucle est de parcourir séquentiellementl'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

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

?Boucleforaméliorée

–    Exemple

–    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.

? 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.

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

? 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>implementsIterable<T> {private MyNode head; Référence vers la tête de liste.

public void add(T o) {}public void remove(T o) {}  publicIterator<T> iterator() { }

private class MyNode { Classe interne qui représente     public T data; un noeud de la liste chaînée.     public MyNode next;

}

}

? Implémentation

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

? 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.

Visiteur

? Parcours avec visiteur

–    Autre moyen de parcourir une structure de données sans en révéler l'implémentation : le design patternvisiteur (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.

Visiteur

? Parcours avec visiteur

– Exemple d'utilisation avec une classe visiteur anonyme.

Table des Matières

1.    Introduction

1.   Collection

2.   Map

2.    Itérateur

3.    Conversion de / vers tableau

4.    Table de hachage

? 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

–    Exemple

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

? Conversion vers un tableau

–    Le JCF fournit une méthode alternative pour convertir une collection vers un tableau correctement typé

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

? Conversion vers un tableau

? 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

? 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

Table des Matières

1. Introduction

1.   Collection

2.   Map

2.    Itérateur

3.    Conversion de / vers tableau

4.    Table de hachage

? Introduction

–    Une table de hachage⁽¹⁾ 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 deNcellules 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.

? 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

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

? Collisions

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

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

–     Cette situation est appelée collision.

? 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).

–    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.

? 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)= ? (31ⁱ × s.charAt(i))

i=0

?

? Table de hachage

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

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

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

? 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().