Les collections en Java
Une collection permet de stocker des éléments de même type dans une structure semblable à un tableau.
Par exemple, un collectionneur peut avoir une collection de timbres, et une collection de billets de banques. Il peut avoir un album pour ranger ses timbres, et un autre pour ranger ses billets mais il ne mélangera généralement pas ses billets avec ses timbres.
Java met à notre disposition des structures qui permettent de gérer de cette manière des objets de même type.
Dans les versions antérieures à Java 1.5, les objets sont maintenus dans la collection sous la forme d'objets, peu importe leur type d'origine. Au moment de faire appel à un élément de la collection, celle-ci nous retourne un élément de type Object, sur lequel nous devons faire un casting(spécifier explicitement le type selon lequel nous envisageons l'objet) si nous désirons l'utiliser avec les propriétés du type dont il est issu.
NB : Bien entendu, il est alors possible de maintenir une collection d'objets dissemblables, mais nous éviterons ce genre de programmation car nous perdons dans ce cas les avantages de la collection.
C'est pour cette raison que depuis la version 1.5 les collections peuvent être typées. Nous sommes donc contraints de déclarer le type des éléments qui la compose, mais nous évitons de devoir recourir à un casting car la collection nous retourne non plus un objet de type Object, mais bien un objet du type des objets de la collection.
Dans les premières versions de Java, nous pouvions disposer de peu de collections :
- Array
- Vector
- Stack
- HashTable
- Bitset
Avec Java 1.2, nous avons pu bénéficier du framework Collections, qui offre une hiérarchie de collections qui répond à la majorité des besoins.
Remarque : attention à ne pas confondre Collections (qui est le framework) avec Collection (qui est une interface).
Interfaces du Framework Collections
Le framework Collections propose une série d'interfaces, ainsi qu'une série d'implémentations de ces interfaces
| Collection | List | |
| Set | SortedSet | |
| Queue | ||
| Map | SortedMap | |
Les interfaces contiennent des méthodes appliquées à un seul objet, ou bien sur une collection.
Collection
Collection (java.util.Collection) traite des ensembles d'éléments uniques. Chaque emplacement de la collection ne contient qu'un seul objet, mais qui peut-être lui même un objet composé de plusieurs objets.
Chaque collection doit implémenter un constructeur qui prend une collection en paramètre. C'est ce qui nous assure que nous pouvons passer d'un type de collection vers un autre.
List
List est une collection qui permet les éléments dupliqués.
Dans une liste, nous accédons aux éléments par leur index (comme dans le cas d'un tableau). Les éléments ne sont donc pas triés.
SubList(int from,int to) : retourne la partie de la liste comprise entre l'index from et l'index to. Attention, SubList retourne une partie de la liste d'origine sous la forme d'une liste, mais il ne s'agit que d'une vue des éléments, et non d'une liste réelle. Si nous modifions un élément de la sous liste, nous modifions en réalité l'élément dans la liste d'origine.
Durant tout le temps pendant lequel nous maintenons la sous liste, nous ne pouvons pas modifier les éléments directement dans la liste d'origine (même les éléments de la liste d'origine qui ne sont pas repris dans la sous liste) sous peine de générer une exception de type ConcurrentModificationException.
Implémentations de List : ArrayList, LinkedList.
Par un retrofit, Vector implémente aussi List.
Set
Set est une collection qui n'ajoute aucune méthode. C'est seulement un contrat qui stipule qu'il ne permet pas les valeurs dupliquées. Les méthodes equals() et hashCode() ont ici une grande importance.
Implémentations de Set : HashSet, TreeSet, LinkedHashSet.
SortedSet
SortedSet est un Set dont les éléments sont ordonnés.
Implémentations de SortedSet : TreeSet.
Map
Map nous fournit un ensemble de correspondances clé-valeur. Une Map contient une classe interne Entry qui reprend chaque objet clé avec sa valeur associée.
Implémentations de Map : HashMap, TreeMap, LinkedHashMap.
SortedMap
SortedMap est un objet Map dont les clés sont ordonnées.
Implémentations de SortedMap : TreeMap.
Implémentations des interfaces de Collections
| Interfaces | Implémentations | Remarques | |||
|---|---|---|---|---|---|
| Collection | List | ArrayList | Non trié | ||
| LinkedList | |||||
| Set | SortedSet | HashSet | Non trié (ordre du hashCode) | Meilleurs performances. | |
| LinkedHashSet | Ordre d'insertion | Maintient les élément sous une structure de liste doublement chaînée. | |||
| TreeSet | Ordre d'insertion | Structure en arbre binaire balancé (red-black tree). | |||
| Queue | cliquez ici pour voir les API | ||||
| Map | SortedMap | HashMap | Non trié (ordre du hashCode de la clé) | Meilleurs performances pour une Map | |
| LinkedHashMap | Ordre d'insertion | Liste doublement chaînée. | |||
| TreeMap | Ordre d'insertion | Structure en arbre binaire balancé (red-black tree). | |||
Itérateur en Java
Nous avons vu dans le cadre du polymorphisme qu'il était souvent préférable de travailler avec le type le plus général possible pour des objets, ce principe s'applique donc aussi pour les collections. Seulement, les méthodes d'accès aux éléments différent selon le type de collection utilisée.
Les itérateurs(Iterator) nous permettent donc de parcourir les éléments d'une collection, sans nous soucier du type réel de la collection, ni de l'implémentation exacte de la manière dont les éléments sont accédés.
Le principe est le suivant :
- Nous sommes positionnés au début de la collection.
- Nous demandons si il existe un élément suivant. Même si un seul élément existe dans la collection, comme nous nous trouvons avant cet élément, il nous sera répondu qu'il existe à ce moment un élément suivant.
- Tant qu'un élément suivant existe, nous nous dépla�ons après cet élément, puis nous renvoyons l'élément que nous venons de dépasser.
La méthode iterator de la classe Collection nous retourne un objet qui implémente l'interface Iterator.
Fail-fast iterators
Tant qu'un itérateur est maintenu sur une collection, nous ne pouvons pas modifier la structure de cette collection (ajouter, supprimer des éléments) en dehors de l'itérateur. Nous devons manipuler les éléments de la collection au travers des méthodes de l'itérateur sous peine de générer une ConcurrentModificationException. Pour supprimer un élément, nous utiliserons donc la méthode remove() de l'itérateur.
Le fait d'implémenter une exception de ce type est le Fail-fast iterator, ce qui permet de détecter et gérer les erreurs.
�
Comparaisons
Trier les éléments d'une collection nécessite généralement deux types d'opérations : la comparaison et la permutation.
Si nous créons nos propres objets, comment Java peut-il déterminer la manière de les comparer?
Prenons l'exemple d'un objet Personne, qui comporte les attributs suivants : nom, prénom, numéroNational, adresse. Comment définir quels sont les critères de comparaisons?
Deux cas sont envisagés :
- la comparaison naturelle : c'est le type de comparaison par défaut qui sera utilisé pour des objets comparables. Les méthodes equals (vérifier que l'objet est identique à un autre) et compareTo (déterminer si l'objet se place avant ou après un autre) doivent donc être réimplémentées.
Dans le cas de notre Personne, nous pouvons par exemple déterminer que par défaut les personnes sont triées par leur nom. Si deux personnes portent le même nom, elles sont alors triées par leur prénom, et si elles portent le même nom et le même prénom elles sont triées selon leur numéro national.
Nous tenterons toujours d'utiliser un élément unique en dernier recours. - la comparaison occasionnelle : il est possible de fournir un comparateur spécifique(Comparator) pour trier nos objets.
Dans notre exemple, notre classe peut implémenter une classe ComparateurParAdresse, qui permet de différencier les objets Personne selon leur adresse. Nous devons ici aussi penser aux cas d'égalités.
Dans notre classe ComparateurParAdresse, nous n'aurons plus un compare(Object o1,Object o2).
NB :
- La méthode equals(Object o) retourne un booléen qui est placé à true si l'objet passé en argument est identique à l'objet courant selon les critères que nous avons déterminé dans son implémentation.
- La méthode compareTo(Object o) retourne une des valeurs suivantes :
- Zéro si les deux objets sont considérés comme identiques.
- Entier positif si l'objet courant se place dans le tri avant l'objet fourni en paramètre.
- Entier négatif si l'objet courant se place dans le tri après l'objet fourni en paramètre.
Résumé
| Interfaces | Classes d'implémentations | |||
|---|---|---|---|---|
| Table de hachage | Tableau de taille variable | Arbre balancé | Liste chaînée | |
| List | ArrayList | LinkedList | ||
| Set | HashSet | TreeSet | ||
| Map | HashMap | TreeMap | ||
English translation
You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.
Thank you in advance.
Document created the 14/06/2005, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/en/java-collections.html
The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.
