A partir da versão 1.24 do Go, a implementação do mapa (map) foi completamente redesenhada para utilizar a estrutura de dados Swiss Tables, originada da biblioteca abseil-cpp do Google. Esta mudança oferece melhorias significativas na performance, particularmente no acesso aos dados, devido ao design otimizado para o cache da CPU e possível otimização via instruções SIMD.

Estruturas Fundamentais

A estrutura principal do mapa (runtime/map.go) contém campos para controle de uso, semente de hash, e um ponteiro inteligente para o diretório de tabelas.

// runtime/map.go
type Map struct {
    elementCount uint64
    hashSeed     uintptr
    dirPtr       unsafe.Pointer
    dirLength    int
    depth        uint8
    shift        uint8
    writingFlag  uint8
    hasTombs     bool
    seqNumber    uint64
}

O campo dirPtr opera em dois modos: para mapas pequenos (até 8 elementos), aponta diretamente para um único grupo (Group). Para mapas maiores, aponta para um array de ponteiros para tabelas (table).

O Conceito de Grupo e Byte de Controle

A inovação central está no Group. Cada grupo contém 8 slots para chaves e valores, acompanhados por 8 bytes de controle.

type Group struct {
    controls [8]controlByte
    keys     [8]KeyType
    values   [8]ValueType
}

type controlByte uint8

const (
    emptySlot   controlByte = 0b10000000 // 128
    deletedSlot controlByte = 0b11111110 // 254
    // bit 7=0 indica ocupado; bits 0-6 contêm os 7 bits inferiores do hash (H2).
)

O byte de controle é dividido: seu bit mais significativo indica se o slot está ocupado (0), livre (1) ou é uma lápide (tombstone, valor 0xFE). Os 7 bits inferiores armazenam H2, os 7 bits menos significativos do hash da chave.

Cálculo do Índice e Sequência de Sondagem

O hash completo de 64 bits é dividido. H1 = hash >> 7 (57 bits supeirores) é usado para calcular a sequência de sondagem. H2 = hash & 0x7F (7 bits inferiores) é armazenado no byte de controle para uma filtragem rápida.

func computeDirectoryIndex(hash uintptr, shift uint8, dirLen int) int {
    if dirLen == 1 {
        return 0
    }
    return int(hash >> (shift & 63))
}

func makeProbeSequence(hashHigh uint64, lengthMask uint64) (offset uint64, mask uint64) {
    return hashHigh & lengthMask, lengthMask
}

A sequência de sondagem avança linearmente pelos grupos, utilizando uma operação AND com a máscara (lengthMask) para indexamento circular eficiente, em vez de uma operação de módulo mais cara.

Operações Principais

Consulta (Get)

A busca por uma chave começa localizando o grupo inicial via H1. Dantro do grupo, os bytes de controle são comparados em paralelo com H2 usando operações bitwise rápidas. Se uma correspondência for encontrada, as chaves são comparadas.

func (t *table) lookup(hash uint64, key KeyType) (*ValueType, bool) {
    h2Target := controlByte(hash & 0x7F)
    offset, mask := makeProbeSequence(hash>>7, t.groupMask)

    for {
        g := &t.groups[offset]
        matchMask := g.controls.matchH2(h2Target)

        for matchMask != 0 {
            slotIdx := findFirstSetBit(matchMask)
            if keysEqual(key, g.keys[slotIdx]) {
                return &g.values[slotIdx], true
            }
            matchMask = clearFirstSetBit(matchMask)
        }

        if g.controls.containsEmpty() {
            return nil, false // Encerra a sondagem se encontrar um slot vazio.
        }
        offset = (offset + 1) & mask
    }
}

Inserção (Put)

A inserção procura por uma chave existente para atualizar, ou por um slot livre (vazio ou lápide) para inserir. Se a tabela atingir sua capacidade máxima (fator de carga de 87.5%), uma limpeza de lápides ou expansão é acionada.

func (t *table) insert(hash uint64, key KeyType, value ValueType) *ValueType {
    // ... busca por chave existente ou slot livre (lógica similar a lookup, mas registrando o primeiro slot 'deleted' encontrado) ...
    
    if growthLeft == 0 {
        if !t.pruneTombstones() {
            t.grow() // Expande a tabela se a limpeza não for suficiente.
            return t.insert(hash, key, value) // Tenta novamente.
        }
    }

    // Escreve no slot (reutilizando uma lápide se necessário e atualizando contadores).
    // Define o byte de controle para H2.
    // Copia chave e valor.
    // Retorna ponteiro para o valor.
}

Remoção (Delete)

Ao remover, se o gruppo do slot alvo ainda tiver slots livres, o slot é marcado como vazio. Se o grupo estiver cheio, o slot é marcado como uma lápide (deletedSlot) para preservar a integridade das sondagens de outras chaves que possam ter colidido.

Expansão e Manutenção

A expansão ocorre quando o fator de carga excede 87.5%. A estratégia pode ser um grow (aumentar a capacidade de uma tabela existente) ou um split (dividir uma tabela em duas, potencialmente expandindo o diretório). Isso garante que a operação de rehash seja incremental e localizada.

Considerações de Performance

• Alocar Capacidade Inicial: Use make(map[K]V, hint) para reduzir realocações.
• Acesso Concorrente: Maps em Go não são seguros para uso concorrente. Utilize sync.RWMutex ou sync.Map.
• Iteração e Modificação: Evite modificar o mapa durante iteração com range; colete as chaves primeiro se precisar deletar.
• Tipo da Chave: Chaves menores (ex.: int) e comparáveis de forma rápida geralmente oferecem melhor performance.