C# : Dictionary et le hachage

Un Dictionary<TKey, TValue> retrouve une valeur par sa clé en temps quasi constant. Ce n'est pas magique : c'est une table de hachage. Comprendre le mécanisme explique pourquoi certaines clés cassent les performances et comment en fabriquer de bonnes.

# Le principe du hachage

Chercher une clé en parcourant toutes les entrées serait O(n). Le dictionnaire fait autrement : il calcule un nombre à partir de la clé (son hash) et s'en sert pour aller directement au bon emplacement.

clé "Alice"  ─GetHashCode()→  -1042 ─(mod nb buckets)→  bucket 7

clé "Alice"  ─GetHashCode()→  -1042 ─(mod nb buckets)→  bucket 7

Le tableau interne est découpé en buckets (compartiments). Le hash de la clé désigne le bucket ; à l'insertion on y range l'entrée, à la lecture on va lire directement ce bucket. Pas de parcours, d'où le O(1) en moyenne.

Dictionary<string, int> ages = new();
ages["Alice"] = 30;          // hash("Alice") -> bucket -> on range (Alice, 30)
int a = ages["Alice"];       // hash("Alice") -> même bucket -> on lit

Dictionary<string, int> ages = new();

ages["Alice"] = 30;          // hash("Alice") -> bucket -> on range (Alice, 30)

int a = ages["Alice"];       // hash("Alice") -> même bucket -> on lit

# Les collisions

Deux clés différentes peuvent tomber dans le même bucket (leurs hash se ramènent au même compartiment). C'est une collision. Le dictionnaire les gère en chaînant les entrées d'un même bucket et en comparant alors les clés une à une avec Equals.

bucket 7 → (Alice, 30) → (Bob, 25)      // deux clés, même bucket

bucket 7 → (Alice, 30) → (Bob, 25)      // deux clés, même bucket

Tant que les collisions restent rares, la lecture reste quasi constante. Si toutes les clés atterrissaient dans le même bucket (un GetHashCode catastrophique qui renvoie toujours la même valeur), le dictionnaire dégénérerait en liste et retomberait à O(n).

# GetHashCode et Equals vont ensemble

Le dictionnaire utilise deux méthodes de la clé :

• GetHashCode() pour choisir le bucket,
• Equals() pour départager les clés d'un même bucket.

La règle d'or : deux objets égaux doivent avoir le même hash. Si a.Equals(b) est vrai, alors a.GetHashCode() == b.GetHashCode() doit l'être aussi. Sinon, le dictionnaire ira chercher la clé dans le mauvais bucket et ne la retrouvera jamais.

Pour les types intégrés (int, string...) c'est déjà correct. Le problème apparaît avec une clé personnalisée :

// MAUVAIS : classe sans Equals/GetHashCode redéfinis
public class Point { public int X; public int Y; }

Dictionary<Point, string> map = new();
map[new Point { X = 1, Y = 2 }] = "A";
string s = map[new Point { X = 1, Y = 2 }];   // PLANTE : KeyNotFoundException

// MAUVAIS : classe sans Equals/GetHashCode redéfinis

public class Point { public int X; public int Y; }

Dictionary<Point, string> map = new();

map[new Point { X = 1, Y = 2 }] = "A";

string s = map[new Point { X = 1, Y = 2 }];   // PLANTE : KeyNotFoundException

Deux Point de mêmes coordonnées sont considérés différents, car par défaut une classe compare par référence. La deuxième instance a une autre référence, donc un autre hash.

# Fabriquer une bonne clé

Le plus simple aujourd'hui : un record, qui génère Equals et GetHashCode par valeur automatiquement.

// BON : un record compare par valeur, hash cohérent inclus
public record Point(int X, int Y);

Dictionary<Point, string> map = new();
map[new Point(1, 2)] = "A";
string s = map[new Point(1, 2)];   // "A" : les deux clés sont égales

// BON : un record compare par valeur, hash cohérent inclus

public record Point(int X, int Y);

Dictionary<Point, string> map = new();

map[new Point(1, 2)] = "A";

string s = map[new Point(1, 2)];   // "A" : les deux clés sont égales

Avec une class classique, il faut redéfinir les deux méthodes à la main :

public class Point
{
    public int X { get; init; }
    public int Y { get; init; }

    public override bool Equals(object? obj) =>
        obj is Point p && p.X == X && p.Y == Y;

    public override int GetHashCode() => HashCode.Combine(X, Y);
}

public class Point

{

    public int X { get; init; }

    public int Y { get; init; }

    public override bool Equals(object? obj) =>

        obj is Point p && p.X == X && p.Y == Y;

    public override int GetHashCode() => HashCode.Combine(X, Y);

}

# Comparer les clés autrement

Parfois la clé est bonne, mais tu veux changer la règle d'égalité sans toucher au type. C'est le rôle d'un IEqualityComparer<T> passé au constructeur. Cas le plus fréquent : ignorer la casse des chaînes.

// Les clés sont comparées sans tenir compte de la casse
Dictionary<string, int> stock = new(StringComparer.OrdinalIgnoreCase);
stock["Pomme"] = 5;
int p = stock["POMME"];   // 5 : "POMME" et "Pomme" sont la même clé ici

// Les clés sont comparées sans tenir compte de la casse

Dictionary<string, int> stock = new(StringComparer.OrdinalIgnoreCase);

stock["Pomme"] = 5;

int p = stock["POMME"];   // 5 : "POMME" et "Pomme" sont la même clé ici

StringComparer fournit les variantes prêtes à l'emploi (Ordinal, OrdinalIgnoreCase, InvariantCulture...).

# Lire sans risque

L'indexeur lève une exception sur une clé absente. Selon le besoin :

// TryGetValue : test + récupération en une passe
if (stock.TryGetValue("Kiwi", out int q)) { /* ... */ }

// GetValueOrDefault : une valeur par défaut si absent
int quantite = stock.GetValueOrDefault("Kiwi", 0);

// TryAdd : ajoute seulement si la clé n'existe pas encore (pas d'exception)
stock.TryAdd("Pomme", 10);

// TryGetValue : test + récupération en une passe

if (stock.TryGetValue("Kiwi", out int q)) { /* ... */ }

// GetValueOrDefault : une valeur par défaut si absent

int quantite = stock.GetValueOrDefault("Kiwi", 0);

// TryAdd : ajoute seulement si la clé n'existe pas encore (pas d'exception)

stock.TryAdd("Pomme", 10);

# La suite

• Les collections en pratique - la vue d'ensemble des structures
• HashSet et l'égalité - la même mécanique côté appartenance, classe vs record
• Les records - l'égalité par valeur, idéale pour les clés