Notes S11

Égalité, ordre et hachage — Résumé CS-108

1. Introduction

Les ensembles sont plus exigeants que les listes : une liste se contente de stocker des éléments, mais un ensemble doit pouvoir détecter les doublons → il faut au minimum une notion d’égalité.

Selon la mise en œuvre choisie, des exigences supplémentaires s’ajoutent :

TreeSet → besoin d’une notion d’ordre (pour trier),
HashSet → besoin d’une fonction de hachage.

2. Égalité

Il n’existe pas de notion absolue d’égalité. Exemple : deux billets de banque neufs de même valeur sont distincts (numéros de série différents) mais substituables (même valeur).

2.1. Deux notions d’égalité en Java

Égalité par référence (identité) : deux objets sont égaux ssi il s’agit du même objet en mémoire.
Égalité par structure (structurelle) : deux objets sont égaux ssi leur contenu est identique.

L’égalité par référence est plus discriminante : égaux par référence ⇒ égaux par structure, mais pas l’inverse.

Mécanisme Java	Type d’égalité
`==`	par référence
`equals` héritée de `Object`	par référence
`equals` redéfinie	par structure (à toi de l’implémenter)

2.2. Règle de l’égalité et de l’immuabilité

Conseil de redéfinir equals pour les classes immuables — et seulement pour elles.

Pourquoi ? L’identité d’une instance immuable n’a aucune importance puisque son contenu ne peut jamais changer ; seule la structure compte.

Exception : si une classe immuable garantit qu’il ne peut pas exister deux instances de même contenu, alors égalité par référence ⇔ égalité par structure, et on n’a pas besoin de redéfinir equals.

⚠️ Beaucoup de classes du JDK violent cette règle (les collections notamment, qui sont mutables mais comparées par structure).

3. Ordre

L’ordre n’est pas indispensable pour stocker des éléments dans un ensemble, mais il permet une mise en œuvre plus efficace (ex. : TreeSet).

Pour les listes : recherche dichotomique — chercher un nom dans une liste triée est bien plus rapide que dans une liste non triée (intuition derrière l’efficacité de l’ordre).

3.1. Deux moyens de spécifier l’ordre en Java

Comparable : la classe elle-même fournit la méthode de comparaison.
Comparator : un objet externe à la classe sait comparer ses instances.

3.2. L’interface `Comparable` (paquetage `java.lang`)

java

public interface Comparable<T> { int compareTo(T that); }

La méthode compareTo compare le récepteur (this) à l’argument :

< 0 si this < that
= 0 si this == that
> 0 si this > that

Pourquoi `Comparable` est-il générique ?

C’est exactement ton point d’incompréhension — voici l’idée :

Le paramètre <T> donne le type de l’argument de compareTo. Sans la généricité, compareTo prendrait un Object, ce qui imposerait un cast à chaque comparaison et autoriserait des comparaisons absurdes (Integer.compareTo(unString)).

Avec la généricité, Integer implements Comparable<Integer> impose que compareTo reçoive forcément un Integer. Le compilateur garantit la cohérence du type.

java

public final class Integer implements Comparable<Integer> { @Override public int compareTo(Integer that) { /* ... */ } }

Règle pratique : toute classe qui implémente Comparable lui passe son propre type en paramètre. C’est une astuce idiomatique en Java qu’on rencontre souvent.

Règle de compatibilité `compareTo` / `equals`

Pour toutes paires d’instances o1 et o2 :

o1.equals(o2) ⇔ o1.compareTo(o2) == 0

Sinon, le comportement des collections triées devient incohérent.

Exemple : `TreeSet` avec ordre naturel

import java.util.Set;
import java.util.TreeSet;
 
public final class TreeSetExemple {
    interface MyComparable<This> {
        int compareTo(This that);
    }
 
    record StringCell(String string) implements MyComparable<StringCell> {
        @Override
        public int compareTo(StringCell that) {
            return this.string.compareTo(that.string);
        }
    }
 
    static void main() {
        Set<StringCell> s = new TreeSet<>();
        s.add(new StringCell("b"));
        s.add(new StringCell("a"));
        s.add(new StringCell("a")); // doublon ignoré
        s.add(new StringCell("c"));
        // Parcours dans l'ordre : a, b, c
    }
}

3.3. L’interface `Comparator` (paquetage `java.util`)

public interface Comparator<T> {
    int compare(T o1, T o2);
}

Un Comparator est un objet séparé qui sait comparer deux objets de type T.

3.4. `Comparable` vs `Comparator` — la différence

