Jak je Map v Go uspořádán?

Map v Go je implementován jako hash tabulka.

Hlavní komponenty struktury map:

• Hash funkce: Mapuje klíče na hash hodnoty (celá čísla).
• Pole bucketů: Sada seznamů nebo polí, kde jsou uloženy páry klíč-hodnota. Index bucketu je určen hash hodnotou klíče.
• Zpracování kolizí: Při shodě hashů pro různé klíče (kolize) jsou prvky s těmito klíči uloženy v jednom bucketu, obvykle ve spojovaném seznamu nebo přetečení do sousedního bucketu.
• Nákladový faktor: Poměr počtu prvků k počtu bucketů. Při překročení určitého prahu dochází k rehashování – vytvoření nového, většího pole bucketů a přesunutí všech prvků ze starých bucketů do nových.

Struktura map v Go je reprezentována typem hmap:

type hmap struct {
    count     int // Počet prvků
    flags     uint8 // Stavové vlajky
    B         uint8 // log_2 počtu bucketů (počet bucketů je 2^B)
    noverflow uint16 // Počet přetečených bucketů (pouze pro statistiku)
    hash0     uint32 // Počáteční hodnota hash funkce

    buckets    unsafe.Pointer // ukazatel na pole bucketů (hlavní a přetečené)
    oldbuckets unsafe.Pointer // ukazatel na staré pole bucketů během migrace
    nevacuate  uintptr // Označuje, do kterého starého bucketu byla migrace dokončena

    extra *mapextra // Další informace (volitelné)
}

type mapextra struct {
    overflow    *[2]*[]*bmap // Ukazatele na pole přetečených bucketů
    oldoverflow *[2]*[]*bmap // Ukazatele na stará pole přetečených bucketů
    nextOverflow *bmap // Následující volný přetečený bucket
}

type bmap struct {
    tophash [8]uint8 // Top hash (horní bity hashe) pro urychlení hledání v bucketu
    // Následují klíče, hodnoty a ukazatel na další bmap (pokud je bucket přetečen)
    // rozložení všech dat pro hmap.buckets v jednom malloc bloku
    // viz ../../runtime/map.go pro detaily
}