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

Une table de hachage (ou tableau associatif, dictionnaire) est une structure de données qui implémente l’interface du tableau associatif, c’est-à-dire qu’elle permet de stocker des paires "clé-valeur" et d’effectuer une recherche rapide de la valeur par la clé.

Le principe de fonctionnement repose sur l’utilisation d’une fonction de hachage, qui transforme la clé en un indice (hash) à l’intérieur du tableau (ou bucket).

Opérations principales :

1. Insertion : Le hash de la clé est calculé, et la paire "clé-valeur" est placée dans le bucket correspondant.
2. Suppression : Le hash de la clé est calculé, le bucket correspondant est trouvé, et la paire est supprimée.
3. Recherche : Le hash de la clé est calculé, le bucket correspondant est trouvé, et la paire avec la clé recherchée est cherchée.

Les tables de hachage offrent en moyenne de bonnes performances pour les opérations d’insertion, de suppression et de recherche (idéalement $O(1)$). Cependant, dans le pire des cas (lorsqu’il y a beaucoup de collisions, c’est-à-dire que différentes clés se transforment en le même indice), la performance peut diminuer à $O(n)$.

Il existe différentes stratégies pour résoudre les collisions :

• Méthode de chaînage (Separate Chaining) : Chaque bucket stocke une liste (par exemple, une liste chaînée) d’éléments ayant le même hash.
• Addressage ouvert (Open Addressing) : Lorsqu’une collision se produit, la recherche d’un espace libre se fait selon un algorithme prédéfini (sondage linéaire, quadratique, etc.).

Exemple conceptuel (simplifié) :

// Exemple de fonction de hachage simplifiée
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Transformation en entier 32 bits
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Méthode de chaînage
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Vérification si la clé existe déjà pour mettre à jour la valeur
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Clé non trouvée
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Suppression réussie
      }
    }
    return false; // Clé non trouvée
  }
}

// Utilisation
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

En JavaScript, les objets ({}) et les cartes (Map) sont des exemples d’implémentations de tables de hachage. Map est souvent préféré car il supporte des clés de tout type et maintient l’ordre d’insertion.

Propriétés d’une bonne fonction de hachage :

• Calcul rapide.
• Distribution uniforme des hashes pour différentes clés.
• Minimisation des collisions.