Maison >interface Web >js tutoriel >Carte de hachage utilisant Javascript
Il utilise une fonction de hachage pour calculer un index dans un tableau de compartiments ou d'emplacements, à partir duquel la valeur souhaitée peut être trouvée.
Le premier avantage d’une Hash Map est son efficacité. Les opérations telles que l'insertion d'une nouvelle paire clé-valeur, la suppression d'une paire clé-valeur et la recherche d'une valeur à partir d'une clé sont toutes très rapides, prenant souvent un temps constant en moyenne.
let hashMap = {}; hashMap['key1'] = 'value1'; hashMap['key2'] = 'value2'; console.log(hashMap['key1']); // Outputs: value1
Chaînage séparé : Dans un chaînage séparé, chaque emplacement du tableau de la table de hachage contient une liste chaînée (ou une autre structure de données pouvant contenir plusieurs éléments). Lorsqu'une collision se produit, la nouvelle paire clé-valeur est ajoutée à la fin de la liste chaînée à l'index correspondant.
Voici une implémentation simple d'une Hash Map utilisant un chaînage séparé en JavaScript :
class HashMap { constructor() { this.table = new Array(100).fill(null).map(() => []); } put(key, value) { const index = this.hash(key); const chain = this.table[index]; const existingPair = chain.find(([existingKey]) => existingKey === key); if (existingPair) { existingPair[1] = value; } else { chain.push([key, value]); } } get(key) { const index = this.hash(key); const chain = this.table[index]; const pair = chain.find(([existingKey]) => existingKey === key); if (pair) { return pair[1]; } return null; } hash(key) { let hash = 0; for (let i = 0; i < key.length; i++) { hash += key.charCodeAt(i); } return hash % this.table.length; } }
Sonde linéaire : En sonde linéaire, lorsqu'une collision se produit, la carte de hachage vérifie l'emplacement suivant dans le tableau (et passe au suivant s'il est également plein, et ainsi de suite) jusqu'à ce qu'elle trouve un emplacement vide où il peut stocker la nouvelle paire clé-valeur.
Voici une implémentation simple d'une Hash Map utilisant un sondage linéaire en JavaScript :
class HashMap { constructor() { this.table = new Array(100).fill(null); } put(key, value) { let index = this.hash(key); while (this.table[index] !== null) { index = (index + 1) % this.table.length; } this.table[index] = [key, value]; } get(key) { let index = this.hash(key); while (this.table[index] !== null) { if (this.table[index][0] === key) { return this.table[index][1]; } index = (index + 1) % this.table.length; } return null; } hash(key) { let hash = 0; for (let i = 0; i < key.length; i++) { hash += key.charCodeAt(i); } return hash % this.table.length; } }
Dans les deux exemples, la méthode de hachage est une simple fonction de hachage qui convertit la clé en un entier utilisé comme index dans le tableau. Dans un scénario réel, vous utiliseriez probablement une fonction de hachage plus complexe pour réduire le risque de collision.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!