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).
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.
Un ancien casier se scinde en deux nouveaux. Un bit de plus du hash de chaque clé décide de la destination.
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.
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.
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.
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
rangesur une map viendrait de la graine de hachage (hash0dans 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.
- 28C3 : Effective Denial of Service attacks against web application platforms, la présentation de 2011 qui a révélé le problème
- LWN : Denial of service via hash collisions
- SipHash, la fonction de hash conçue en réponse à ces attaques
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 |
|
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
rangen’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
- Go runtime : src/internal/runtime/maps
- Go 1.23 runtime : src/runtime/map.go
- Faster Go maps with Swiss Tables
- Go 1.24 Release Notes
- golang/go#54766 : use SwissTable for runtime map
- Rust std::collections::HashMap
- OpenJDK HashMap.java
- JEP 180 : Handle Frequent HashMap Collisions with Balanced Trees
- CPython Objects/dictobject.c
- python-dev : More compact dictionaries with faster iteration
- hashbrown, le port Rust de la SwissTable
- Abseil : Swiss Tables design notes
