Les Tables Associatives

Une table associative (ou map, dictionnaire, tableau associatif) est une structure de données qui stocke des couples (clé → valeur). Chaque clé est unique et permet de retrouver sa valeur de manière efficace.

Exemples concrets

Les trois « vues » d'une table

Conceptuellement, toute table associative expose trois collections :

Les tables associatives forment une branche distincte du Java Collections Framework : elles n'implémentent pas Collection<E> mais leur propre interface racine Map<K,V>.

Les classes HashMap et TreeMap implémentent toutes deux l'interface Map<K,V>. Voici les méthodes fondamentales à connaître.

Déclaration simplifiée

public interface Map<K, V> {

    // ── Taille ─────────────────────────────────────────────
    boolean       isEmpty();
    int           size();

    // ── Ajout / Modification ────────────────────────────────
    V             put(K key, V value);   // retourne null ou ancienne valeur
    void          putAll(Map<? extends K, ? extends V> map);

    // ── Accès ───────────────────────────────────────────────
    V             get(Object key);         // null si clé absente
    V             getOrDefault(Object key, V defaultValue);

    // ── Suppression ─────────────────────────────────────────
    V             remove(Object key);      // null si clé absente
    void          clear();

    // ── Tests ───────────────────────────────────────────────
    boolean       containsKey(Object key);
    boolean       containsValue(Object value);

    // ── Vues ────────────────────────────────────────────────
    Set<K>                      keySet();
    Collection<V>               values();
    Set<Map.Entry<K,V>>         entrySet();
}

Détail des méthodes clés

L'interface java.util.SortedMap<K,V> (depuis Java 1.2) étend Map<K,V> et définit les fonctionnalités d'une map dont les clés sont triées. L'ordre des clés est déterminé soit par l'implémentation de Comparable<K>, soit par un Comparator<K> fourni à la création.

Méthodes propres à SortedMap

public interface SortedMap<K, V> extends Map<K, V> {

    K                   firstKey();              // plus petite clé
    K                   lastKey();               // plus grande clé

    SortedMap<K,V>      headMap(K toKey);         // clés < toKey
    SortedMap<K,V>      tailMap(K fromKey);       // clés >= fromKey
    SortedMap<K,V>      subMap(K fromKey, K toKey); // [fromKey, toKey[

    Comparator<? super K> comparator();          // null si ordre naturel
}

NavigableMap<K,V> (Java 6+) étend SortedMap<K,V> et ajoute des méthodes de navigation fine permettant de se déplacer dans la table autour d'une clé donnée.

public interface NavigableMap<K, V> extends SortedMap<K, V> {

    // Clé/entrée strictement inférieure
    K                  lowerKey(K key);
    Map.Entry<K,V>    lowerEntry(K key);

    // Clé/entrée strictement supérieure
    K                  higherKey(K key);
    Map.Entry<K,V>    higherEntry(K key);

    // Clé/entrée inférieure ou égale
    K                  floorKey(K key);
    Map.Entry<K,V>    floorEntry(K key);

    // Clé/entrée supérieure ou égale
    K                  ceilingKey(K key);
    Map.Entry<K,V>    ceilingEntry(K key);

    // Accès/suppression des extrêmes
    Map.Entry<K,V>    firstEntry();
    Map.Entry<K,V>    lastEntry();
    Map.Entry<K,V>    pollFirstEntry();  // retire et retourne le premier
    Map.Entry<K,V>    pollLastEntry();   // retire et retourne le dernier

    // Vue inversée
    NavigableMap<K,V> descendingMap();
}

Constructeurs de TreeMap

// Constructeur 1 : ordre naturel (Comparable<K> doit être implémenté)
TreeMap<String, Integer> map1 = new TreeMap<>();

// Constructeur 2 : avec Comparator personnalisé
TreeMap<String, Integer> map2 = new TreeMap<>(
    Comparator.comparingInt(String::length)
              .thenComparing(Comparator.naturalOrder())
);

// Constructeur 3 : depuis une Map existante
HashMap<String, Integer> source = new HashMap<>();
// ... remplissage ...
TreeMap<String, Integer> map3 = new TreeMap<>(source);

Constructeurs de HashMap

// Constructeur 1 : par défaut (capacité 16, facteur de charge 0.75)
HashMap<String, Integer> map = new HashMap<>();

// Constructeur 2 : capacité initiale personnalisée
HashMap<String, Integer> map2 = new HashMap<>(100);

Une table associative ne dispose pas d'itérateur direct. On la parcourt via l'une de ses trois vues. Attention : toute modification effectuée via une vue (notamment remove()) est répercutée sur la table maître. En revanche, les ajouts ne sont pas autorisés par les vues.

Vue 1 – Ensemble des couples : entrySet()

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob",   87);
scores.put("Carol", 91);

