Pouvez-vous expliquer le principe de fonctionnement d'une table de hachage et comment les données y sont stockées?

Une table de hachage est une structure de données qui permet un accès très rapide aux données par clé. Son principe de fonctionnement repose sur l'utilisation d'une fonction de hachage, qui transforme la clé en un indice de tableau où la valeur correspondante est stockée.

Lorsqu'il faut sauvegarder une paire clé-valeur, la fonction de hachage calcule l'indice, et les données sont placées dans la cellule du tableau à cet indice. Lors de la recherche par clé, la fonction de hachage calcule à nouveau l'indice, et la valeur nécessaire est rapidement trouvée.

Si deux clés différentes donnent le même indice (collision), la méthode des chaînes est généralement utilisée : la cellule contient une liste de tous les éléments avec cet indice, et la recherche se fait dans cette liste.

Exemple en Dart (Flutter) :

void main() {
  Map<String, int> hashTable = {};
  hashTable['apple'] = 5;
  hashTable['banana'] = 3;

  print(hashTable['apple']); // 5
}

Ici, Map est une implémentation de la table de hachage, où la clé est une chaîne et la valeur est un nombre.