Q/A MAP, HMAP, et Structures de Données Associées

---

🔹 1. Qu’est-ce qu’un Dictionary<TKey, TValue> et comment fonctionne-t-il ?

✅ Définition :

Dictionary<TKey, TValue> est une collection générique du namespace System.Collections.Generic qui stocke des paires clé-valeur.
Chaque clé doit être unique et permet un accès rapide à la valeur correspondante.

✅ Fonctionnement interne :

• Basé sur une table de hachage (hash table).

• Chaque clé est transformée en un code de hachage (GetHashCode()).

• Ce code détermine le bucket (emplacement) où la paire clé-valeur est stockée.

• Lorsqu’on recherche une clé :

  1. Le dictionnaire calcule le hash.

  2. Il accède au bucket correspondant.

  3. Il compare la clé (via Equals) pour confirmer la correspondance.

🧩 Exemple :

var dict = new Dictionary<int, string>();
dict.Add(1, "Alice");
dict.Add(2, "Bob");

Console.WriteLine(dict[1]); // "Alice"

🧠 Complexité moyenne :

• Insertion : O(1)

• Recherche : O(1)

• Suppression : O(1)

---

🔹 2. Quelle est la différence entre Hashtable et Dictionary<TKey, TValue> ?

Critère	Hashtable	Dictionary<TKey, TValue>
Namespace	System.Collections	System.Collections.Generic
Typage	Non générique (clé/valeur en object)	Générique (TKey, TValue)
Type Safety	Non typé (cast nécessaire)	Type-sûr
Performance	Boxing/unboxing pour types valeur	Plus rapide (pas de boxing)
Ordre d’insertion	Non garanti	Non garanti
Utilisation moderne	Déconseillée	Recommandée

🧩 Exemple :

// Hashtable (ancienne approche)
Hashtable ht = new Hashtable();
ht["id"] = 123;  // clé en string, valeur en object

// Dictionary (moderne)
Dictionary<string, int> dict = new Dictionary<string, int>();
dict["id"] = 123;

🧠 Conclusion :

Dictionary<TKey, TValue> est plus performant, plus sûr et préféré à Hashtable dans tout nouveau développement .NET.

---

🔹 3. Qu’est-ce qu’un ConcurrentDictionary<TKey, TValue> et pourquoi est-il utile ?

✅ Définition :

ConcurrentDictionary<TKey, TValue> (namespace System.Collections.Concurrent) est une version thread-safe du Dictionary, conçue pour les environnements multi-thread.

✅ Caractéristiques :

• Gère automatiquement les verrous internes (fine-grained locking).

• Permet plusieurs accès concurrents sans lever d’exception.

• Fournit des méthodes atomiques comme :

  • TryAdd(key, value)

  • TryUpdate(key, oldValue, newValue)

  • GetOrAdd(key, valueFactory)

🧩 Exemple :

var concurrentDict = new ConcurrentDictionary<int, string>();
concurrentDict.TryAdd(1, "Alice");

// Thread-safe access
concurrentDict.AddOrUpdate(1, "Bob", (key, oldValue) => oldValue + " Updated");

Console.WriteLine(concurrentDict[1]); // "Alice Updated"

🧠 Pourquoi utile :

Utile dans les applications multi-thread, serveurs web, ou services parallèles sans avoir à gérer manuellement les verrous (lock).

---

🔹 4. Comment fonctionne le HashSet et dans quel cas l’utiliser ?

✅ Définition :

HashSet<T> est une collection d’éléments uniques, basée sur une table de hachage.

✅ Fonctionnement :

• Chaque élément est stocké en fonction de son GetHashCode().

• Avant d’ajouter un élément, le HashSet vérifie s’il existe déjà.

• Les doublons sont automatiquement ignorés.

🧩 Exemple :

HashSet<string> set = new HashSet<string>();
set.Add("A");
set.Add("B");
set.Add("A"); // Ignoré car déjà présent

Console.WriteLine(set.Count); // 2

🧠 Quand l’utiliser :

Quand tu veux tester l’unicité ou rechercher rapidement des valeurs sans associer de clé.
Exemples : filtrage, détection de doublons, comparaison d’ensembles.

---

🔹 5. Différence entre SortedDictionary<TKey, TValue> et SortedList<TKey, TValue>

