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

CollectionList
SetSortedSet
Queue
MapSortedMap

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

Table des matières Haut

InterfacesImplémentationsRemarques
CollectionListArrayListNon trié  
LinkedList  
SetSortedSetHashSetNon trié (ordre du hashCode)Meilleurs performances.
LinkedHashSetOrdre d'insertion Maintient les élément sous une structure de liste doublement chaînée.
TreeSetOrdre d'insertionStructure en arbre binaire balancé (red-black tree).
Queuecliquez ici pour voir les API
MapSortedMapHashMapNon trié (ordre du hashCode de la clé) Meilleurs performances pour une Map
LinkedHashMapOrdre d'insertionListe doublement chaînée.
TreeMapOrdre d'insertionStructure en arbre binaire balancé (red-black tree).

Itérateur en Java

Table des matières Haut

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é

Table des matières Haut

InterfacesClasses d'implémentations
Table de hachage Tableau de taille variable Arbre balancé Liste chaînée
ListArrayListLinkedList
SetHashSetTreeSet
MapHashMapTreeMap

Document créé le 14/06/2005, dernière modification le 26/10/2018
Source du document imprimé : https://www.gaudry.be/java-collections.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.