Les Tables de Hachage en JavaScript

Introduction aux Tables de Hachage

Une table de hachage représente une implémentation d'un tableau associatif, constitué d'une liste de paires clé-valeur. Ce mécanisme permet de récupérer une valeur par l'intermédiaire d'une clé. En interne, une table de hachage se sert d'une fonction de hachage pour convertir une clé en un indice, qui pointe vers l'emplacement où la valeur est conservée en mémoire. Ce dispositif permet d'effectuer des opérations de recherche, d'insertion et de suppression de manière très rapide.

Implémentation d'une Table de Hachage en JavaScript

Il existe principalement deux façons de créer une table de hachage ou un tableau associatif en JavaScript.

Utilisation de l'Objet

La manière la plus simple d'implémenter une table de hachage est d'utiliser le type d'objet. En effet, tous les objets non scalaires en JavaScript fonctionnent comme des tableaux associatifs, c'est-à-dire qu'un objet peut servir de table de hachage.

Voici un exemple concernant l'objet :

var simpleHash = {}; // ou var simpleHash = new Object();
simpleHash['key1'] = 'value1';
simpleHash['key2'] = 'value2';
simpleHash['key3'] = 'value3';

for (var key in simpleHash) {  
    if (simpleHash.hasOwnProperty(key)) {  // utiliser hasOwnProperty pour éviter les propriétés du prototype  
        console.log('la clé est : ' + key + ', la valeur est : ' + simpleHash[key]);  
    }
}

Le résultat afficherait :

la clé est : key1, la valeur est : value1
la clé est : key2, la valeur est : value2
la clé est : key3, la valeur est : value3

Inconvénients de l'Approche Objet

Cependant, cette méthode présente quelques inconvénients : - Les objets portent en eux leurs propres propriétés, ce qui peut provoquer des conflits avec les noms de clés. - Il n’existe pas de méthode simple pour obtenir la taille d'une table de hachage sauvegardée dans un objet, nécessitant un suivi manuel. - Les clés utilisées sont restreintes aux types String ou Symbol. - Les objets ne sont pas optimisés pour les ajouts ou suppressions fréquents de paires clé-valeur.

Utilisation de l'Objet Map

Pour contourner ces limitations, l'objet Map a été conçu. Son utilisation présente de nombreux avantages : - Il n'y a pas de clés préexistantes de type objet qui peuvent entrer en collision. - L'objet Map possède une propriété size qui permet de suivre son contenu. - Les clés dans un objet Map peuvent être de n'importe quel type de données. - Il est optimisé pour les additions et suppressions fréquentes de paires clé-valeur.

Méthodes de l'Objet Map

L'objet Map dispose également des méthodes suivantes : - .clear() : Supprime toutes les paires clé-valeur de l'objet Map. - .delete(key) : Supprime la paire clé-valeur correspondante et renvoie true si la clé existe, false sinon. - .get(key) : Renvoie la valeur associée à la clé, ou undefined si la clé n'existe pas. - .has(key) : Renvoie true si la clé est présente, false sinon. - .set(key, value) : Définit la valeur pour la clé dans l'objet Map et renvoie l'objet Map.

Exemple de l'Objet Map

var mapHash = new Map();
mapHash.set('key1', 'value1');
mapHash.set('key2', 'value2');
mapHash.set('key3', 'value3');

console.log(mapHash.get('key3')); // Sortie : value3

mapHash.set('key1', 'nouvelle valeur');
console.log(mapHash.get('key1')); // Sortie : nouvelle valeur
console.log(mapHash.size); // Sortie : 3

mapHash.delete('key2');
console.log(mapHash.size); // Sortie : 2

for (const [key, value] of mapHash) {  
    console.log(key + ' = ' + value);
} // Sortie :
// key1 = nouvelle valeur
// key3 = value3

Conclusion

Les tables de hachage constituent un outil puissant pour gérer des données sous forme de paires clé-valeur, offrant ainsi des performances avantageuses pour le stockage et la récupération d'informations.