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.
Ce qui porte la capacité, ce n’est pas la taille d’un bucket
Dans l’ancienne implémentation (hmap, avant Go 1.24), un bucket a toujours 8 cases. Ce qui change, c’est leur nombre : 2^B buckets. Une map grossit quand elle dépasse un seuil basé sur le facteur de charge visé, 6,5 clés par bucket en moyenne (loadFactorNum/Den = 13/2) :
| B | buckets | seuil |
|---|---|---|
| 3 | 8 | 52 |
| 5 | 32 | 208 |
| 6 | 64 | 416 |
| 7 | 128 | 832 |
| 8 | 256 | 1664 |
(Extrait, il manque des valeurs de B.)
Pour 1000 clés, Go choisit B=8 : 256 buckets, environ 3,9 clés par bucket en moyenne. 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.
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.
Grossir sans geler le programme
Faire grossir une map d’un coup, recalculer 1000 hash et tout recopier dans la même écriture, produirait un pic de latence. Go l’évite avec une évacuation incrémentale. hashGrow alloue 2^(B+1) nouveaux buckets, range l’ancien tableau dans h.oldbuckets, et chaque écriture ou suppression suivante évacue un ou deux buckets au passage (nevacuate avance petit à petit). Un ancien bucket se scinde en exactement deux nouveaux, selon un bit de hash supplémentaire : evacuatedX et evacuatedY marquent, case par case, vers quelle moitié chaque entrée est partie.
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 : un seuil plus haut, une croissance bornée
Depuis Go 1.24, les Swiss Tables changent ces règles. Le facteur de charge maximal passe à 7/8 (maxAvgGroupLoad = 7 pour 8 slots), contre 6,5/8 avant. Un delete ne vide pas le slot : il le marque 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.
Le changement le plus visible porte sur la croissance elle-même. Une map Go n’est plus une seule grande table qui double : elle est découpée en plusieurs tables, chacune plafonnée à 1024 slots (896 entrées avec le facteur de charge de 7/8), organisées derrière un directory extensible (globalDepth/localDepth). Sous ce plafond, une table qui atteint son seuil double en place ; au-delà, elle se scinde en deux. Ce choix, arbitré dans rehash (table.go), borne la latence d’un grow à la taille d’une seule table. Et comme pour hmap, rien ne rétrécit une table ou le directory quand la map se vide (map.go garde un // TODO: shrink directory? explicite).
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. 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
}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])
}Attention à un piège d’observation : fmt.Println(m) trie les clés avant de les afficher depuis Go 1.12. Ça masque complètement le phénomène si on teste avec Println au lieu d’un vrai range.
Et ailleurs
Les autres langages font des choix différents. Java HashMap chaîne les collisions et vise un load factor de 0,75 ; un bucket qui dépasse 8 entrées devient un arbre rouge-noir, mais seulement si la table a atteint 64 cases (sinon elle double d’abord). Python utilise de l’adressage ouvert avec un seuil d’occupation aux deux tiers. Rust a porté l’algorithme Swiss Table dans sa std, avec le même principe de groupes et d’octets de contrôle que Go.
À retenir
Le nombre de buckets ou de tables porte la capacité, pas leur taille. La croissance est conçue pour borner le travail fait par une seule insertion, que ce soit par évacuation incrémentale ou par découpage en tables de taille bornée. Et l’ordre de range n’a jamais été un contrat : ne l’utilisez jamais comme un signal, 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 du prochain article.