Réalisations des collections et des tables

Les interfaces spécialisées spécifiant les collections et les tables disposent d'une ou de plusieurs réalisations, toutes membres du paquet java.util :

• les classes ArrayList (recommandée) et LinkedList réalisent l'interface List ;
• les classes HashSet (recommandée) et LinkedHashSet réalisent l'interface Set ;
• la classe TreeSet réalise l'interface SortedSet ;
• les classes HashMap (recommandée) et LinkedHashMap réalisent l'interface Map ;
• la classe TreeMap réalise l'interface SortedMap.

Après avoir choisi les fonctionnalités souhaitées, ce qui détermine l'interface (par exemple, l'ordre d'insertion doit-il être préservé ? souhaite-t-on utiliser une relation d'ordre sur les éléments ?), il faut choisir la représentation de la structure de données (quelles sont les opérations qui doivent être les plus efficaces ?), ce qui détermine la réalisation.

Il faut savoir que :

• dans une ArrayList, les opérations get et set se font en temps constant, mais les opérations add et remove peuvent se faire en temps linéaire dans le pire des cas (elles se font cependant en temps amorti constant, c'est-à-dire que 59#59 opérations se font en temps 247#247) ; les objets de cette classe peuvent être décrits comme des tableaux à taille variable ;
• dans une LinkedList, les opérations get et set se font en temps linéaire, mais l'opération add se fait en temps constant ;
• dans un HashSet, toutes les opérations se font en temps constant ; les objets de cette classe sont des tables de hachage ;
• l'ordre d'insertion est préservé dans un LinkedHashSet et dans une LinkedHashMap, il ne l'est pas dans un HashSet ou une HashMap ;
• dans un TreeSet et une TreeMap, les opérations add, remove, contains, containsKey, get, put et remove se font en temps logarithmique.

On adoptera la discipline d'abstraction suivante :

• les champs, les paramètres des méthodes, les variables locales sont toujours déclarées avec comme type une interface (Set, List, etc.) ;
• les classes de réalisation ne sont utilisées que par l'intermédiaire de leurs constructeurs (HashSet, ArrayList, etc.).

Ainsi, on déclarera par exemple :

  List l = new ArrayList(); 
  Set s = new HashSet();
  Map m = new HashMap();