Notes S4

Les Ensembles (Set)

Un Set est une collection non ordonnée qui ne contient aucun élément en double.

Opérations sur les ensembles

L’interface java.util.Set fournit plusieurs méthodes pour effectuer des opérations logiques sur les ensembles.

Opération	Méthode	Description
Union (∪)	addAll(Collection c)	Ajoute tous les éléments de c à l’ensemble.
Intersection (∩)	retainAll(Collection c)	Ne conserve que les éléments de l’ensemble qui sont aussi dans c.
Différence ()	removeAll(Collection c)	Supprime de l’ensemble tous les éléments qui sont aussi dans c.
Test d’appartenance (∈)	contains(Object o)	Retourne true si l’élément o est dans l’ensemble.
Test d’inclusion (⊆)	containsAll(Collection c)	Retourne true si tous les éléments de c sont dans l’ensemble.

---

Exemple d’intersection

Objectif : Trouver les mots communs entre une liste de mots français (frWords) et une liste de mots anglais (enWords).

L’opération frWords.retainAll(enWords) calcule l’intersection.

Problème de performance avec List

Si frWords et enWords sont des ArrayList, l’opération retainAll est très lente. Sa complexité est en O(n * m), où n et m sont les tailles des deux listes.

Pour chaque élément de frWords, la méthode retainAll doit parcourir toute la liste enWords pour voir si l’élément s’y trouve (avec enWords.contains()).

Voici une implémentation manuelle équivalente qui illustre ce problème :

// frWords et enWords sont des List<String>
Iterator<String> frIt = frWords.iterator();
 
// "frLoop" est une étiquette (label) de boucle.
// Elle permet de contrôler la boucle externe depuis une boucle interne.
frLoop:
while (frIt.hasNext()) {
    String frWord = frIt.next();
    // On cherche si le mot français existe dans la liste anglaise
    for (String enWord : enWords) {
        if (enWord.equals(frWord)) {
            // Le mot existe, on passe au mot français suivant
            continue frLoop;
        }
    }
    // Si on arrive ici, le mot n'a pas été trouvé dans enWords, on le supprime.
    frIt.remove();
}

Qu’est-ce qu’une étiquette de boucle (Label) ? En Java, une étiquette (comme frLoop:) permet de nommer une boucle. On peut ensuite utiliser break nom_etiquette; ou continue nom_etiquette; à l’intérieur d’une boucle imbriquée pour interrompre ou continuer la boucle externe (celle qui porte l’étiquette). C’est utile pour sortir de plusieurs niveaux de boucles à la fois.

Solution avec HashSet ou TreeSet

Pour optimiser, il suffit de transformer la collection sur laquelle on fait le test d’appartenance (contains) en un HashSet.

// On convertit la liste de mots anglais en HashSet pour un accès quasi-instantané.
Set<String> enWordsSet = new HashSet<>(enWords);
 
// L'opération retainAll sera maintenant beaucoup plus rapide !
// Complexité : O(n) où n est la taille de frWords.
frWords.retainAll(enWordsSet);

Implémentations : HashSet vs TreeSet

Implémentation	Complexité (ajout/test)	Ordre des éléments
HashSet	O(1) (constant, très rapide)	Aucun ordre garanti.
TreeSet	O(log n) (logarithmique)	Éléments triés selon leur ordre naturel (ou un Comparator).

• Pour une performance maximale, utilisez HashSet.
• Pour avoir des éléments triés, utilisez TreeSet.

Itération et Ordre

L’ordre dans lequel on parcourt les éléments dépend de l’implémentation :

• ArrayList : Ordre d’insertion.
• TreeSet : Ordre trié (p. ex., alphabétique). Attention, les majuscules viennent avant les minuscules par défaut.
• HashSet : Ordre quelconque, peut changer au fil des ajouts/suppressions.

Pour afficher les 10 premiers éléments d’un Set :

Iterator<String> it = frWords.iterator();
for (int i = 0; i < 10 && it.hasNext(); i++) {
    System.out.println(it.next());
}

Ensembles immuables vs vues non modifiables

• Set.of(e1, e2, ...) : construit un Set immuable.
• Set.copyOf(Collection<E> c) : copie immuable des éléments d’une collection.
• Collections.unmodifiableSet(Set<E> s) : retourne une vue non modifiable (mais pas forcément immuable).
• Règle : pour obtenir un ensemble immuable à partir d’un ensemble quelconque, utiliser Set.copyOf(...).

---

Les Tables Associatives (Map)

Une Map est un objet qui associe des clefs (keys) à des valeurs (values). Les clefs sont uniques.

L’interface Map

Quelques méthodes importantes de java.util.Map.

Remarque : Map n’hérite pas de Collection (ni de Iterable).

Méthodes principales

• boolean isEmpty() : retourne vrai ssi la map est vide.
• int size(): Retourne le nombre d’associations.
• boolean containsKey(Object k): Retourne true si la map contient la clef k.
• V get(Object k): Retourne la valeur associée à la clef k, ou null.
• V getOrDefault(Object k, V defaultValue): Retourne la valeur pour la clef k, ou defaultValue si la clef n’existe pas.
• V put(K k, V v): Associe la valeur v à la clef k.
• V putIfAbsent(K k, V v) : n’ajoute que si la clef est absente.
• V remove(Object k): Supprime l’association pour la clef k.
• boolean remove(Object k, Object v) : supprime uniquement si la clef est associée à la valeur donnée.

