Jour 27 Day 27 · mercredi 9 septembre 2026 Wednesday 9 September 2026 CS Intermédiaire

Hashmaps en profondeur Hashmaps in depth

Buckets, collisions, load factor, hash flooding : comprendre ce qui se cache derrière le O(1) — la structure la plus rentable en entretien, du quiz théorique au two-sum. Buckets, collisions, load factor, hash flooding: understand what hides behind the O(1) — the highest-yield data structure in interviews, from theory quizzes to two-sum.

L’essentiel

La table de hachage — dict en Python, Map en JavaScript, HashMap en Java, unordered_map en C++ — associe des clés à des valeurs avec insertion, recherche et suppression en O(1) en moyenne. C’est la structure la plus utilisée en pratique et la plus rentable en entretien : la moitié des exercices « optimisez ce code » se résolvent en remplaçant une recherche linéaire par une hashmap.

Le principe tient en une ligne : une fonction de hachage transforme la clé en un entier, réduit modulo le nombre de cases du tableau interne (les buckets), et cet index donne directement l’emplacement de la donnée. Pas de parcours de toutes les clés : un calcul, un accès tableau.

Mais ce O(1) est en moyenne, pas garanti. Collisions, facteur de charge et redimensionnement font tout l’écart entre la théorie et la réalité — et c’est précisément là-dessus qu’un entretien creuse.

Comment ça marche

Le chemin d’un map.get("cat") :

hash("cat") produit un grand entier (rapide, déterministe) ;
index = hash mod capacité le ramène dans les bornes du tableau interne ;
on lit le bucket à cet index.

hash("cat") = 0x51f2 ─▶ 0x51f2 mod 8 = 2

 [0] ─▶ ∅
 [1] ─▶ ("dog",4) ─▶ ∅
 [2] ─▶ ("cat",3) ─▶ ("act",7) ─▶ ∅
 [3] ─▶ ∅            ▲
 ...                 └── collision : deux clés,
 [7] ─▶ ("zoo",1) ─▶ ∅   même bucket → chaînage

Deux clés distinctes peuvent tomber dans le même bucket : c’est une collision, inévitable — il y a infiniment plus de clés possibles que de buckets (principe des tiroirs). Deux grandes familles de résolution :

	Chaining (chaînage)	Open addressing
Collision	liste (ou arbre) dans le bucket	on sonde une autre case (probing)
Mémoire	pointeurs et allocations en plus	tableau compact, cache-friendly
Load factor	peut dépasser 1	doit rester < 1
Suppression	simple (retirer le maillon)	délicate (tombstones)
Exemples	Java `HashMap`	`dict` Python, `HashMap` Rust

Le load factor (facteur de charge) = nombre d’éléments / nombre de buckets. Plus il monte, plus les collisions s’accumulent et plus les buckets s’allongent. Au-delà d’un seuil (0.75 pour Java, ~0.66 pour CPython), la table redimensionne : elle alloue un tableau plus grand (souvent ×2) et re-hache toutes les entrées — car hash mod capacité change avec la capacité.

💡 O(n) amorti — un resize coûte O(n), mais il est déclenché de plus en plus rarement (après environ n insertions). Réparti sur toutes les insertions, le coût moyen reste O(1) : c’est exactement l’argument du tableau dynamique (ArrayList, vector). Dire « O(1) amorti » plutôt que « O(1) » en entretien, c’est un point bonus immédiat.

Concepts clés à maîtriser

Pire cas O(n) : si toutes les clés atterrissent dans le même bucket (fonction de hachage mauvaise ou adversariale), la hashmap dégénère en liste chaînée. Java 8+ se défend en transformant un bucket trop peuplé (≥ 8 entrées) en arbre rouge-noir : O(log n) au pire.
Hash flooding : un attaquant qui connaît la fonction de hachage peut forger des milliers de clés qui collisionnent toutes → chaque insertion devient O(n) et le serveur qui parse un JSON ou des paramètres HTTP s’effondre (déni de service, CVE-2011-4885 entre autres). Défenses : hachage avec graine aléatoire par processus (SipHash dans Python, Ruby, Rust) et/ou treeification (Java).
Ce qui fait une bonne clé : elle doit être immuable (ou au minimum ne jamais muter tant qu’elle est dans la map), et son égalité et son hash doivent être cohérents : a.equals(b) ⟹ hash(a) == hash(b). En Java, redéfinir equals sans hashCode est le bug classique : deux objets « égaux » finissent dans des buckets différents et get ne retrouve rien.
Objet JS vs Map : l’objet n’accepte que des clés string/symbol (tout le reste est converti en chaîne), hérite de son prototype ({}["toString"] existe !) et est vulnérable à la pollution __proto__ si on y range des clés venant de l’utilisateur. Map : clés de tout type, .size en O(1), ordre d’insertion garanti, meilleures performances en insertions/suppressions intensives. Règle simple : objet = struct à forme fixe, Map = vrai dictionnaire dynamique.
Ordre d’itération : jamais garanti par le contrat général (Java HashMap : ordre arbitraire, qui peut changer après un resize). Python ≥ 3.7 et Map JS préservent l’ordre d’insertion — mais ne jamais supposer un ordre trié : pour ça, il faut un arbre (TreeMap).

