Java Collection Performance

Le temps de [ ] est révolu ; celui de < > est venu. La liste a remplacé le tableau et type ses éléments — comme son prédécesseur — depuis java 1.5. Mais est-elle efficace ? À quel prix s’entoure-t-on d’un de ses cadets, LinkedList, HashSet, TreeMap ? La JavaDoc détaille leurs complexités, pourtant aucun site ni ouvrage semblent n’en faire l’écho. Quelques indices glanés dans « Java in a Nutshell » quelques autres dans « Java Generics and Collections » pas beaucoup plus sur la toile à ma connaissance. Les Collections, utilisées si généreusement, seraient méconnues ? Petite revue des troupes.

• Collections classiques
• Respect de l’ordre d’insertion
• Respect de l’ordre naturel

Collections classiques

Commençons par la star de ces dames : ArrayList. Comme toute List qui se respecte, cette implémentation est une séquence d’objets autorisant les doublons, la valeur null et l’ajout à un index donné. Elle est bâtie sur un tableau dont la taille est gérée en interne.

légende : e = élément, i = index, n = nombre d’éléments

Cette liste est donc toute désignée lorsqu’il s’agit d’itérer sur des éléments ou d’y accéder par index. Mais, dès lors qu’une suppression ou une recherche est nécessaire, il faudra s’en remettre à une autre collection ; pourquoi pas au matheux de la bande : HashSet. Cet ensemble ne tolère ni doublons, ni valeur null ni accès à un élément donné. Il permet, cependant, de vérifier la présence d’un élément en son sein ou de l’en retirer en temps constant.

légende : c = capacité (c > n)

Cet ensemble serait la collection idéale si il offrait la possibilité d’accéder à un élément par index. Il n’en demeure pas moins un alié de choix lorsque l’appartenance d’un élément prime sur la valeur de ses attributs. Si ces deux informations comptent, c’est à sa soeur ainée qu’il faut s’adresser : HashMap. Ce dictionnaire référence ses objets par clé (à l’image du rangement d’une définition par mot dans un dictionnaire classique). L’ajout d’un objet pour une clé existante remplace l’ancien objet.

légende : k = clé (de type objet)

Attention toutefois, les objets clés sont transformés en entier à l’aide d’un algorithme de hash (la structure sous-jacente peut être vue ainsi Map<int, Objet>). Ce calcul est effectué à partir de la référence java de l’objet ; deux objets aux attributs égaux ne correspondent pas à la même clé. Il est possible de modifier cet état de fait via la surcharge des méthodes hashCode() et equals() (« Effective Java » souligne que les deux méthodes doivent toujours être implémentées de paire). Les wraps de type primitifs les surchargent par défaut (deux Integer de même valeur représentent la même clé).

Comme le souligne la JavaDoc, la complexité des types à base de hash est garantie à condition que la fonction de hash répartisse correctement leurs valeurs. Les collisions sont prises en charge ; lorsque deux objets aux attributs différents obtiennent le même hash, ils sont tous deux conservés. Si la fonction de hash est correcte, n opérations s’effectuent en O(n), les erreurs étant amorties par le nombre d’éléments, une opération est bien en O(1).

En Java les hash sont couramment calculés ainsi, pour n attributs a : ((17 * 31 + a1) * 31 + a2) * ... * 31 + an 31 offre les qualités d’être un nombre premier, impair et de permettre une multiplication optimisée 31 * i == (i << 5) - i Et, toujours selon « Effective Java », ce nombre offre une bonne distribution (HashCodeBuilder de commons-lang s'appuie lui, par défaut, sur 37). La valeur initiale 17 diminue le nombre de collisions qu'aurait occasionné un premier attribut de valeur 0. Sa valeur est arbitraire.

Respect de l'ordre d'insertion

Certaines implémentations des collections sont dédiées au maintient des éléments dans leur ordre d'insertion.

À l'instar du HashSet, les opérations du LinkedHashSet sont en temps constant. Ses performances sont légèrement moins bonnes (à cause du coût de maintient du tri), à une exception : itérer sur ses éléments sera moins coûteux (relatif à son nombre d'éléments et non à sa capacité).

Ces mêmes remarques s'appliquent à LinkedHashMap, respectant elle aussi l'ordre d'insertion.

En ce qui concerne les listes, ArrayList maintient déjà les éléments dans leur ordre d'insertion, mais des compères peuvent lui prêter main forte dans certains cas particuliers.

légende : ajout en queue, retrait en tête

Comme ses paires, la liste doublement chainée LinkedList n'est pas allouée d'un bloc ; ses éléments se référencent les uns les autres. Récupérer un élément à un index donné peut être coûteux si l'on ignore son prédécesseur ou son successeur (LinkedHashSet et LinkedHashMap ont recours à ce procédé pour garantir l'itération ; chaque élément connait le suivant).

Une ArrayDeque peut être utilisée comme une file d'attente ; premier arrivé, premier servi (FIFO). Elle peut également l'être comme une pile d'assiettes ; dernière arrivée, première utilisée (LIFO). Cette implémentation est à préférer à celle de Stack, basée sur Vector. Comme elle n'accède qu'aux premier et dernier éléments, cette implémentation offre une suppression en temps constant.

Respect de l'ordre naturel

Certaines implémentations des collections sont dédiées au maintient des éléments dans leur ordre naturel (les chiffres et les chaines de caractères par ordre croissant, les objets selon leur implémentation de l'interface Comparable) évitant d'avoir recours à un tri.

Un TreeSet peut remplacer avantageusement un ensemble classique lorsque des éléments y sont ajoutés à différentes reprises et que leur ordre importe.

Une TreeMap permet de s'assurer de l'ordre d'itération sur ses clés.

Une TreeList, proposée dans commons-collections car absente du langage natif, améliore suppression et vérification d'appartenance d'un élément au détriment d'une insertion plus coûteuse. Sa documentation souligne que LinkedList est rarement un bon choix (via des statistiques que l'on aimerait voir plus souvent ; TreeList vs ArrayList vs LinkedList).

Limite des collections du JDK

Malgré sa richesse, certains cas de figure ne sont pas adressés par les collections du JDK. C'est là qu'Apache avec ses commons-collections et Google avec guava-collections (anciennement google-collections) prennent le relais. Contrairement aux secondes, et malgré leur popularité, les premières ne supportent pas les génériques (un portage de la version 3.1 par une entreprise externe les y ajoute ; mais ne semble plus maintenu). Voici leurs dépendances maven : guava-collections, commons-collection (et de son port en collections-generic).

Retenir une collection pour sa complexité en temps n'a pas que des vertus d'optimisation, elle est porteuse de sens pour l'algorithme qu'elle accompagne ; elle porte plus que l'opération elle-même la logique des traitements attendus.

Ce billet est dédié à Denis Lapoire