Utiliser les Hashmaps en JavaScript : Associer des Clés à des Valeurs dans les Structures de Données

Qu'est-ce qu'une Hashmap ?

Les hashmaps sont une structure de données qui stocke des paires clé-valeur, où chaque clé est unique et correspond à une valeur. La clé sert à indexer la valeur, permettant une récupération rapide de la valeur associée. Les hashmaps utilisent une fonction de hachage pour calculer un index servant au stockage et à la récupération des valeurs. La fonction de hachage prend la clé en entrée et génère un code de hachage unique, qui est ensuite utilisé pour déterminer l'index où la valeur sera stockée dans le tableau ou le bucket.

Hashmaps vs Objets JavaScript

Les objets JavaScript peuvent également stocker des paires clé-valeur, comme les hashmaps. Cependant, les hashmaps offrent des avantages par rapport aux objets :

1. Types de Clés : Les hashmaps permettent d'utiliser n'importe quel type de données comme clé, y compris les objets, les tableaux et les fonctions. Les objets JavaScript sont limités à l'utilisation de chaînes de caractères et de symboles comme clés.

   const hashmap = new Map();
   hashmap.set({ name: 'John' }, 25);
   hashmap.set([1, 2, 3], 'array');
   
   const obj = {};
   obj[{ name: 'John' }] = 25; // Invalide : Les objets ne peuvent pas être utilisés comme clés dans les objets

2. Maintien de l'Ordre : Les hashmaps maintiennent l'ordre d'insertion des éléments, ce qui signifie que l'ordre dans lequel les paires clé-valeur sont ajoutées à la hashmap est préservé. Les objets JavaScript ne garantissent aucun ordre de leurs propriétés.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   hashmap.set('c', 3);
   console.log(Array.from(hashmap.keys())); // Sortie : ['a', 'b', 'c']
   
   const obj = { a: 1, b: 2, c: 3 };
   console.log(Object.keys(obj)); // Sortie : ['a', 'b', 'c'] (Non garanti)

3. Suivi de la Taille : Les hashmaps fournissent des méthodes comme size() pour obtenir le nombre d'éléments stockés dans la hashmap. Avec les objets JavaScript, vous devriez suivre manuellement le nombre de propriétés ou utiliser Object.keys(obj).length pour déterminer la taille.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   console.log(hashmap.size); // Sortie : 2
   
   const obj = { a: 1, b: 2 };
   console.log(Object.keys(obj).length); // Sortie : 2

Complexité Temporelle des Opérations sur les Hashmaps

L'un des principaux avantages des hashmaps est leur complexité temporelle pour les opérations de base. Les hashmaps offrent une complexité temporelle constante, notée O(1), pour les opérations suivantes :

1. Insertion : L'ajout d'une nouvelle paire clé-valeur à la hashmap est une opération en O(1). La fonction de hachage est utilisée pour calculer l'index, et la paire clé-valeur est stockée à cet index dans le tableau ou le bucket.

2. Suppression : La suppression d'une paire clé-valeur de la hashmap est également une opération en O(1). La fonction de hachage est utilisée pour localiser l'index où la paire clé-valeur est stockée, puis elle est supprimée de cet index.

3. Recherche : La récupération de la valeur associée à une clé donnée est une opération en O(1). La fonction de hachage est utilisée pour calculer l'index basé sur la clé, et la valeur peut être accédée à cet index.

const cache = new Map();

function fetchData(key) {
  if (cache.has(key)) {
    return cache.get(key); // Récupérer les données du cache (recherche en O(1))
  } else {
    const data = fetchFromAPI(key); // Récupérer les données de l'API
    cache.set(key, data); // Stocker les données dans le cache (insertion en O(1))
    return data;
  }
}

Créer une Hashmap

Pour créer une nouvelle hashmap, utilisez le constructeur new Map(). Cela crée une hashmap vide pour stocker des paires clé-valeur.

const myHashmap = new Map();

Par exemple, pour créer une hashmap pour stocker des données d'étudiants :

const studentMap = new Map();

Ajouter des Paires Clé-Valeur

Pour ajouter une nouvelle paire clé-valeur à la hashmap, utilisez la méthode set(). Elle prend deux arguments : la clé et la valeur.

