Hashmap : passer de O(n) à O(1)

Un hashmap transforme une recherche répétée en accès instantané : c'est l'outil n°1 pour éliminer un O(n²).

Une fonction de hachage convertit la clé en index de tableau : accès, insertion et suppression en O(1) en moyenne. Un Set est un hashmap sans valeurs (test d'appartenance, détection de doublons).

Two Sum : le cas d'école#

Trouver deux indices dont les valeurs somment à target. La force brute compare toutes les paires (O(n²)). Avec un hashmap, on mémorise ce qu'on a vu et on demande « mon complément existe-t-il déjà ? ».

function twoSum(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>();           // valeur -> index
  for (let i = 0; i < nums.length; i++) {
    const j = seen.get(target - nums[i]);
    if (j !== undefined) return [j, i];
    seen.set(nums[i], i);
  }
  return null;                                      // O(n) temps, O(n) espace
}

Collisions#

Deux clés peuvent tomber sur le même index. On les gère par chaînage (une liste par case) ou adressage ouvert (on cherche la case libre suivante). Bien dimensionné, l'accès reste O(1) en moyenne ; le pire cas (tout en collision) est O(n).

Astuce : dès qu'un énoncé parle de « déjà vu », de doublons, de fréquences ou de « trouve la paire », pensez hashmap. Le compteur de fréquences (Counter en Python, Map<string, number> en TypeScript) est le cas le plus courant.

Pour aller plus loin#

• NeetCode — Arrays & Hashing (playlist) — NeetCode