⚠️ La clé mutée est une clé perdue — insérez un objet mutable comme clé, puis modifiez un champ qui participe au hash : la valeur est toujours dans la map, mais dans le mauvais bucket. get re-hache la clé, cherche dans le nouveau bucket, ne trouve rien. C’est pour ça que Python interdit les list comme clés (unhashable) et n’accepte que des types immuables comme le tuple.

En entretien

« Pourquoi une hashmap est-elle en O(1) en moyenne, et pas toujours ? » — Le hash donne directement l’index du bucket : un calcul plus un accès tableau, indépendant de n. « En moyenne » parce que les collisions existent : avec une bonne fonction de hachage et un load factor contrôlé, chaque bucket contient O(1) éléments ; avec une mauvaise fonction (ou face à un adversaire), tout tombe dans le même bucket et on dégénère en O(n).

« Chaining ou open addressing : lequel choisir ? » — Chaining : plus simple, tolère un load factor > 1, mais pointeurs et sauts mémoire. Open addressing : tout dans un tableau contigu, excellent pour le cache CPU, mais suppression délicate (tombstones) et très sensible au load factor. Les implémentations modernes orientées performance (dict Python, HashMap Rust) choisissent l’open addressing pour la localité mémoire.

« Que se passe-t-il quand la table se remplit ? » — Le load factor dépasse son seuil (~0.75) : allocation d’un tableau ×2 et re-hachage de toutes les entrées. O(n) ponctuel, O(1) amorti. Bonus : si on connaît la taille finale à l’avance, pré-dimensionner (new HashMap<>(1024)) évite tous les resizes intermédiaires.

« Object ou Map en JavaScript ? » — Clés dynamiques ou non-string, besoin de .size, insertions/suppressions fréquentes, données venant de l’utilisateur → Map. Forme fixe connue à l’avance (config, DTO) → objet. Mentionner la pollution de prototype : ranger de l’input utilisateur dans un objet nu est un risque, Map (ou Object.create(null)) l’élimine.

« Quel contrat pour une clé de HashMap en Java ? » — equals et hashCode redéfinis ensemble et cohérents (égaux ⟹ même hash), stables tant que l’objet est dans la map — donc clé immuable de préférence (String, Integer, record).

L’exercice le plus classique, two-sum, illustre le réflexe hashmap :

// Naïf : O(n²) — on teste toutes les paires
function twoSumNaive(nums, target) {
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      if (nums[i] + nums[j] === target) return [i, j];
  return null;
}

// Hashmap : O(n) — un seul passage
function twoSum(nums, target) {
  const seen = new Map();              // valeur → index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];     // le complément cherché
    if (seen.has(need))                // déjà vu ? O(1)
      return [seen.get(need), i];
    seen.set(nums[i], i);              // mémoriser APRÈS le test
  }                                    // (cas need === nums[i])
  return null;
}

🎤 En entretien — « implémente un compteur de fréquences » (mots d’un texte, caractères d’une chaîne) est l’échauffement le plus fréquent : une map élément → compte, un seul passage, map.set(x, (map.get(x) ?? 0) + 1). Sachez l’écrire les yeux fermés dans votre langage, puis enchaînez sur les variantes : top-k (compteur + tri ou heap), anagrammes (comparer deux compteurs), déduplication (un Set, qui n’est qu’une hashmap sans valeurs).

Pièges & idées reçues