Vues sur la Map

Une Map peut être vue de 3 manières différentes :

• Set<K> keySet(): Retourne une vue de type Set sur toutes les clefs.
• Collection<V> values(): Retourne une vue de type Collection sur toutes les valeurs.
• Set<Map.Entry<K, V>> entrySet(): Retourne une vue de type Set sur toutes les paires clef/valeur.

Si la map est modifiable, ces vues le sont aussi et les modifications se répercutent entre la vue et la map.

C’est la vue entrySet qui est la plus efficace pour itérer sur une Map.

L’interface Map.Entry

Chaque élément d’un entrySet est un Map.Entry, qui représente une paire clef/valeur.

• K getKey(): Retourne la clef de la paire.
• V getValue(): Retourne la valeur de la paire.

Exemple : Compter les occurrences par longueur de mot

Objectif : Pour une liste de mots, compter combien de mots ont une certaine longueur.

Map<Integer, Integer> counts = new HashMap<>(); // <Longueur, Nombre de mots>
 
for (String word : frWords) {
    int length = word.length();
    // La méthode getOrDefault simplifie grandement le code.
    counts.put(length, counts.getOrDefault(length, 0) + 1);
}
 
// Pour afficher les résultats :
// On itère sur le entrySet pour avoir accès à la clef et la valeur en même temps.
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
    System.out.printf("Longueur%2d :%5d mots\n", entry.getKey(), entry.getValue());
}

Implémentations : HashMap vs TreeMap

Comme pour les Set, les Map ont deux implémentations principales :

Implémentation	Complexité (put/get)	Ordre des clefs
HashMap	O(1) (constant, très rapide)	Aucun ordre garanti.
TreeMap	O(log n) (logarithmique)	Clefs triées selon leur ordre naturel (ou un Comparator).

Relation entre Set et Map

On peut voir un Set comme un cas particulier d’une Map où seule la clef nous intéresse (la valeur serait une constante factice).

• Set<E> ≈ Map<E, Object>
• Map<K, V> est conceptuellement un Set<Map.Entry<K, V>>.

---

Les Expressions Lambda et Classes Anonymes

• Intro : une lambda est une écriture courte pour passer une “fonction” en argument (souvent notée [λ] dans le poly). On verra ça en détail la semaine prochaine.

Problème : Trier une liste en ordre décroissant

Pour trier une collection, on peut utiliser Collections.sort(list, comparator). Le Comparator définit la logique de tri.

Solution 1 : Classe imbriquée (nested class)

C’est une solution verbeuse mais claire. On définit une classe qui implémente Comparator.

class InverseIntegerComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer i1, Integer i2) {
        // On inverse les paramètres pour inverser l'ordre de tri.
        return Integer.compare(i2, i1);
    }
}
 
// Utilisation
Collections.sort(maListe, new InverseIntegerComparator());

Note sur la comparaison : Éviter de faire i2 - i1. Cette technique peut causer un bug de dépassement d’entier (integer overflow) si les nombres sont très grands. Integer.compare(i2, i1) est la méthode sûre et correcte.

Solution 2 : Classe anonyme (anonymous class)

Si le comparateur n’est utilisé qu’une seule fois, on peut le déclarer et l’instancier directement, sans lui donner de nom. C’est plus concis.

Collections.sort(maListe, new Comparator<Integer>() {
    @Override
    public int compare(Integer i1, Integer i2) {
        return Integer.compare(i2, i1);
    }
});

Solution 3 : Expression Lambda (Java 8+)

Depuis Java 8, on peut utiliser une expression lambda, qui est encore plus concise.

// (param1, param2) -> { corps de la méthode }
Collections.sort(maListe, (i1, i2) -> Integer.compare(i2, i1));
 
// On peut même utiliser une référence de méthode
//maListe.sort(Comparator.reverseOrder());

Explication : Capture de variables locales

Analysons l’exemple que vous n’avez pas compris.

// Contexte : une méthode sortDescending
int i = 12; // Une variable locale
Collections.sort(list, new Comparator<Integer>() {
    @Override
    public int compare(Integer i1, Integer i2) {
        // Attention : i2 n'est pas utilisé !
        // La comparaison se fait entre i1 et la variable locale 'i' (qui vaut 12).
        return i1 - i;
    }
});

Que se passe-t-il ici ?

1. Capture de variable : La classe anonyme new Comparator<...>() “capture” la variable locale i de la méthode sortDescending. Elle peut donc l’utiliser à l’intérieur de sa méthode compare.
2. Logique de comparaison incorrecte : Le contrat d’un Comparator exige qu’il compare ses deux arguments (i1 et i2). Ici, la méthode compare ignore i2 et compare i1 à une valeur externe (i = 12).
3. Conséquence : Ce n’est pas un comparateur valide pour un tri général. Le résultat du tri est imprévisible et dépend de l’algorithme de tri utilisé. L’intention de ce code n’est pas de trier la liste dans un ordre croissant ou décroissant. Il pourrait être utilisé pour partitionner la liste : tous les nombres inférieurs à 12 se retrouveraient avant tous les nombres supérieurs à 12, mais l’ordre au sein de ces deux groupes ne serait pas garanti.

Ce genre de code est généralement une erreur, sauf si l’intention est très spécifique et non liée à un tri standard.