Aspect	`Comparable`	`Comparator`
Implémenté par	la classe comparable elle-même	un objet étranger
Méthode	`compareTo(T that)`	`compare(T o1, T o2)`
Nombre d’arguments	1 (l’autre est `this` implicite)	2
Usage typique	définir l’ordre naturel	définir un ordre alternatif (ex. inverse)
Écriture	méthode dans la classe	souvent une lambda

En résumé : Comparator prend 2 paramètres (souvent défini par lambda), Comparable n’en prend qu’un car this est implicite.

Exemple : tri d’une liste avec et sans comparateur

java

`List l = Arrays.asList(1, 3, 5, 7, 2, 4, 6, 8);

l.sort(null); // ordre naturel : [1, 2, 3, 4, 5, 6, 7, 8]

l.sort((i, j) → Integer.compare(j, i)); // comparateur inversant : [8, 7, …, 1]`

3.5. `TreeSet`

Stocke ses éléments triés → parcours toujours en ordre croissant.
Par défaut : utilise l’ordre naturel (compareTo).
On peut passer un Comparator au constructeur pour utiliser un autre ordre.

Set<Integer> s = new TreeSet<>((i, j) -> Integer.compare(j, i));
s.addAll(Set.of(1, 3, 5, 7, 2, 4, 6, 8));
// Parcours : 8, 7, 6, 5, 4, 3, 2, 1

4. Hachage

4.1. Définition

Le hachage consiste à transformer une donnée en un entier (généralement borné) au moyen d’une fonction de hachage h. L’entier produit est la valeur de hachage.

Intuition : la valeur de hachage permet de déterminer dans quel « sous-ensemble » (ou bucket) l’élément sera placé en mémoire — d’où l’accès rapide.

Exemple

`h(c) = (Σ pos(cᵢ)) mod 100

h(chien) = (3+8+9+5+14) mod 100 = 39 h(niche) = (14+9+3+8+5) mod 100 = 39 ← collision ! h(zoologie) = (…) mod 100 = 4`

4.2. Propriétés

Toute fonction de hachage doit satisfaire :

∀ x, y : x = y ⇒ h(x) = h(y)

L’implication inverse n’est vraie que pour les fonctions parfaites (injectives) :

∀ x, y : x ≠ y ⇒ h(x) ≠ h(y)

En pratique, le principe des tiroirs rend les fonctions parfaites quasi impossibles dès que l’espace des données est plus grand que celui des hachages → des collisions sont inévitables. L’objectif est de bien distribuer les valeurs.

4.3. Hachage en Java

Object fournit la méthode hashCode() qui retourne un int.

Par défaut : valeur dérivée de l’identité de l’objet (deux objets distincts → généralement des hash distincts, non garanti).
Souvent à redéfinir.

Règle fondamentale : compatibilité `hashCode` / `equals`

x.equals(y) ⇒ x.hashCode() == y.hashCode()

Si tu redéfinis hashCode, redéfinis aussi equals — et inversement.

Sans cette compatibilité, hashCode ne définit pas une vraie fonction de hachage, et HashSet ne fonctionne plus correctement.

Mise en œuvre recommandée

Utiliser la méthode statique Objects.hash(...) du paquetage java.util :

public final class Person {
    private final String firstName, lastName;
    private final Date birthDate;
 
    @Override
    public int hashCode() {
        return Objects.hash(firstName, lastName, birthDate);
    }
}

Exceptions :

Classe à un seul attribut → réutiliser le hashCode() de cet attribut.
Classe à un seul attribut entier (int) → utiliser sa valeur directement.

4.4. Pourquoi hachage + mutabilité = catastrophe

La valeur de hachage dépend du contenu des attributs hachés. Si on modifie un de ces attributs, la valeur de hachage change — mais l’objet est déjà stocké dans le bucket correspondant à son ancienne valeur. Le HashSet ne le retrouve plus.

D’où l’importance que hashCode et equals restent stables → on ne s’en sert proprement que sur des objets immuables.

Exemple cassant : `HashSet` avec une classe mutable

import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
public class HashSetExemple {
    static final class StringCell {
        private String string;
 
        public StringCell(String string) { this.string = string; }
        public String string() { return string; }
        public void setString(String string) { this.string = string; }
 
        @Override
        public boolean equals(Object obj) {
            return (obj instanceof StringCell that) && this.string.equals(that.string);
        }
 
        @Override
        public int hashCode() { return string.hashCode(); }
 
        @Override
        public String toString() { return string; }
 
        static void main() {
            StringCell a = new StringCell("a");
            StringCell b = new StringCell("b");
            StringCell c = new StringCell("c");
 
            Set<StringCell> s = new HashSet<>(List.of(a, b, c));
            System.out.println(s);
 
            a.setString("d");           // ⚠️ on modifie un objet déjà dans l'ensemble
            System.out.println(s.contains(a)); // false ! Pourtant a est dedans...
 
            for (var cell : s) {
                if (cell.equals(a)) {
                    System.out.printf("Trouvé ! %s == %s\n", cell, a);
                }
            }
        }
    }
}

