Qu'est-ce qu'une table de hachage?

Une table de hachage, ou tableau associatif, est une structure de données qui implémente l'interface de tableau associatif, c'est-à-dire qu'elle relie des clés à des valeurs. Elle utilise une fonction de hachage pour calculer un indice, ou "hash", de la case ou du slot où la valeur recherchée doit se trouver.

Composants principaux:

• Clé: Identifiant unique de l'élément.
• Valeur: Données associées à la clé.
• Fonction de hachage: Convertit la clé en une valeur numérique (hash), utilisée pour déterminer l'indice de la case.
• Cases (Buckets): Tableau où sont stockés les paires clé-valeur.
• Gestion des collisions: Mécanisme pour résoudre les situations où différentes clés donnent le même hash (et pointent donc vers la même case). Méthodes courantes:
  • Chaînage: Chaque case stocke une liste (par exemple, une liste chaînée) d'éléments dont les hashes pointent vers cette case.
  • Adresse ouverte: En cas de collision, on cherche la prochaine case libre en utilisant des algorithmes comme le hachage linéaire, quadratique ou double hachage.

Principe de fonctionnement:

1. Insertion: La fonction de hachage s'applique à la clé pour obtenir le hash. Le hash est utilisé pour déterminer l'indice de la case. La paire clé-valeur est stockée dans cette case. En cas de collision, la méthode de gestion des collisions est appliquée.

   // Exemple d'insertion dans une table de hachage (chaînage)
   function insert(key, value) {
     const hash = hashFunction(key); // Calcul du hash
     const bucketIndex = hash % tableSize; // Détermination de l'indice de la case
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Création de la liste si elle n'existe pas
     }
     buckets[bucketIndex].push({ key, value }); // Ajout de la paire à la liste
   }
   

2. Recherche: La fonction de hachage s'applique à la clé pour obtenir le hash. Le hash est utilisé pour déterminer l'indice de la case. Ensuite, dans cette case, on recherche l'élément avec la clé donnée. En utilisant la méthode de chaînage, on cherche dans la liste de la case. En adresse ouverte, on vérifie successivement d'autres cases jusqu'à trouver l'élément ou déterminer qu'il n'existe pas.

   // Exemple de recherche dans une table de hachage (chaînage)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Calcul du hash
     const bucketIndex = hash % tableSize; // Détermination de l'indice de la case
   
     if (buckets[bucketIndex]) {
       // Recherche dans la liste de la case
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Si suppression nécessaire
           return value; // Retourne la valeur
         }
       }
     }
     return undefined; // Élément non trouvé
   }
   

Avantages:

• Opérations d'insertion, de recherche et de suppression rapides en moyenne (O(1)).
• Utilisation efficace de la mémoire par rapport à un tableau d'adresses directes (si les clés sont dispersées).

Inconvénients:

• La performance peut diminuer en cas de nombreuses collisions (dans le pire cas O(n)).
• L'ordre d'insertion des éléments n'est pas conservé.
• Nécessite une bonne fonction de hachage pour une distribution uniforme des clés.

En JavaScript, les tables de hachage sont implémentées via l'objet intégré Map et, historiquement, Object. Map est préféré car il permet d'utiliser n'importe quel type de données comme clé et conserve l'ordre d'insertion. Object convertit toutes les clés en chaînes.