Collections : Tables associatives

Le concept de table associative est représenté dans l'API Java par l'interface Map du paquetage java.util. Cette interface est générique et prend deux paramètres de type nommés K et V qui représentent respectivement le type des clefs (keys) et celui des valeurs (values) :

public interface Map<K, V> {
  // … méthodes
}

A noter que contrairement aux interfaces List et Set, l'interface Map n'hérite pas de Collection, ni de Iterable.

Les principales méthodes de cette interface sont présentées ci-après, parfois avec un type simplifié pour des raisons pédagogiques.

L'interface Map.Entry — imbriquée statiquement dans l'interface Map — représente une association entre une clef et une valeur, aussi appelée paire clef/valeur.

Tout comme l'interface Map, l'interface Entry est générique et prend deux paramètres de type : le type K de la clef et le type V de la valeur qui lui est associée.

public interface Map<K, V> {
  public static interface Entry<K, V> {
    // … méthodes
  }
}

L'interface Map.Entry offre deux méthodes permettant respectivement d'accéder à la clef et à la valeur de la paire clef/valeur qu'elle représente :

• K getKey(), retourne la clef de la paire,
• V getValue(), retourne la valeur de la paire.

De plus, elle offre une méthode optionnelle permettant de modifier la valeur associée à la clef :

• void setValue(V v), remplace la valeur de la paire par celle donnée.

Comme les interfaces List et Set, l'interface Map possède une famille de méthodes statiques nommées of et permettant de créer des tables associatives immuables. Les versions à 0, 1 et 2 arguments sont :

• <K, V> Map<K, V> of(), qui retourne une table associative immuable vide,
• <K, V> Map<K, V> of(K k, V v), qui retourne une table associative immuable contenant uniquement la paire clef/valeur donnée,
• <K, V> Map<K, V> of(K k1, V v1, K k2, V v2), qui retourne une table associative immuable contenant les deux paires clef/valeur données.

Des méthodes similaires prenant jusqu'à 10 paires clef/valeur existent.

De plus, tout comme pour les listes et les ensembles, la classe Collections (avec un s) offre des méthodes permettant de créer des tables associatives immuables :

• <K, V> Map<K, V> emptyMap(), retourne une table associative immuable vide.
• <K, V> Map<K, V> singletonMap(K k, V v), retourne une table associative immuable contenant uniquement l'association entre la clef et la valeur donnés.

Tout comme pour les listes, la classe Collections offre une méthode permettant d'obtenir une vue non modifiable sur une table associative :

• <K,V> Map<K, V> unmodifiableMap(Map<K, V> m)

Comme d'habitude, il faut prendre garde au fait qu'il s'agit d'une vue et que toute éventuelle modification à la table sous-jacente sera répercutée sur la vue ! Celle-ci est donc non modifiable mais pas forcément immuable.

Map<…> immutableMap =
  Collections.unmodifiableMap(new HashMap<>(map));

L'interface Map n'étend malheureusement pas l'interface Iterable, et il n'est donc pas possible de parcourir directement les paires clef/valeur d'une table associative au moyen d'un itérateur.

Il est par contre possible de parcourir ces paires clef/valeur par l'intermédiaire de la vue fournie par entrySet :

Map<String, Integer> m = …;
for (Map.Entry<String, Integer> e: m.entrySet())
  System.out.println(e.getKey() + "->" + e.getValue());

Attention : comme pour les ensembles, l'ordre de parcours dépend de la mise en œuvre utilisée. Avec TreeSet, le parcours se fait par ordre croissant des clefs, tandis qu'avec HashSet, le parcours se fait dans un ordre quelconque.

La bibliothèque Java offre deux mises en œuvre principales des tables associatives, TreeMap et HashMap. Comme la similarité de leurs noms l'indique, ces mises en œuvres sont basées sur les mêmes techniques que les classes TreeSet et HashSet. Dès lors, elles ont les mêmes caractéristiques principales, à savoir :

• TreeMap exige que ses clefs soient comparables, et utilise cette caractéristique pour offrir les opérations principales en O(log n), tout en garantissant que les paires clef/valeur sont parcourues par ordre croissant des clefs,
• HashMap exige que ses clefs soient hachables, et utilise cette caractéristique pour offrir les opérations principales en O(1), mais ne donne aucune garantie quant à l'ordre de parcours des paires clef/valeur.

Notez que seules les clefs doivent être comparables (pour TreeMap) ou hachables (pour HashMap), aucune exigence n'est placée sur les valeurs d'une table associative.

Le fait que les techniques de mise en œuvre des ensembles et des tables associatives soient similaires peut sembler surprenant au premier abord. Toutefois, à la réflexion, on se rend compte qu'il y a une très grande similarité entre ces deux types de collections :

• un ensemble peut être vu comme une table associative dont seules les clefs importent, les valeurs étant ignorées,
• une table associative peut être vue comme un ensemble de paires clef/valeur — pour peu que la valeur soit ignorée dans les tests d'égalité, les comparaisons et le hachage.

En pratique, la bibliothèque Java tire parti de ces similarités, puisque HashSet est mis en œuvre au moyen de HashMap, tandis que TreeSet est mise en œuvre au moyen de TreeMap.