Deux observations importantes :

s.contains(a) retourne false alors que a est bien dans s : HashSet cherche dans le bucket correspondant au nouveau hash, mais a est encore stocké dans l’ancien.
L’ordre d’affichage n’est pas trié (contrairement à TreeSet) : HashSet n’a aucune notion d’ordre, le parcours suit l’organisation interne des buckets.

4.5. `HashSet`

Stocke les éléments selon leur valeur de hachage.
Accès très rapide.
Aucun ordre garanti lors du parcours.

5. Résumé

Les exigences placées par les listes et les ensembles (et leurs mises en œuvre) en Java sont résumées par la table ci-dessous. Pour chaque type de collection, elle montre les méthodes qui doivent être fournies (correctement !) par les éléments pour qu’on puisse les stocker dans la collection en question. Étant donné que TreeSet offre deux possibilités pour déterminer l’ordre des éléments, cette collection apparaît deux fois dans la table.

Collection	Méthodes requises
`List<E>`	aucune
`Set<E>`	`equals`
`HashSet<E>`	`equals` et `hashCode`
`TreeSet<E>`	`equals` et `compareTo`
`TreeSet<E>`	`equals` et `compare`

6. Les règles à retenir

Égalité & immuabilité : redéfinir equals pour les classes immuables uniquement.
Compatibilité compareTo / equals : o1.equals(o2) ⇔ o1.compareTo(o2) == 0.
Compatibilité hashCode / equals : x.equals(y) ⇒ x.hashCode() == y.hashCode(). Redéfinir l’un = redéfinir l’autre.
Mise en œuvre de hashCode : utiliser Objects.hash(...) avec tous les attributs pertinents.

Quartz 4

Explorer

Notes S11

Notes S11

Égalité, ordre et hachage — Résumé CS-108

1. Introduction

2. Égalité

2.1. Deux notions d’égalité en Java

2.2. Règle de l’égalité et de l’immuabilité

3. Ordre

3.1. Deux moyens de spécifier l’ordre en Java

3.2. L’interface `Comparable` (paquetage `java.lang`)

Pourquoi `Comparable` est-il générique ?

Règle de compatibilité `compareTo` / `equals`

Exemple : `TreeSet` avec ordre naturel

3.3. L’interface `Comparator` (paquetage `java.util`)

3.4. `Comparable` vs `Comparator` — la différence

Exemple : tri d’une liste avec et sans comparateur

3.5. `TreeSet`

4. Hachage

4.1. Définition

Exemple

4.2. Propriétés

4.3. Hachage en Java

Règle fondamentale : compatibilité `hashCode` / `equals`

Mise en œuvre recommandée

4.4. Pourquoi hachage + mutabilité = catastrophe

Exemple cassant : `HashSet` avec une classe mutable

4.5. `HashSet`

5. Résumé

6. Les règles à retenir

Graph View

Table of Contents

Quartz 4

Explorer

Notes S11

Notes S11

Égalité, ordre et hachage — Résumé CS-108

1. Introduction

2. Égalité

2.1. Deux notions d’égalité en Java

2.2. Règle de l’égalité et de l’immuabilité

3. Ordre

3.1. Deux moyens de spécifier l’ordre en Java

3.2. L’interface Comparable (paquetage java.lang)

Pourquoi Comparable est-il générique ?

Règle de compatibilité compareTo / equals

Exemple : TreeSet avec ordre naturel

3.3. L’interface Comparator (paquetage java.util)

3.4. Comparable vs Comparator — la différence

Exemple : tri d’une liste avec et sans comparateur

3.5. TreeSet

4. Hachage

4.1. Définition

Exemple

4.2. Propriétés

4.3. Hachage en Java

Règle fondamentale : compatibilité hashCode / equals

Mise en œuvre recommandée

4.4. Pourquoi hachage + mutabilité = catastrophe

Exemple cassant : HashSet avec une classe mutable

4.5. HashSet

5. Résumé

6. Les règles à retenir

Graph View

Table of Contents

3.2. L’interface `Comparable` (paquetage `java.lang`)

Pourquoi `Comparable` est-il générique ?

Règle de compatibilité `compareTo` / `equals`

Exemple : `TreeSet` avec ordre naturel

3.3. L’interface `Comparator` (paquetage `java.util`)

3.4. `Comparable` vs `Comparator` — la différence

3.5. `TreeSet`

Règle fondamentale : compatibilité `hashCode` / `equals`

Exemple cassant : `HashSet` avec une classe mutable

4.5. `HashSet`