Présentation

Depuis Go 1.24, le runtime remplace l’ancien algorithme de stockage des maps par une implémentation inspirée des Swiss Tables. Cette refonte conserve le type de haut niveau map[string]int tout en modifiant la représentation interne. Chaque variable map pointe vers une structure 

type Map struct {
    used   uint64
    seed   uintptr
    dirPtr unsafe.Pointer
    dirLen int
    ...
}
où used indique le nombre d’entrées et seed fournit un sel aléatoire unique à chaque instance, garantissant une distribution de hachage différente entre deux maps contenant les mêmes clés.

Structure interne

Le stockage s’organise en « groupes » de 8 paires clé‑valeur. Un groupe minimal ressemble à :

type group struct {
    ctrl  uint64
    slots [8]struct {
        key  Key
        elem Elem
    }
}

Le champ ctrl regroupe les huit octets de contrôle, un par slot. Chaque octet encode le fragment de hachage H2 (7 bits) et un indicateur de statut (bit le plus significatif). Les valeurs spéciales sont : 10000000 pour une case vide et 11111110 pour une tombstone (case supprimée). Cette représentation compacte permet de déterminer, sans accéder aux clés complètes, si une case est occupée, vide ou supprimée.

Mécanisme de hachage et recherche

Lorsqu’une clé est insérée, le runtime calcule un hash de 64 bits à partir du seed. Les 57 bits supérieurs constituent H1, utilisés pour choisir le groupe de départ. Les 7 bits inférieurs forment H2, stockés dans le byte de contrôle correspondant. Par exemple, la clé "cow" produit H2=42, soit le byte 00101010. En insertion, le runtime compare simultanément H2 à tous les octets de contrôle du groupe grâce à une instruction SIMD : un registre de 64 bits est comparé à la valeur 42, générant un bitmap où chaque bit indique une correspondance possible. Les slots candidats sont ensuite vérifiés par comparaison d’égalité complète des clés.

Performances et limites

Cette approche réduit le nombre d’accès mémoire lors de la recherche : un seul chargement du mot de contrôle de 64 bits suffit à éliminer 6 slots sur 8. L’utilisation du SIMD accélère les cas courants où le groupe reste petit (≤ 8 entrées). En cas de croissance, le tableau de groupes (dirPtr) s’élargit et dirLen indique le nombre de groupes supplémentaires, conservant la même logique de contrôle. Toutefois, la taille fixe de 8 slots par groupe impose un coût de réallocation lorsqu’une map dépasse la capacité d’un groupe, entraînant une copie potentiellement coûteuse. De plus, le mécanisme de tombstones peut entraîner un remplissage progressif du tableau si les suppressions sont fréquentes, ce qui nécessite un déclenchement de « rehash » pour restaurer la densité optimale.