« O(1) garanti » — non : O(1) en moyenne et amorti. Pire cas O(n) (collisions massives), et une insertion isolée peut coûter O(n) (resize). Pour du temps réel strict, c’est un vrai sujet.
Supposer un ordre d’itération — code qui marche en Python (ordre d’insertion) et casse en Java (ordre arbitraire, instable après resize). Besoin d’un ordre trié → TreeMap ou arbre équilibré, en acceptant le O(log n).
Clés flottantes — NaN !== NaN, arrondis binaires (0.1 + 0.2 !== 0.3) : hacher des flottants est un piège classique. Préférer des entiers ou des chaînes canoniques.
Ranger de l’input utilisateur dans un objet JS nu — pollution de prototype (__proto__, constructor). Map ou Object.create(null).
Sur-optimiser la capacité initiale d’entrée de jeu — utile quand n est connu à l’avance, mais c’est un détail : d’abord la solution claire, ensuite mentionner l’optimisation.

Pour aller plus loin

MDN — Map, avec le comparatif objet vs Map
Java HashMap (javadoc) : load factor 0.75 et treeification documentés noir sur blanc
CPython — dictobject.c : le commentaire d’en-tête explique l’open addressing du dict Python
SipHash : la fonction de hachage à clé conçue contre le hash flooding
Étape suivante naturelle : les arbres équilibrés (TreeMap, B-tree) — quand l’ordre trié vaut le coût O(log n)

The essentials

The hash table — dict in Python, Map in JavaScript, HashMap in Java, unordered_map in C++ — maps keys to values with insertion, lookup and deletion in O(1) on average. It’s the most used structure in practice and the highest-yield one in interviews: half of all “optimize this code” exercises are solved by replacing a linear search with a hashmap.

The principle fits in one line: a hash function turns the key into an integer, reduced modulo the number of slots in the internal array (the buckets), and that index points directly to the data. No scanning of all keys: one computation, one array access.

But that O(1) is on average, not guaranteed. Collisions, load factor and resizing make all the difference between theory and reality — and that’s exactly where an interview digs.

How it works

The path of a map.get("cat"):

hash("cat") produces a large integer (fast, deterministic);
index = hash mod capacity brings it within the bounds of the internal array;
read the bucket at that index.

hash("cat") = 0x51f2 ─▶ 0x51f2 mod 8 = 2

 [0] ─▶ ∅
 [1] ─▶ ("dog",4) ─▶ ∅
 [2] ─▶ ("cat",3) ─▶ ("act",7) ─▶ ∅
 [3] ─▶ ∅            ▲
 ...                 └── collision: two keys,
 [7] ─▶ ("zoo",1) ─▶ ∅   same bucket → chaining

Two distinct keys can land in the same bucket: that’s a collision, and it’s unavoidable — there are infinitely more possible keys than buckets (pigeonhole principle). Two main resolution families:

	Chaining	Open addressing
Collision	list (or tree) inside the bucket	probe another slot (probing)
Memory	extra pointers and allocations	compact array, cache-friendly
Load factor	can exceed 1	must stay < 1
Deletion	simple (unlink the node)	tricky (tombstones)
Examples	Java `HashMap`	Python `dict`, Rust `HashMap`

The load factor = number of elements / number of buckets. As it rises, collisions pile up and buckets grow longer. Past a threshold (0.75 for Java, ~0.66 for CPython), the table resizes: it allocates a larger array (usually ×2) and rehashes every entry — because hash mod capacity changes with the capacity.

💡 Amortized O(n) — a resize costs O(n), but it’s triggered less and less often (after roughly n insertions). Spread over all insertions, the average cost stays O(1): it’s exactly the dynamic array argument (ArrayList, vector). Saying “amortized O(1)” instead of “O(1)” in an interview is an instant bonus point.

Key concepts to master

Worst case O(n): if all keys land in the same bucket (bad or adversarial hash function), the hashmap degenerates into a linked list. Java 8+ defends itself by turning an overcrowded bucket (≥ 8 entries) into a red-black tree: O(log n) worst case.
Hash flooding: an attacker who knows the hash function can forge thousands of keys that all collide → every insertion becomes O(n) and the server parsing a JSON body or HTTP parameters collapses (denial of service, CVE-2011-4885 among others). Defenses: hashing with a per-process random seed (SipHash in Python, Ruby, Rust) and/or treeification (Java).
What makes a good key: it must be immutable (or at minimum never mutate while it’s in the map), and its equality and hash must be consistent: a.equals(b) ⟹ hash(a) == hash(b). In Java, overriding equals without hashCode is the classic bug: two “equal” objects end up in different buckets and get finds nothing.
JS object vs Map: the object only accepts string/symbol keys (everything else is coerced to a string), inherits from its prototype ({}["toString"] exists!) and is vulnerable to __proto__ pollution if you store user-provided keys in it. Map: keys of any type, O(1) .size, guaranteed insertion order, better performance under heavy insertion/deletion. Simple rule: object = fixed-shape struct, Map = true dynamic dictionary.
Iteration order: never guaranteed by the general contract (Java HashMap: arbitrary order, which can change after a resize). Python ≥ 3.7 and JS Map preserve insertion order — but never assume a sorted order: for that you need a tree (TreeMap).

