Come funziona una mappa in Go?

La mappa in Go è implementata come una tabella hash.

I componenti principali della struttura map:

• Funzione hash: Mappa le chiavi ai valori hash (numeri interi).
• Array di bucket: Un insieme di liste o array dove vengono memorizzate le coppie chiave-valore. L'indice del bucket è determinato dal valore hash della chiave.
• Gestione delle collisioni: Quando diverse chiavi hanno lo stesso hash (collisione), gli elementi con queste chiavi vengono memorizzati nello stesso bucket, di solito sotto forma di lista collegata o in un bucket di overflow.
• Fattore di carico: Rapporto tra il numero di elementi e il numero di bucket. Quando si supera una soglia, viene eseguito un rehashing: viene creato un nuovo array di bucket più grande e tutti gli elementi dei bucket vecchi vengono spostati in quelli nuovi.

La struttura map in Go è rappresentata dal tipo hmap:

 type hmap struct {
    count     int // Numero di elementi
    flags     uint8 // Flags di stato
    B         uint8 // log_2 del numero di bucket (numero di bucket è 2^B)
    noverflow uint16 // Numero di bucket con overflow (solo per statistiche)
    hash0     uint32 // Valore iniziale della funzione hash

    buckets    unsafe.Pointer // Puntatore all'array di bucket (principale e overflow)
    oldbuckets unsafe.Pointer // Puntatore all'array di bucket vecchio durante la migrazione
    nevacuate  uintptr // Indica fino a quale bucket vecchio è stata completata la migrazione

    extra *mapextra // Informazioni aggiuntive (opzionale)
}

 type mapextra struct {
    overflow    *[2]*[]*bmap // Puntatori ad array di bucket di overflow
    oldoverflow *[2]*[]*bmap // Puntatori ad array di bucket di overflow vecchi
    nextOverflow *bmap // Il prossimo bucket di overflow libero
}

 type bmap struct {
    tophash [8]uint8 // Top hash (bit superiori dell'hash) per accelerare la ricerca nel bucket
    // Segue chiavi, valori e puntatori al prossimo bmap (se il bucket è saturo)
    // Disporre tutti i dati per hmap.buckets in un singolo blocco malloc
    // vedi ../../runtime/map.go per i dettagli
}

Operazioni:

• Inserimento/Aggiornamento: Si calcola l'hash della chiave, si determina il bucket. Se la chiave esiste già, il valore viene aggiornato. Altrimenti, la coppia chiave-valore viene aggiunta al bucket. In caso di overflow o superamento del Load Factor, può avvenire un rehashing.
• Ricerca: Si calcola l'hash della chiave, si determina il bucket. Si percorrono gli elementi nel bucket per top-hash, poi si confrontano le chiavi complete. Viene restituito il valore e un flag di presenza.
• Eliminazione: Si calcola l'hash della chiave, si determina il bucket. L'elemento viene contrassegnato come eliminato (ma non rimosso immediatamente dalla memoria). L'eliminazione avviene in operazioni successive o durante il rehashing.

La mappa in Go non è sincronizzata e non può essere usata in modo sicuro da più goroutine senza sincronizzazione esterna.