Dans le premier article de cette série, on a vu qu’une map Go range ses entrées par groupes de 8.

Question logique : comment une map de 1000 éléments tient dans des cases de 8 ? C’est de l’overflow ? Non. Et la réponse dit beaucoup de la façon dont Go fait grossir une map sans bloquer le programme dessus.

💡 Tout le code de la série est sur github.

Une map qui grossit, c’est un déménagement

Un bucket, c’est un casier de 8 places.

Pour 1000 clés, Go ne prend pas un gros casier : il en aligne 256 (2^8), soit environ 4 clés par casier.

Quand la moyenne dépasse 6,5 clés par casier, il en ouvre deux fois plus et déménage tout le monde.

C’est bien la moyenne qui compte : un casier plein ne déclenche rien, il reçoit simplement un casier de débordement chaîné (overflow bucket).

Le nombre de casiers double : 4 casiers presque pleins deviennent 8 casiers à moitié remplis Avant B = 2 7 / 8 7 / 8 7 / 8 7 / 8 moyenne de 7 > 6,5 (28 clés > seuil de 26) : il faut grossir Après B = 3 8 casiers, environ 3,5 clés chacun
Ici, les 4 casiers contiennent 7 clés en moyenne, au-dessus de 6,5 : leur nombre double. La taille d'un casier, elle, ne change jamais.

Déménager 1000 clés d’un coup ferait freezer le programme.

Go le fait donc au fil des écritures : chaque m[k] = v déménage un ou deux casiers au passage, et les lectures vont chercher dans le bon tableau selon l’avancement.

Pendant la croissance, l'ancien tableau se vide casier par casier vers le nouveau tableau, à chaque écriture Ancien oldbuckets déménagé déménagé en cours à faire chaque écriture déménage 1 ou 2 casiers de plus Nouveau buckets le nouveau tableau se remplit au fil des déménagements
Le programme n'attend jamais la fin : l'ancien et le nouveau tableau coexistent le temps du déménagement.

Un ancien casier se scinde en deux nouveaux. Un bit de plus du hash de chaque clé décide de la destination.

Un ancien casier se scinde en deux nouveaux casiers selon un bit supplémentaire du hash : le casier 2 donne les casiers 2 et 6 ancien casier 2 casier 2 bit de hash = 0 casier 6 bit de hash = 1
Les clés d'un même casier se répartissent entre deux casiers : l'ancien numéro, et l'ancien numéro plus le nombre d'anciens casiers.
Le tableau : seuils de croissance par valeur de B

B est l’exposant du nombre de casiers : la map en compte 2^B. Passer de B à B+1, c’est doubler les casiers. La map grossit quand elle dépasse le facteur de charge visé, 6,5 clés par casier en moyenne (loadFactorNum/Den = 13/2), soit 6,5 × 2^B clés :

B buckets seuil
3 8 52
5 32 208
6 64 416
7 128 832
8 256 1664

Pour 1000 clés, Go choisit B=8 : 256 buckets, environ 3,9 clés par bucket.
Le hash ne distribue pas les clés de façon parfaitement uniforme (loi de Poisson), donc quelques buckets débordent dans un overflow bucket chaîné.
Ce sont des cas isolés sur 256 buckets, pas une chaîne de 125 maillons.

Sous le capot : hashGrow et l'évacuation

Dans l’ancienne implémentation (hmap, Go < 1.24), un bucket a toujours 8 cases. hashGrow alloue 2^(B+1) nouveaux buckets et range l’ancien tableau dans h.oldbuckets. Chaque écriture ou suppression suivante évacue un ou deux buckets au passage (nevacuate avance petit à petit). evacuatedX et evacuatedY marquent, case par case, vers quelle moitié chaque entrée est partie.

Le nombre de buckets n’est pas exposé par l’API, mais le coût de ces croissances successives se mesure en allocations :

growing := testing.AllocsPerRun(50, func() {
	m := make(map[int]int)
	insertNKeys(m, 1000)
})

