Parlez des tables de hachage et de leur principe de fonctionnement principal.

La table de hachage (hash map) est une structure de données qui implémente un tableau associatif, mappant des clés à des valeurs.

Principe de fonctionnement:

1. Hachage: Pour chaque clé, on calcule un code hash, une valeur numérique de taille fixe à l'aide d'une fonction de hachage. Une bonne fonction de hachage répartit uniformément les codes hash sur toute la plage de sorties.
2. Indexation: Le code hash calculé est utilisé pour déterminer l'indice (position) dans le tableau où la valeur correspondante sera stockée. Souvent, le code hash modulo la taille du tableau (hash(key) % taille_array) donne l'indice final.
3. Stockage: Dans le tableau, à l'indice calculé, on stocke une paire (clé, valeur).
4. Recherche: Pour trouver une valeur par clé, on recalcule le code hash de la clé, on détermine l'indice, et à cet indice on extrait la valeur.
5. Collisions: Surviennent lorsque différentes clés ont le même code hash. Il existe plusieurs méthodes pour résoudre les collisions:
   • Méthode de chaînage (Separate Chaining): À chaque indice du tableau, on maintient une liste (ou une autre structure de données) contenant toutes les paires (clé, valeur) dont les codes hash mènent à cet indice.
   • Méthode d'adressage ouvert (Open Addressing): Lorsqu'une collision se produit, on cherche un autre emplacement libre dans le tableau selon une règle déterminée (sondage linéaire, sondage quadratique, double hachage).

Avantages:

• En moyenne, les opérations d'insertion, de suppression et de recherche ont une complexité O(1), si la fonction de hachage est bonne et que les collisions sont rares.

Inconvénients:

• Le pire cas de performance peut être O(n), si toutes les clés sont hachées au même indice (par exemple, avec une mauvaise fonction de hachage ou beaucoup de collisions).
• Nécessite de la mémoire supplémentaire pour le tableau et éventuellement pour la résolution des collisions.

En Swift, les tables de hachage sont implémentées avec le type Dictionary.

// Exemple d'utilisation de Dictionary en Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Accès par clé
let value = myDictionary["banana"] // Obtiendra Optional(2)

// Ajout/mise à jour
myDictionary["grape"] = 4 // Ajoute une nouvelle paire
myDictionary["apple"] = 10 // Met à jour la valeur pour la clé "apple"

// Suppression
myDictionary["orange"] = nil // Supprime la paire avec la clé "orange"