Les tables de hachage, également connues sous le nom de tables de dispersion, sont des structures de données essentielles utilisées pour stocker des paires clé-valeur. Elles permettent une récupération et une insertion de données extrêmement rapides en transformant une clé en un index où la valeur est stockée. Cette transformation est effectuée par une fonction de hachage.
Principes Fondamentaux des Tables de Hachage
- Accès Direct : L'idée principale est d'accéder aux données directement via une clé, plutôt que de parcourir la structure séquentiellement. Un tableau est un exemple simple de table de hachage où l'indice est la clé.
- Détection de Présence : Elles sont particulièrement efficaces pour vérifier rapidement si un élément est présent dans une collection.
- Fonction de Hachage : C'est une fonction qui prend une clé en entrée (par exemple, une chaîne de caractères) et renvoie un nombre entier, qui sert d'index dans le tableau sous-jacent de la table de hachage.
- Collisions : Plusieurs clés peuvent produire le même index. C'est ce qu'on appelle une collision de hachage. Les méthodes courantes pour les résoudre incluent :
- Chaînage (Separate Chaining) : À chaque index du tableau, on stocke une liste chaînée (ou une autre structure de données) contenant toutes les paires clé-valeur qui ont été hachées à cet index.
- Sondage Linéaire (Linear Probing) : Si l'index calculé est déjà occupé, on cherche l'emplacement libre suivant dans le tableau.
- Implémentations Courantes : En JavaScript, les structures de données qui se comportent comme des tables de hachage incluent les objets (pour de simples paires clé-valeur), les
Set(pour stocker des valeurs uniques) et lesMap(pour des paires clé-valeur plus complexes, avec des clés de tout type).
Problème 1 : Anagramme Valide (LeetCode 242)
Étant données deux chaînes de caractères s et t, déterminez si t est un anagramme de s. Un anagramme est formé en réarrangeant les lettres d'un mot ou d'une phrase pour produire un nouveau mot ou phrase, en utilisant toutes les lettres originales exactement une fois.
Approche 1 : Utilisation d'un Tableau de Fréquences
Puisqu'il s'agit de lettres minuscules de l'alphabet anglais, nous pouvons utiliser un tableau de taille 26 pour stocker les fréquences de chaque caractère. On parcourt la première chaîne s et on incrémente le compteur pour chaque caractère. Ensuite, on parcourt la seconde chaîne t et on décrémente le compteur. Si à un moment donné, un compteur devient négatif ou si la longueur des chaînes est différente, ce n'est pas un anagramme. Enfin, tous les compteurs doivent être à zéro.
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
function estAnagrammeAvecTableau(s, t) {
if (s.length !== t.length) {
return false;
}
// Un tableau pour stocker les fréquences des 26 lettres de l'alphabet.
// L'ASCII de 'a' sert de décalage pour mapper les caractères aux indices 0-25.
const compteursCaracteres = new Array(26).fill(0);
const codeAsciiA = 'a'.charCodeAt(0);
// Incrémenter les compteurs pour les caractères de la chaîne s
for (let i = 0; i < s.length; i++) {
compteursCaracteres[s.charCodeAt(i) - codeAsciiA]++;
}
// Décrémenter les compteurs pour les caractères de la chaîne t
for (let i = 0; i < t.length; i++) {
const indexCaractere = t.charCodeAt(i) - codeAsciiA;
if (compteursCaracteres[indexCaractere] === 0) { // Si un caractère de t n'existe pas dans s ou est déjà "épuisé"
return false;
}
compteursCaracteres[indexCaractere]--;
}
// Pas besoin de vérifier si tous les compteurs sont à zéro à la fin,
// car si toutes les conditions précédentes sont passées et les longueurs sont égales,
// cela implique que tous les compteurs doivent être à zéro.
return true;
}
// Exemple d'utilisation
// console.log(estAnagrammeAvecTableau("anagram", "nagaram")); // true
// console.log(estAnagrammeAvecTableau("rat", "car")); // false
Approche 2 : Utilisation d'une Map
Une Map offre plus de flexibilité car elle peut gérer n'importe quel type de caractère (pas seulement les minuscules de l'alphabet) et n'a pas de limite de taille fixe. Le principe reste le même : compter les fréquences des caractères de s, puis décrémenter pour t.
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
function estAnagrammeAvecMap(s, t) {
if (s.length !== t.length) {
return false;
}
const frequences = new Map();
// Compter les fréquences des caractères dans la chaîne s
for (const char of s) {
frequences.set(char, (frequences.get(char) || 0) + 1);
}
// Décrémenter les fréquences pour les caractères de la chaîne t
for (const char of t) {
// Si le caractère n'est pas dans la map ou son compteur est déjà à zéro,
// alors t contient un caractère non présent dans s ou en plus grande quantité.
if (!frequences.has(char) || frequences.get(char) === 0) {
return false;
}
frequences.set(char, frequences.get(char) - 1);
}
// Similaire à l'approche avec tableau, une vérification finale n'est pas nécessaire
// car les longueurs égales et la logique de décrémentation garantissent l'exactitude.
return true;
}
// Exemple d'utilisation
// console.log(estAnagrammeAvecMap("listen", "silent")); // true
// console.log(estAnagrammeAvecMap("hello", "world")); // false
Problème 2 : Intersection de Deux Tableaux (LeetCode 349)
Étant donnés deux tabelaux d'entiers nums1 et nums2, retournez leur intersection. Chaque élément du résultat doit être unique, et l'ordre n'a pas d'importance.
Approche 1 : Utilisation de Set
La propriété principale des Set est de stocker uniquement des valeurs uniques. Cela simplifie grandement la tâche de trouver l'intersection tout en garantissant l'unicité des éléments.
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
function trouverIntersectionAvecSet(nums1, nums2) {
// Crée un Set à partir du premier tableau pour des recherches rapides
const elementsUniques1 = new Set(nums1);
const elementsCommuns = new Set();
// Parcourt le second tableau
for (const num of nums2) {
// Si l'élément du second tableau est présent dans le Set du premier,
// ajoute-le au Set des éléments communs. Le Set gère l'unicité automatiquement.
if (elementsUniques1.has(num)) {
elementsCommuns.add(num);
}
}
// Convertit le Set des éléments communs en tableau
return Array.from(elementsCommuns);
}
// Exemple d'utilisation
// console.log(trouverIntersectionAvecSet([1, 2, 2, 1], [2, 2])); // [2]
// console.log(trouverIntersectionAvecSet([4, 9, 5], [9, 4, 9, 8, 4])); // [9, 4] ou [4, 9]
Approche 2 : Utilisation d'un Tableau de Présence (pour petites plages d'entiers)
Si les nombres dans les tableaux sont dans une plage limitée (par exemple, de 0 à 1000), un tableau booléen (ou un tableau d'entiers pour des statuts) peut servir de table de hachage direct.
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
function trouverIntersectionAvecTableauDePresence(nums1, nums2) {
// Déterminer la valeur maximale pour dimensionner le tableau de présence
// Note: Cette approche est efficace pour des entiers non négatifs dans une plage limitée.
const maxVal = Math.max(...nums1, ...nums2);
const estPresent = new Array(maxVal + 1).fill(0); // 0: absent, 1: présent dans nums1, 2: ajouté au résultat
// Marquer les éléments de nums1
for (const num of nums1) {
estPresent[num] = 1;
}
const resultat = [];
// Vérifier les éléments de nums2
for (const num of nums2) {
// Si l'élément est dans nums1 (marqué par 1) et n'a pas déjà été ajouté au résultat (pas marqué par 2)
if (estPresent[num] === 1) {
resultat.push(num);
estPresent[num] = 2; // Marquer comme "ajouté au résultat" pour éviter les doublons
}
}
return resultat;
}
// Exemple d'utilisation
// console.log(trouverIntersectionAvecTableauDePresence([1, 2, 2, 1], [2, 2])); // [2]
Problème 3 : Nombre Heureux (LeetCode 202)
Un "nombre heureux" est défini par le processus suivant : pour un entier positif, on remplace le nombre par la somme des carrés de ses chiffres. On répète ce processus jusqu'à ce que le nombre devienne 1 (auquel cas il est heureux) ou qu'il entre dans un cycle infini qui n'inclut pas 1 (auquel cas il n'est pas heureux).
Approche 1 : Détection de Cycle avec un Set
La clé pour résoudre ce problème est de détecter un cycle. Si un nombre se répète au cours du processus, cela signifie que nous sommes entrés dans une boucle infinie. Un Set est idéal pour suivre les nombres déjà rencontrés.
/**
* @param {number} n
* @return {boolean}
*/
function estNombreHeureuxAvecSet(n) {
const nombresVus = new Set();
// Fonction auxiliaire pour calculer la somme des carrés des chiffres
function calculerSommeCarresChiffres(nombre) {
let somme = 0;
while (nombre > 0) {
const chiffre = nombre % 10;
somme += chiffre * chiffre;
nombre = Math.floor(nombre / 10);
}
return somme;
}
// Continuer tant que le nombre n'est pas 1 et qu'il n'a pas été vu auparavant
while (n !== 1 && !nombresVus.has(n)) {
nombresVus.add(n);
n = calculerSommeCarresChiffres(n);
}
// Le nombre est heureux si le processus se termine par 1
return n === 1;
}
// Exemple d'utilisation
// console.log(estNombreHeureuxAvecSet(19)); // true
// console.log(estNombreHeureuxAvecSet(2)); // false
Approche 2 : Algorithme de détection de cycle de Floyd (Pointeurs lents et rapides)
Cette approche est inspirée de la détection de cycles dans les listes chaînées. On utilise deux "poineturs" qui avancent à des vitesses différentes. Si le nombre est heureux, les deux pointeurs convergeront vers 1. S'il y a un cycle, ils se rencontreront à l'intérieur du cycle.
/**
* @param {number} n
* @return {boolean}
*/
function estNombreHeureuxAvecPointeurs(n) {
// Fonction auxiliaire pour calculer la somme des carrés des chiffres
function calculerSommeCarres(nombre) {
let somme = 0;
while (nombre > 0) {
const chiffre = nombre % 10;
somme += chiffre * chiffre;
nombre = Math.floor(nombre / 10);
}
return somme;
}
let pointeurLent = n;
let pointeurRapide = calculerSommeCarres(n);
// Les pointeurs se déplacent jusqu'à ce qu'ils se rencontrent ou que le nombre rapide atteigne 1
while (pointeurRapide !== 1 && pointeurLent !== pointeurRapide) {
pointeurLent = calculerSommeCarres(pointeurLent);
pointeurRapide = calculerSommeCarres(calculerSommeCarres(pointeurRapide));
}
// Le nombre est heureux si le pointeur rapide atteint 1
return pointeurRapide === 1;
}
// Exemple d'utilisation
// console.log(estNombreHeureuxAvecPointeurs(19)); // true
// console.log(estNombreHeureuxAvecPointeurs(2)); // false
Problème 4 : Deux Sommes (LeetCode 1)
Étant donné un tableau d'entiers nums et un entier cible, retournez les indices des deux nombres qui, additionnés, donnent la cible.
Approche : Utilisation d'une Map pour stocker les compléments
Ce problème est un cas d'école pour les tables de hachage. L'objectif est de trouver rapidement si un "complément" (cible - nombre_actuel) a déjà été vu. Une Map est parfaite pour cela car elle peut stocker la valeur d'un nombre et son indice.
- Pourquoi une table de hachage ? Nous devons vérifier si un élément particulier a été rencontré précédemment et, si oui, récupérer son indice.
- Pourquoi une
Map? Nous avons besoin de stocker à la fois la valeur de l'élément (comme clé) et son indice (comme valeur).
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
function trouverDeuxSommes(nums, target) {
// Une Map pour stocker chaque nombre que nous rencontrons et son indice.
// Clé: le nombre, Valeur: son indice dans le tableau d'origine.
const complementsVus = new Map();
for (let i = 0; i < nums.length; i++) {
const nombreActuel = nums[i];
const complementRecherche = target - nombreActuel;
// Vérifie si le complément requis est déjà dans notre Map
if (complementsVus.has(complementRecherche)) {
// Si oui, nous avons trouvé la paire. Retourne l'indice du complément et l'indice actuel.
return [complementsVus.get(complementRecherche), i];
}
// Si le complément n'est pas trouvé, ajoute le nombre actuel et son indice à la Map
complementsVus.set(nombreActuel, i);
}
// Si aucune paire n'est trouvée (selon l'énoncé du problème, une solution existe toujours)
return [];
}
// Exemple d'utilisation
// console.log(trouverDeuxSommes([2, 7, 11, 15], 9)); // [0, 1]
// console.log(trouverDeuxSommes([3, 2, 4], 6)); // [1, 2]