preSized := testing.AllocsPerRun(50, func() {
	m := make(map[int]int, 1000)
	insertNKeys(m, 1000)
})

Sur ma machine, avec Go 1.27.1 (Swiss Tables), 20 allocations sans taille initiale contre 5 avec make(map[int]int, 1000).

📝 Quand on connaît la taille à l’avance, on la donne.

Ce que la croissance laisse derrière elle

Il existe un second déclencheur de croissance, indépendant du nombre de clés : tooManyOverflowBuckets.

Après beaucoup d’insertions et de suppressions, une map peut accumuler des overflow buckets même sans grossir en nombre de clés. Go déclenche alors un sameSizeGrow : même B, mais réécriture complète pour compacter.

Un effet de bord à connaître, et qui vaut pour les deux implémentations : aucune des deux ne rend sa mémoire sur delete.
Côté hmap, delete ne réduit jamais B. Si une map a grossi pour tenir un pic puis s’est vidée, elle garde ses buckets.

💡 Le seul remède est d’en recréer une neuve et d’y recopier ce qu’il reste.

Swiss Tables : des rayons plutôt qu’un entrepôt

Depuis Go 1.24, les Swiss Tables changent les règles. Une map n’est plus un seul grand tableau qui double, mais un ensemble de rayons (des tables), chacun plafonné à 1024 slots. Un annuaire (le directory) dit à quel rayon appartient chaque clé, d’après les premiers bits de son hash.

Un annuaire de 4 entrées pointe vers 3 rayons : les entrées 00 et 01 partagent le rayon A Annuaire directory 00 01 10 11 Rayons tables rayon A rayon B rayon C 00 et 01 partagent le rayon A : plusieurs entrées peuvent viser la même table
La clé est routée vers un rayon grâce aux premiers bits de son hash, lus dans l'annuaire.

Quand un rayon est plein, lui seul grossit : sous 1024 slots il double sur place, au-delà il se scinde en deux. Le reste de la map ne bouge pas. La latence d’un grow dépend donc de la taille d’un rayon, jamais de celle de la map.

Un rayon plein à 1024 slots se scinde en deux rayons, les autres rayons ne bougent pas Avant A · 896 / 1024 B · 400 / 1024 C · 150 / 1024 A atteint 7/8 : il se scinde Après A1 · 448 A2 · 448 B · 400 / 1024 C · 150 / 1024 B et C n'ont pas bougé
Un rayon à 1024 slots se scinde en deux. Sous ce plafond, il aurait simplement doublé sur place.

Les rayons se remplissent aussi davantage : le facteur de charge maximal passe à 7/8 (maxAvgGroupLoad = 7 pour 8 slots), contre 6,5/8 avant. Et comme pour hmap, rien ne rétrécit quand la map se vide.

Les tombstones : ce que devient un delete

Un delete ne vide pas le slot : il le marque comme supprimé (ctrlDeleted = 0b11111110), ce que le runtime appelle un tombstone.

Un groupe de 8 slots où deux slots supprimés sont marqués par un tombstone au lieu d'être vidés Un groupe de 8 slots clé clé ✗ clé ✗ clé vide vide tombstone tombstone delete marque le slot, il ne le vide pas
Les slots supprimés restent occupés tant que le runtime ne les a pas récupérés.

Quand used + tombstones dépasse 7/8 de la capacité, le runtime tente d’abord de récupérer ces slots marqués supprimés (s’ils dépassent 10 % de la capacité), et ne rehash que si ça ne suffit pas.

Sous le capot : directory et tables

L’annuaire est un directory extensible, indexé par globalDepth (le nombre de bits de hash qu’il lit) ; chaque table garde son propre localDepth. Un rayon plafonné à 1024 slots contient au plus 896 entrées avec le facteur de charge de 7/8. Le choix entre doubler sur place et se scinder est arbitré dans rehash dans table.go. Rien ne rétrécit une table ou le directory quand la map se vide : map.go garde un // TODO: shrink directory? explicite.