myHashmap.set('name', 'John');
myHashmap.set('age', 25);

Dans l'exemple ci-dessus, nous ajoutons deux paires clé-valeur à myHashmap : 'name' correspond à 'John' et 'age' correspond à 25.

Ajoutons quelques données d'étudiants à notre studentMap :

studentMap.set('1', { name: 'John', age: 20, major: 'Computer Science' });
studentMap.set('2', { name: 'Alice', age: 22, major: 'Mathematics' });
studentMap.set('3', { name: 'Bob', age: 21, major: 'Physics' });

Obtenir des Valeurs

Pour obtenir la valeur d'une clé donnée, utilisez la méthode get(). Elle prend la clé comme argument et retourne la valeur.

const name = myHashmap.get('name');
console.log(name); // Sortie : 'John'

Dans cet exemple, nous obtenons la valeur de la clé 'name' de myHashmap, qui est 'John'.

Pour obtenir les données d'un étudiant spécifique de studentMap :

const student = studentMap.get('2');
console.log(student); // Sortie : { name: 'Alice', age: 22, major: 'Mathematics' }

Vérifier l'Existence d'une Clé

Pour vérifier si une clé existe dans la hashmap, utilisez la méthode has(). Elle prend la clé comme argument et retourne une valeur booléenne.

const hasAge = myHashmap.has('age');
console.log(hasAge); // Sortie : true

Ici, nous vérifions si la clé 'age' existe dans myHashmap en utilisant la méthode has(), qui retourne true.

Vérifier si un étudiant avec l'ID '4' existe dans studentMap :

const hasStudent = studentMap.has('4');
console.log(hasStudent); // Sortie : false

Supprimer des Paires Clé-Valeur

Pour supprimer une paire clé-valeur de la hashmap, utilisez la méthode delete(). Elle prend la clé comme argument et supprime la paire clé-valeur de la hashmap.

myHashmap.delete('age');
console.log(myHashmap.has('age')); // Sortie : false

Dans cet exemple, nous supprimons la paire clé-valeur avec la clé 'age' de myHashmap en utilisant la méthode delete(). Après suppression, has('age') retourne false.

Supprimer un étudiant de studentMap :

studentMap.delete('1');
console.log(studentMap.has('1')); // Sortie : false

Obtenir la Taille de la Hashmap

Pour obtenir le nombre de paires clé-valeur dans la hashmap, utilisez la propriété size. Elle retourne la taille de la hashmap.

console.log(myHashmap.size); // Sortie : 1

Ici, nous accédons à la propriété size de myHashmap, qui retourne 1, indiquant qu'il y a une paire clé-valeur dans la hashmap.

Obtenir le nombre d'étudiants dans studentMap :

console.log(studentMap.size); // Sortie : 2

Résumé des Opérations sur les Hashmaps

Ce sont les opérations de base que vous pouvez faire sur une hashmap en utilisant l'objet Map de JavaScript. L'objet Map fournit un moyen de travailler avec des paires clé-valeur et offre des méthodes pour manipuler et accéder aux données dans la hashmap.

L'objet Map conserve l'ordre des paires clé-valeur, ce qui signifie que lorsque vous itérez sur la hashmap en utilisant des méthodes comme forEach() ou la boucle for...of, les paires clé-valeur seront accédées dans l'ordre où elles ont été ajoutées.

La Méthode forEach()

La méthode forEach() est intégrée à l'objet Map. Elle vous permet d'itérer sur chaque paire clé-valeur dans la hashmap. Elle utilise une fonction de callback qui s'exécute pour chaque paire.

La fonction de callback reçoit trois paramètres :

1. value : La valeur de la paire actuelle.
2. key : La clé de la paire actuelle.
3. map : La hashmap sur laquelle forEach() a été appelée.

const shoppingCart = new Map();
shoppingCart.set('shirt', 25);
shoppingCart.set('pants', 50);
shoppingCart.set('shoes', 75);

let totalPrice = 0;

shoppingCart.forEach((price) => {
  totalPrice += price;
});

console.log(`Total Price: $${totalPrice}`);

Total Price: $150

La Boucle for...of

