Ինչպես է աշխատում Map-ը Go-ում?

Map-ը Go-ում իրականացվում է որպես հեշ-տախտակ:

Հիմնական բաղադրիչները map կառուցվածքի:

• Հեշ-գործառույթ: Կառուցում է բանալիները հեշ արժեքների (լուծարանական թվեր):
• Բաքետների զանգված: Կազմված է ցանկերի կամ զանգվածների, որտեղ պահվում են բանալիներ-արժեք զույգերը: Բաքետի ինդեքսը որոշվում է բանալու հեշ արժեքով:
• Կոլիզիաների մշակումը: Երբ տարբեր բանալիների համար հեշերը համընկնում են (կոլիզիա), այդ տարրերը պահվում են մեկ բաքետում, սովորաբար կապված ցանկի կամ լրացուցիչ բաքի միջոցով:
• Բեռնվածության գործակից: Բանալի տարրերի և բաքետների քանակի հարաբերակցություն: Երբ այն գերազանցում է որոշ սահման, կատարվում է վերահեշավորում՝ նոր, մեծ զանգվածի ստեղծում և տարրերի տեղափոխում հին բաքետներից նորերը:

map կառուցվածքը Go-ում ներկայացված է hmap տիպով:

type hmap struct {
    count     int // տարրերի քանակը
    flags     uint8 // վիճակի նշաններ
    B         uint8 // log_2 բաքետների քանակի (2^B)
    noverflow uint16 // լրացուցիչ բաքետների քանակը (միայն վիճակագրության համար)
    hash0     uint32 // սկզբնական հեշ արժեքը

    buckets    unsafe.Pointer // ցուցիչ բաքետների զանգվածին
    oldbuckets unsafe.Pointer // ցուցիչ հին բաքետների զանգվածին միգրացիայի ժամանակ
    nevacuate  uintptr // նշում է, թե որ հին բաքետում ավարտվել է միգրացիան

    extra *mapextra // լրացուցիչ տեղեկություններ
}

type mapextra struct {
    overflow    *[2]*[]*bmap // ցուցիչներ լրացուցիչ բաքետների զանգվածների
    oldoverflow *[2]*[]*bmap // ցուցիչներ հին լրացուցիչ բաքետների
    nextOverflow *bmap // հաջորդ ազատ լրացուցիչ բաքը
}

type bmap struct {
    tophash [8]uint8 // վերին հեշ (վերևի բիթերը) արագացման համար
    // Նշաններ, արժեքներ և ցուցիչ հաջորդ bmap-ի համար (եթե բաքը լրացուցիչ է)
    // բոլոր տվյալների դասավորությունը hmap.buckets-ում մեկ malloc բլոկում
    // մանրամասների համար տես ../../runtime/map.go
}