Go-da Map necə işləyir?

Go'da xəritə hash cədvəli kimi həyata keçirilir.

map strukturunun əsas komponentləri:

• Hash funksiyası: Açarları hash dəyərlərinə (tam ədədlər) xəritələndirir.
• Bucketların massivləri: Açar-dəyər cütlüklərinin saxlandığı siyahılar və ya massivlər toplusu. Bucket indeksləri açarın hash dəyəri ilə müəyyən edilir.
• Çatışmazlıqların idarə olunması: Müxtəlif açarlar eyni hash-ə malik olduqda (çatışmazlıq), bu elementlər eyni bucketdə saxlanılır, adətən əlaqəli siyahı və ya overflow bucket şəklində.
• Yükləmə faktoru: Elementlərin sayı ilə bucketların sayı arasındakı nisbət. Bir sərhəd aşılırsa, yenidən hashləmə (rehashing) həyata keçirilir: yeni, daha böyük bucket massivləri yaradılır və köhnə bucketlərdəki bütün elementlər yeni massivə köçürülür.

Go'da map strukturu hmap tipi ilə təmsil olunur:

 type hmap struct {
    count     int // Elementlərin sayı
    flags     uint8 // Vəziyyət bayraqları
    B         uint8 // log_2 bucket sayı (bucket sayı 2^B)
    noverflow uint16 // Overflow bucket sayı (yalnız statistik üçün)
    hash0     uint32 // Hash funksiyasının başlanğıc dəyəri

    buckets    unsafe.Pointer // Bucket massivinə göstərici (əsas və overflow)
    oldbuckets unsafe.Pointer // Köhnə bucket massivinə göstərici migrasiya zamanı
    nevacuate  uintptr // Köhnə bucket-in hansı hissəsinin tamamlandığını göstərir

    extra *mapextra // Əlavə məlumatlar (istəyə bağlı)
}

 type mapextra struct {
    overflow    *[2]*[]*bmap // Overflow bucket massivlərinə göstəricilər
    oldoverflow *[2]*[]*bmap // Köhnə overflow bucket massivlərinə göstəricilər
    nextOverflow *bmap // Növbəti boş overflow bucket
}

 type bmap struct {
    tophash [8]uint8 // Top hash (hash-in yuxarı bitləri) axtarışın sürətləndirilməsi üçün
    // Sonra açarlar, dəyərlər və növbəti bmap-ə göstəricilər (əgər bucket dolubsa)
    // Bütün məlumatları hmap.buckets üçün tək malloc bloku şəklində yerləşdirin
    // ətraflı məlumat üçün ../../runtime/map.go-ya baxın
}

Əməliyyatlar:

• Yerləşdirmə/Yeniləmə: Açarın hash-i hesablanır, bucket müəyyən edilir. Əgər açar artıq mövcuddursa, dəyər yenilənir. Əks halda, açar-dəyər cütlüyü bucket-ə əlavə olunur. Overflow və ya Load Factor-ı aşdıqda, rehash edilə bilər.
• Axtarış: Açarın hash-i hesablanır, bucket müəyyən edilir. Bucket-dəki elementlər top-hash-ə görə yoxlanır, sonra isə tam açar müqayisə edilir. Dəyər və mövcudluq flag-i qaytarılır.
• Silinmə: Açarın hash-i hesablanır, bucket müəyyən edilir. Element silinmiş kimi işarələnir (amma dərhal yaddaşdan silinmir). Silinmə, sonrakı əməliyyatlar və ya rehash zamanı həyata keçirilir.

Go'dakı xəritə sinxronlaşdırılmayıb və xarici sinxronizasiya olmadan çoxlu goroutine-lər tərəfindən təhlükəsiz istifadə edilə bilməz.