Cum funcționează un Map în Go?

Map în Go este implementată ca o tabelă hash.

Componentele principale ale structurii map:

• Funcție hash: Mapază cheile la valori hash (numere întregi).
• Array de bucket-uri: Un set de liste sau array-uri unde sunt stocate perechile cheie-valoare. Indicele bucket-ului este determinat de valoarea hash a cheii.
• Gestionarea coliziunilor: Când diferite chei au același hash (coliziune), elementele cu aceste chei sunt stocate în același bucket, de obicei sub formă de listă legată sau bucket de overflow.
• Factor de încărcare: Raportul dintre numărul de elemente și numărul de bucket-uri. Când se depășește un prag, se face un rehashing: se creează un nou array de bucket-uri mai mare și toate elementele din bucket-urile vechi sunt mutate în cele noi.

Structura map în Go este reprezentată de tipul hmap:

 type hmap struct {
    count     int // Numărul de elemente
    flags     uint8 // Flag-uri de stare
    B         uint8 // log_2 al numărului de bucket-uri (numărul de bucket-uri este 2^B)
    noverflow uint16 // Numărul de bucket-uri cu overflow (doar pentru statistici)
    hash0     uint32 // Valoarea inițială a funcției hash

    buckets    unsafe.Pointer // Punter către array-ul de bucket-uri (principal și overflow)
    oldbuckets unsafe.Pointer // Punter către array-ul vechi de bucket-uri în timpul migrației
    nevacuate  uintptr // Indică până la care bucket vechi s-a finalizat migrația

    extra *mapextra // Informații suplimentare (opțional)
}

 type mapextra struct {
    overflow    *[2]*[]*bmap // Pointers către array-uri de bucket-uri de overflow
    oldoverflow *[2]*[]*bmap // Pointers către array-uri vechi de bucket-uri de overflow
    nextOverflow *bmap // Următorul bucket de overflow liber
}

 type bmap struct {
    tophash [8]uint8 // Top hash (bitii superiori ai hash-ului) pentru accelerarea căutării în bucket
    // Urmează cheile, valorile și pointerii către următorul bmap (dacă bucket-ul este plin)
    // Distribuie toate datele pentru hmap.buckets într-un singur bloc malloc
    // vezi ../../runtime/map.go pentru detalii
}

Operații:

• Inserare/Actualizare: Se calculează hash-ul cheii, se determină bucket-ul. Dacă cheia există deja, valoarea se actualizează. Altfel, perechea cheie-valoare se adaugă în bucket. La overflow sau depășirea Load Factor, poate avea loc o rehashare.
• Căutare: Se calculează hash-ul cheii, se determină bucket-ul. Se parcurg elementele din bucket după top-hash, apoi se compară cheile complete. Se returnează valoarea și un flag de existență.
• Ștergere: Se calculează hash-ul cheii, se determină bucket-ul. Elementul este marcat ca șters (dar nu este șters imediat din memorie). Ștergerea are loc în operațiile ulterioare sau în timpul rehash-ului.

Map-ul în Go nu este sincronizat și nu poate fi utilizat în siguranță de mai multe goroutine fără sincronizare externă.