Critère	SortedDictionary<TKey, TValue>	SortedList<TKey, TValue>
Structure interne	Arbre binaire équilibré (Red-Black Tree)	Tableaux triés internes
Tri	Automatique par clé	Automatique par clé
Insertion/Suppression	O(log n)	O(n)
Accès indexé	Non	Oui
Mémoire	Plus élevée	Plus compacte
Usage recommandé	Données modifiées fréquemment	Données stables et triées

🧩 Exemple :

var sortedDict = new SortedDictionary<int, string>();
sortedDict.Add(2, "B");
sortedDict.Add(1, "A");

var sortedList = new SortedList<int, string>();
sortedList.Add(2, "B");
sortedList.Add(1, "A");

🧠 Conclusion :

• SortedList → petite collection, peu de modifications.

• SortedDictionary → plus efficace pour de nombreuses insertions/suppressions.

---

🔹 6. Pourquoi la méthode TryGetValue() est-elle recommandée pour accéder aux valeurs d’un Dictionary<TKey, TValue> ?

✅ Explication :

L’accès direct via dict[key] lève une exception si la clé n’existe pas.
TryGetValue() permet une lecture sécurisée sans exception.

🧩 Exemple :

var dict = new Dictionary<int, string> { [1] = "Alice" };

if (dict.TryGetValue(2, out string value))
    Console.WriteLine(value);
else
    Console.WriteLine("Key not found"); // Pas d'exception

🧠 Avantages :

• Plus performant (évite le double test).

• Plus propre et plus sûr.

• Bonnes pratiques dans le code de production.

---

🔹 7. Comment implémenter une table de hachage personnalisée en C# ?

✅ Principe :

Une table de hachage se compose :

1. D’un tableau de buckets.

2. D’une fonction de hachage.

3. D’un mécanisme de gestion des collisions.

🧩 Exemple simplifié :

public class SimpleHashTable<K, V>
{
    private const int Size = 10;
    private readonly List<KeyValuePair<K, V>>[] _buckets = new List<KeyValuePair<K, V>>[Size];

    public void Add(K key, V value)
    {
        int index = Math.Abs(key.GetHashCode()) % Size;
        _buckets[index] ??= new List<KeyValuePair<K, V>>();
        _buckets[index].Add(new KeyValuePair<K, V>(key, value));
    }

    public bool TryGetValue(K key, out V value)
    {
        int index = Math.Abs(key.GetHashCode()) % Size;
        if (_buckets[index] != null)
        {
            foreach (var kv in _buckets[index])
            {
                if (kv.Key.Equals(key))
                {
                    value = kv.Value;
                    return true;
                }
            }
        }
        value = default!;
        return false;
    }
}

✅ Utilisation :

var table = new SimpleHashTable<string, int>();
table.Add("Alice", 25);
if (table.TryGetValue("Alice", out int age))
    Console.WriteLine(age); // 25

🧠 Concepts clés :

• Fonction de hachage → distribue les clés.

• Buckets → regroupent les collisions.

• Comparaison → via Equals.

---

🔹 8. Comment gérer les collisions dans une table de hachage en C# ?

Une collision se produit lorsque deux clés différentes produisent le même code de hachage.
Plusieurs stratégies existent :

Technique	Description	Exemple d’utilisation
Chaînage (Chaining)	Chaque bucket contient une liste de paires (LinkedList)	Utilisée par Dictionary<TKey, TValue>
Ouverture linéaire (Linear Probing)	Recherche du prochain emplacement vide dans le tableau	Implémentation personnalisée
Double hachage (Double Hashing)	Utilisation d’une deuxième fonction de hachage pour trouver le slot suivant	Avancé, rarement nécessaire

🧩 Exemple de chaînage :

_bucket[index] = new List<KeyValuePair<K, V>>(); // plusieurs éléments dans un même bucket

🧠 Résumé :

En .NET, Dictionary et HashSet utilisent le chaînage séparé, garantissant des performances stables même en cas de collisions.

---

📘 RÉCAPITULATIF SYNTHÉTIQUE

Structure	Caractéristiques principales	Thread-safe	Complexité recherche
Dictionary<TKey, TValue>	Table de hachage clé-valeur typée	❌	O(1)
Hashtable	Ancien, non générique	❌	O(1)
ConcurrentDictionary<TKey, TValue>	Thread-safe	✅	O(1)
HashSet<T>	Ensemble d’éléments uniques	❌	O(1)
SortedDictionary<TKey, TValue>	Arbre rouge-noir, trié	❌	O(log n)
SortedList<TKey, TValue>	Tableau trié	❌	O(log n) (recherche) / O(n) (insertion)

---