// ── Java 5+ : for-each sur entrySet ─────────────────────
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + " → " + entry.getValue());
}

// ── Java 8+ : forEach avec lambda ───────────────────────
scores.forEach((nom, note) ->
    System.out.println(nom + " → " + note)
);

Vue 2 – Ensemble des clés : keySet()

Set<String> cles = scores.keySet();
for (String nom : cles) {
    System.out.println(nom);
}
// Sur un TreeMap, les clés sont affichées dans l'ordre naturel

Vue 3 – Collection des valeurs : values()

Collection<Integer> valeurs = scores.values();
// Collection (pas Set) car les valeurs peuvent contenir des doublons

int somme = valeurs.stream()
                   .mapToInt(Integer::intValue)
                   .sum();
System.out.println("Somme des notes : " + somme);

Nous allons créer un annuaire qui associe chaque Personne à une liste de numéros de téléphone (ListNo). L'annuaire doit afficher les personnes par ordre alphabétique sur le nom et le prénom, ce qui nous oriente vers un TreeMap.

Classe Personne (avec Comparable)

public class Personne implements Comparable<Personne> {

    private final String nom;
    private final String prenom;

    public Personne(String nom, String prenom) {
        this.nom    = nom;
        this.prenom = prenom;
    }

    // Getters omis pour la lisibilité

    /** Ordre alphabétique : nom puis prénom */
    @Override
    public int compareTo(Personne autre) {
        int cmp = this.nom.compareTo(autre.nom);
        return (cmp != 0) ? cmp : this.prenom.compareTo(autre.prenom);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Personne)) return false;
        Personne autre = (Personne) obj;
        return nom.equals(autre.nom) && prenom.equals(autre.prenom);
    }

    @Override
    public int hashCode() {
        return Objects.hash(nom, prenom);
    }

    @Override
    public String toString() {
        return nom + " " + prenom;
    }
}

Classe ListNo

public class ListNo {
    private final List<String> numeros = new ArrayList<>();

    public void ajouter(String numero) { numeros.add(numero); }

    @Override
    public String toString() { return numeros.toString(); }
}

Classe TableTelPersonne

import java.util.*;

public class TableTelPersonne {

    private final TreeMap<Personne, ListNo> annuaire;

    /** Constructeur : crée un annuaire vide */
    public TableTelPersonne() {
        annuaire = new TreeMap<>();
    }

    /** Ajoute un numéro pour une personne (crée l'entrée si besoin) */
    public void ajouterNumero(Personne p, String numero) {
        ListNo liste = annuaire.getOrDefault(p, null);
        if (liste == null) {
            liste = new ListNo();
            annuaire.put(p, liste);
        }
        liste.ajouter(numero);
    }

    /** Affiche toutes les personnes par ordre alphabétique */
    public void afficherPersonnes() {
        Set<Personne> cles = annuaire.keySet();
        System.out.println(cles);
    }

    /** Parcourt et affiche chaque couple (personne → numéros) */
    public void afficherAnnuaire() {
        for (Map.Entry<Personne, ListNo> e : annuaire.entrySet()) {
            System.out.println(e.getKey() + " : " + e.getValue());
        }
    }

    /** Recherche les numéros d'une personne */
    public ListNo rechercherNumeros(Personne p) {
        return annuaire.get(p);
    }
}

// ── Utilisation ────────────────────────────────────────────
TableTelPersonne a = new TableTelPersonne();

Personne alice = new Personne("Dupont", "Alice");
Personne bob   = new Personne("Martin", "Bob");

a.ajouterNumero(alice, "06 12 34 56 78");
a.ajouterNumero(alice, "01 23 45 67 89");
a.ajouterNumero(bob,   "07 98 76 54 32");

a.afficherAnnuaire();
// Dupont Alice : [06 12 34 56 78, 01 23 45 67 89]
// Martin Bob   : [07 98 76 54 32]

1 – Déclarer via l'interface

// ✅ Bon : dépendance à l'interface, pas à l'implémentation
Map<String, Integer> map = new HashMap<>();

// ❌ À éviter : couplage fort sur l'implémentation
HashMap<String, Integer> map = new HashMap<>();

2 – Implémenter equals() ET hashCode() pour les clés d'un HashMap

Si vous utilisez vos propres objets comme clés d'un HashMap, vous devez implémenter equals() et hashCode() de manière cohérente. Si a.equals(b) est vrai, alors a.hashCode() == b.hashCode() doit l'être également.

3 – Utiliser compute et merge (Java 8+)

Map<String, Integer> compteur = new HashMap<>();

// Incrémenter un compteur : classique
compteur.put("mot", compteur.getOrDefault("mot", 0) + 1);

// Idem avec merge (Java 8) : plus élégant
compteur.merge("mot", 1, Integer::sum);

4 – Récapitulatif des méthodes Java 8+