Carte de hachage utilisant Javascript

Introduction

• Une carte de hachage, également connue sous le nom de table de hachage, est une structure de données qui implémente un type de données abstrait de tableau associatif, une structure qui peut mapper des clés à des valeurs.

• 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.

Implémentation d'une simple carte de hachage en JavaScript

let hashMap = {};
hashMap['key1'] = 'value1';
hashMap['key2'] = 'value2';
console.log(hashMap['key1']); // Outputs: value1

Gérer les collisions

• La gestion des collisions est un aspect important de la mise en œuvre d'une Hash Map. Une collision se produit lorsque deux clés différentes produisent le même hachage. Il existe plusieurs stratégies pour gérer les collisions, mais les deux plus courantes sont le chaînage séparé et le sondage linéaire.

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!