Como funciona o Map em Go?

Map em Go é implementada como uma tabela de dispersão.

Os componentes principais da estrutura map:

• Função de hash: Mapeia as chaves para valores de hash (números inteiros).
• Array de buckets: Conjunto de listas ou arrays onde são armazenados pares chave-valor. O índice do bucket é determinado pelo valor de hash da chave.
• Gestão de colisões: Quando diferentes chaves têm o mesmo hash (colisão), os elementos com essas chaves são armazenados no mesmo bucket, geralmente em forma de lista ligada ou em um bucket de overflow.
• Fator de carga: Relação entre o número de elementos e o número de buckets. Quando um limiar é ultrapassado, é realizado um rehashing: cria-se um novo array de buckets maior e move-se todos os elementos dos buckets antigos para os novos.

A estrutura map em Go é representada pelo tipo hmap:

 type hmap struct {
    count     int // Número de elementos
    flags     uint8 // Flags de estado
    B         uint8 // log_2 do número de buckets (número de buckets é 2^B)
    noverflow uint16 // Número de buckets com overflow (apenas para estatísticas)
    hash0     uint32 // Valor inicial da função de hash

    buckets    unsafe.Pointer // Ponteriro para o array de buckets (principal e overflow)
    oldbuckets unsafe.Pointer // Ponteriro para o array antigo de buckets durante a migração
    nevacuate  uintptr // Indica até que bucket antigo a migração foi concluída

    extra *mapextra // Informação adicional (opcional)
}

 type mapextra struct {
    overflow    *[2]*[]*bmap // Ponteriros para arrays de buckets de overflow
    oldoverflow *[2]*[]*bmap // Ponteriros para antigos arrays de buckets de overflow
    nextOverflow *bmap // Próximo bucket de overflow livre
}

 type bmap struct {
    tophash [8]uint8 // Top hash (bits superiores do hash) para acelerar a busca no bucket
    // Seguem-se as chaves, valores e ponteiros para o próximo bmap (se o bucket estiver cheio)
    // distribuir todos os dados para hmap.buckets num único bloco malloc
    // ver ../../runtime/map.go para detalhes
}

Operações:

• Inserção/Atualização: Calcula-se o hash da chave, determina-se o bucket. Se a chave já existir, o valor é atualizado. Caso contrário, o par chave-valor é adicionado ao bucket. Em caso de overflow ou superação do Load Factor, pode ocorrer um rehashing.
• Busca: Calcula-se o hash da chave, determina-se o bucket. Percorrem-se os elementos no bucket pelo top-hash, depois compara-se as chaves completas. Retorna-se o valor e um indicador de existência.
• Remoção: Calcula-se o hash da chave, determina-se o bucket. O elemento é marcado como removido (mas não é removido imediatamente da memória). A remoção ocorre em operações posteriores ou durante o rehashing.

O mapa em Go não é sincronizado e não pode ser usado com segurança por múltiplas goroutines sem sincronização externa.