Pour voir ce mécanisme en petit, le dépôt d’exemples en propose une version pédagogique : table.go (une table qui double sur place jusqu’à 1024 slots) et map.go (l’annuaire et la scission d’une table pleine).

Pour comparer les deux implémentations, le dépôt d’exemples fournit BenchmarkInsert1000 et un README qui explique comment le lancer avec Go 1.23 et une version récente (ou GOEXPERIMENT=noswissmap sur Go 1.24 et 1.25).

L’ordre d’itération n’a jamais rien eu à voir avec le hash

Idée reçue tenace :

l’ordre aléatoire de range sur une map viendrait de la graine de hachage (hash0 dans l’ancienne implémentation).

👉 C’est faux 🙅‍♂️.

La graine protège contre le hash flooding, un abus qui forcerait des collisions volontaires pour dégrader les performances.

Le hash flooding, c'est quoi ?

Une map reste rapide tant que les clés se répartissent bien entre les casiers. Si un attaquant connaît la fonction de hash, il peut fabriquer des milliers de clés qui tombent toutes dans le même casier : chaque insertion doit alors parcourir tout ce qui s'y trouve, et la map passe d'un coût constant à un coût proportionnel au nombre de clés.

👉 Quelques requêtes bien choisies, avec des noms de paramètres ou des clés JSON, suffisent à saturer un CPU.

👉 La parade consiste à rendre le hash imprévisible.
Une graine tirée au hasard à la création de chaque map (hash0) entre dans le calcul, donc l'attaquant ne peut pas savoir quelles clés vont entrer en collision.

L’ordre d’itération, lui, vient d’un tirage indépendant.
Chaque itérateur choisit un point de départ aléatoire (startBucket/offset côté hmap, entryOffset/dirOffset côté Swiss Tables) à chaque nouveau range.

Deux boucles successives sur la même map, avec le même contenu, peuvent donner deux ordres différents.

for k := range m {
    fmt.Println(k) // l'ordre peut différer à chaque exécution de la boucle
}
Obtenir un ordre stable

Si un ordre stable est nécessaire, il faut le construire soi-même :

for _, k := range slices.Sorted(maps.Keys(m)) { // Go 1.23+
    fmt.Println(k, m[k])
}
Piège : observer l'ordre avec Println

⚠️ Attention à un piège si vous voulez observer le phénomène : n’affichez pas la map directement.

m := map[string]int{"a": 1, "b": 2, "c": 3}
fmt.Println(m) // toujours map[a:1 b:2 c:3]

Ce résultat identique à chaque exécution ne prouve rien car, depuis Go 1.12, fmt trie les clés avant d’afficher une map, pour que les sorties des tests et des logs soient reproductibles.

Seul un vrai range montre l’ordre aléatoire.

Et ailleurs

Les autres langages font des choix différents.

Langage Collisions Croissance
Java HashMap (JEP 180) chaînage
  • load factor de 0,75 ;
  • un casier trop chargé (plus de 8 entrées) devient un arbre, plus rapide à parcourir ; si la table est encore petite, Java la double d’abord
Python dict (dict compact) adressage ouvert à deux tiers d’occupation
Rust HashMap (hashbrown) Swiss Table, groupes et octets de contrôle comme Go même algorithme que Go 1.24+

À retenir

  • La capacité d’une map vient du nombre de casiers (ou de rayons), pas de leur taille : un casier fait toujours 8 slots.
  • Go ne bloque jamais le programme pour agrandir une map : le déménagement se fait par petits morceaux.
  • L’ordre de range n’a jamais été garanti : ne vous y fiez pas, même par accident.

Reste la question qui suit naturellement : que se passe-t-il si deux goroutines écrivent dans la même map en même temps ? C’est le sujet d’un prochain article.


📚 Liens