Vous pouvez également utiliser une boucle for...of pour itérer sur une hashmap. La boucle for...of fonctionne avec les objets itérables comme les tableaux, les chaînes de caractères et les maps.

Lorsque vous utilisez for...of avec une hashmap, chaque itération retourne un tableau avec la paire [key, value].

Visualiser l'Itération sur une Hashmap

Voici un diagramme montrant comment fonctionne l'itération sur une hashmap :

Le diagramme montre la hashmap et l'itération sur chaque paire clé-valeur. Pour chaque paire, nous la traitons selon ce que nous devons faire, comme des calculs, des comparaisons ou d'autres opérations.

forEach() et for...of vous permettent tous deux d'itérer sur les paires clé-valeur d'une hashmap en JavaScript. Celui que vous utilisez dépend de vos be­­soins spécifiques. forEach() est pratique quand vous voulez faire quelque chose pour chaque paire, tandis que for...of est utile quand vous avez besoin à la fois des clés et des valeurs dans chaque itération.

Gardez à l'esprit que l'ordre d'itération dans une hashmap est basé sur l'ordre dans lequel les paires ont été ajoutées. L'objet Map de JavaScript conserve cet ordre.

Itérer sur les hashmaps est courant lors du travail avec des paires clé-valeur, et JavaScript offre ces méthodes pour le rendre plus facile et plus rapide. Pour plus d'informations sur les objets Map et l'itération, consultez les MDN Web Docs.

Qu'est-ce qu'une Collision ?

Dans une hashmap, les collisions se produisent lorsque deux clés ou plus se hachent au même index. Cela signifie que plusieurs paires clé-valeur doivent être stockées à la même position dans le tableau ou le bucket. Si elles ne sont pas bien gérées, les collisions peuvent entraîner l'écrasement de données ou un ralentissement de la récupération des valeurs.

Voici un exemple de collision dans une hashmap :

Dans cet exemple, les clés 'John' et 'Alice' se hachent toutes deux au même index (Index 0), provoquant une collision.

Si les collisions ne sont pas corrigées, ces problèmes peuvent survenir :

1. Écrasement de Données : Si une nouvelle paire clé-valeur se hache au même index qu'une paire existante, la paire existante pourrait être écrasée, causant une perte de données.

2. Récupération Ralentie : Lorsque des collisions se produisent, la recherche de valeurs devient plus lente car la hashmap doit effectuer plus d'étapes pour trouver la bonne valeur parmi les paires en collision.

Pour corriger ces problèmes, les hashmaps utilisent des techniques de gestion des collisions.

Moyens de Gérer les Collisions

Il existe deux principales façons de gérer les collisions dans les hashmaps :

1. Chaînage Séparé

• Chaque index du tableau ou bucket de la hashmap stocke une liste chaînée de paires clé-valeur.
• Lorsqu'une collision se produit, la nouvelle paire clé-valeur est ajoutée à la liste chaînée à cet index.
• Trouver une valeur signifie parcourir la liste chaînée à l'index haché pour trouver la paire clé-valeur souhaitée.

2. Adressage Ouvert

• L'adressage ouvert n'utilise pas de listes chaînées pour gérer les collisions. Au lieu de cela, il cherche le prochain index libre dans le tableau lorsqu'une collision se produit.
• Il existe différentes façons de trouver l'index suivant, telles que le sondage linéaire, le sondage quadratique et le double hachage.
• Lorsqu'une collision se produit, la hashmap utilise la méthode de sondage pour trouver le prochain emplacement vide dans le tableau pour stocker la paire clé-valeur.

Bonnes Pratiques pour Utiliser les Hashmaps

1. Choisissez une bonne fonction de hachage qui réduit les collisions et répartit les clés uniformément.
2. Réfléchissez au nombre d'éléments attendus et aux performances souhaitées lors du choix de la taille de départ de la hashmap.
3. Soyez conscient de l'impact des collisions sur la vitesse des opérations de hashmap, particulièrement avec de nombreuses collisions.
4. Utilisez le chaînage séparé ou l'adressage ouvert selon les besoins de votre application, en tenant compte de facteurs comme l'utilisation de la mémoire et la vitesse de récupération.