⚠️ A mutated key is a lost key — insert a mutable object as a key, then modify a field that participates in the hash: the value is still in the map, but in the wrong bucket. get rehashes the key, looks in the new bucket, finds nothing. That’s why Python forbids list as keys (unhashable) and only accepts immutable types like the tuple.

In an interview

“Why is a hashmap O(1) on average, and not always?” — The hash gives the bucket index directly: one computation plus one array access, independent of n. “On average” because collisions exist: with a good hash function and a controlled load factor, each bucket holds O(1) elements; with a bad function (or against an adversary), everything lands in the same bucket and you degenerate to O(n).

“Chaining or open addressing: which one to pick?” — Chaining: simpler, tolerates a load factor > 1, but extra pointers and memory jumps. Open addressing: everything in one contiguous array, excellent for the CPU cache, but tricky deletion (tombstones) and very sensitive to the load factor. Modern performance-oriented implementations (Python dict, Rust HashMap) pick open addressing for memory locality.

“What happens when the table fills up?” — The load factor crosses its threshold (~0.75): allocate a ×2 array and rehash every entry. Occasional O(n), amortized O(1). Bonus: if the final size is known upfront, pre-sizing (new HashMap<>(1024)) avoids all intermediate resizes.

“Object or Map in JavaScript?” — Dynamic or non-string keys, need for .size, frequent insertions/deletions, user-provided data → Map. Fixed shape known upfront (config, DTO) → object. Mention prototype pollution: storing user input in a bare object is a risk, Map (or Object.create(null)) eliminates it.

“What’s the contract for a HashMap key in Java?” — equals and hashCode overridden together and consistent (equal ⟹ same hash), stable while the object is in the map — hence preferably an immutable key (String, Integer, record).

The most classic exercise, two-sum, illustrates the hashmap reflex:

// Naive: O(n²) — test every pair
function twoSumNaive(nums, target) {
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      if (nums[i] + nums[j] === target) return [i, j];
  return null;
}

// Hashmap: O(n) — a single pass
function twoSum(nums, target) {
  const seen = new Map();              // value → index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];     // the complement we need
    if (seen.has(need))                // seen before? O(1)
      return [seen.get(need), i];
    seen.set(nums[i], i);              // store AFTER the check
  }                                    // (case need === nums[i])
  return null;
}

🎤 In an interview — “implement a frequency counter” (words in a text, characters in a string) is the most common warm-up: a map element → count, one pass, map.set(x, (map.get(x) ?? 0) + 1). Be able to write it with your eyes closed in your language, then chain into the variants: top-k (counter + sort or heap), anagrams (compare two counters), deduplication (a Set, which is just a hashmap without values).

Pitfalls & misconceptions

“Guaranteed O(1)” — no: O(1) on average and amortized. Worst case O(n) (massive collisions), and a single insertion can cost O(n) (resize). For hard real-time, that’s a real concern.
Assuming an iteration order — code that works in Python (insertion order) and breaks in Java (arbitrary order, unstable after a resize). Need sorted order → TreeMap or a balanced tree, accepting the O(log n).
Floating-point keys — NaN !== NaN, binary rounding (0.1 + 0.2 !== 0.3): hashing floats is a classic trap. Prefer integers or canonical strings.
Storing user input in a bare JS object — prototype pollution (__proto__, constructor). Use Map or Object.create(null).
Over-optimizing the initial capacity from the start — useful when n is known upfront, but it’s a detail: clear solution first, mention the optimization second.

Going further

MDN — Map, with the object vs Map comparison
Java HashMap (javadoc): load factor 0.75 and treeification documented in black and white
CPython — dictobject.c: the header comment explains the open addressing of Python’s dict
SipHash: the keyed hash function designed against hash flooding
Natural next step: balanced trees (TreeMap, B-tree) — when sorted order is worth the O(log n) cost

S'entraîner sur ce sujet → Practice this topic →