Comment fonctionne une Map en Go?

Map en Go est implémenté comme une table de hachage.

Les composants principaux de la structure map:

• Fonction de hachage: Mappe les clés à des valeurs de hachage (nombres entiers).
• Tableau de buckets: Ensemble de listes ou tableaux où sont stockés les paires clé-valeur. L'indice du bucket est déterminé par la valeur de hachage de la clé.
• Gestion des collisions: Lorsqu'il y a collision (même hash pour différentes clés), les éléments avec ces clés sont stockés dans le même bucket, généralement sous forme de liste chaînée ou de bucket de débordement.
• Facteur de charge: Rapport entre le nombre d'éléments et le nombre de buckets. Lorsqu'un seuil est dépassé, un rehashing est effectué : création d'un nouveau tableau de buckets plus grand et déplacement de tous les éléments des anciens buckets vers les nouveaux.

La structure map en Go est représentée par le type hmap:

 type hmap struct {
    count     int // Nombre d'éléments
    flags     uint8 // Flags d'état
    B         uint8 // log_2 du nombre de buckets (nombre de buckets est 2^B)
    noverflow uint16 // Nombre de buckets avec débordement (pour statistiques uniquement)
    hash0     uint32 // Valeur initiale de la fonction de hachage

    buckets    unsafe.Pointer // Pointeur vers le tableau de buckets (principal et débordements)
    oldbuckets unsafe.Pointer // Pointeur vers l'ancien tableau de buckets lors de la migration
    nevacuate  uintptr // Indique jusqu'à quel bucket ancien la migration est terminée

    extra *mapextra // Informations supplémentaires (optionnel)
}

 type mapextra struct {
    overflow    *[2]*[]*bmap // Pointeurs vers des tableaux de buckets de débordement
    oldoverflow *[2]*[]*bmap // Pointeurs vers d'anciens tableaux de buckets de débordement
    nextOverflow *bmap // Bucket de débordement libre suivant
}

 type bmap struct {
    tophash [8]uint8 // Top hash (bits supérieurs du hash) pour accélérer la recherche dans le bucket
    // Ensuite, clés, valeurs et pointeurs vers le prochain bmap (si le bucket est débordé)
    // répartir toutes les données pour hmap.buckets dans un seul bloc malloc
    // voir ../../runtime/map.go pour les détails
}

Opérations:

• Insertion/Mise à jour: Calcul du hash de la clé, détermination du bucket. Si la clé existe déjà, la valeur est mise à jour. Sinon, la paire clé-valeur est ajoutée au bucket. En cas de débordement ou de dépassement du Load Factor, un rehashing peut se produire.
• Recherche: Calcul du hash de la clé, détermination du bucket. Parcours des éléments dans le bucket par top-hash, puis comparaison des clés complètes. Retourne la valeur et un indicateur de présence.
• Suppression: Calcul du hash de la clé, détermination du bucket. L'élément est marqué comme supprimé (mais n'est pas immédiatement supprimé de la mémoire). La suppression se fait lors d'opérations ultérieures ou lors du rehashing.

La map en Go n'est pas synchronisée et ne peut pas être utilisée en toute sécurité par plusieurs goroutines sans synchronisation externe.