Maps in Go

Golang မှာ Map ဆိုတာ Key-Value pair တွေနဲ့ Data ကို သိမ်းဆည်းတဲ့ Built-in Data Structure တစ်ခုဖြစ်ပါတယ်။ တခြား Programming language တွေက Hash Table ဒါမှမဟုတ် Dictionary တွေနဲ့ သဘောတရားချင်း တူညီပါတယ်။

---

၁။ Map ၏ အဓိက အင်္ဂါရပ်များ

• Unordered: Map ထဲက Data တွေကို iterate လုပ်တဲ့အခါ ထည့်ထားတဲ့ အစီအစဉ်အတိုင်း ထွက်လာမယ်လို့ အာမခံချက်မရှိပါဘူး။

• Fast Lookup: Hash table ကို အခြေခံထားတာကြောင့် Key တစ်ခုကို ရှာဖွေတဲ့နှုန်းဟာ ပျမ်းမျှအားဖြင့် $O(1)$ ရှိပါတယ်။

• Reference Type: Map ကို function တစ်ခုဆီ pass လုပ်လိုက်တဲ့အခါ မူရင်း Map ကိုပဲ ညွှန်းဆိုနေမှာဖြစ်လို့ function ထဲက ပြင်ဆင်မှုတွေဟာ မူရင်းနေရာမှာပါ သက်ရောက်ပါတယ်။

---

၂။ Map ကို ကြေညာခြင်းနှင့် အသုံးပြုခြင်း

Map တစ်ခုကို make function သုံးပြီး တည်ဆောက်နိုင်သလို Map Literal နဲ့လည်း တိုက်ရိုက် တည်ဆောက်နိုင်ပါတယ်။

// make သုံးပြီး တည်ဆောက်ခြင်း
// map[KeyType]ValueType
m := make(map[string]int)

// Value ထည့်ခြင်း
m["apple"] = 5
m["orange"] = 10

// Map Literal သုံးပြီး တည်ဆောက်ခြင်း
prices := map[string]float64{
    "coffee": 2.5,
    "tea":    1.5,
}

Key တစ်ခု ရှိမရှိ စစ်ဆေးခြင်း

Map ထဲမှာ Key တစ်ခု တကယ်ရှိမရှိကို "Comma ok" idiom သုံးပြီး စစ်ဆေးရပါတယ်။

ဘာကြောင့်လဲဆိုရင် မရှိတဲ့ Key နဲ့တောင်မှ Map ကနေ data read လုပ်လို့ရပါတယ်။ ဒါကြောင့် တကယ် data ရှိမရှိကို ok နဲ့ စစ်ဆေးရမှာဖြစ်ပါတယ်။

val, ok := m["apple"]
if ok {
    fmt.Println("Value is:", val)
} else {
    fmt.Println("Key not found")
}

---

၃။ Map ၏ အတွင်းပိုင်း အလုပ်လုပ်ပုံ (Under the Hood)

Go map ရဲ့ နောက်ကွယ်မှာ Buckets လို့ခေါ်တဲ့ Array တစ်ခုရှိပါတယ်။ Key တစ်ခုကို ထည့်လိုက်တဲ့အခါ Go က အောက်ပါအဆင့်အတိုင်း လုပ်ဆောင်ပါတယ်။

1. Hashing: Key ကို Hash function ထဲ ထည့်ပြီး Hash value တစ်ခု ထုတ်ယူပါတယ်။

2. Bucket Selection: ရလာတဲ့ Hash value ကိုသုံးပြီး ဘယ် Bucket ထဲမှာ သိမ်းမလဲဆိုတာ ဆုံးဖြတ်ပါတယ်။

3. Storing: Bucket တစ်ခုစီမှာ Key-Value pair ၈ ခုအထိ သိမ်းနိုင်ပါတယ်။ အကယ်၍ Bucket တစ်ခု ပြည့်သွားရင် Overflow Buckets တွေကို ထပ်ချိတ်ပြီး သိမ်းဆည်းပါတယ်။

---

၄။ သတိထားရမည့် အချက်များ

(က) Nil Map

Map တစ်ခုကို ကြေညာရုံပဲ ကြေညာပြီး make နဲ့ initialize မလုပ်ထားရင် ၎င်းဟာ nil ဖြစ်နေပါလိမ့်မယ်။ Nil map ထဲကို data ထည့်ဖို့ ကြိုးစားရင် Runtime Panic ဖြစ်ပါလိမ့်မယ်။

Go

var m map[string]int
// m["test"] = 1 // Panic ဖြစ်မည်

(ခ) Concurrency

Go map တွေဟာ Thread-safe မဖြစ်ပါဘူး။ Goroutines အများကြီးကနေ Map တစ်ခုတည်းကို တစ်ပြိုင်နက် Write လုပ်ဖို့ ကြိုးစားရင် Program crash ဖြစ်ပါလိမ့်မယ်။ ဒါကို ဖြေရှင်းဖို့ sync.Mutex ကို သုံးပြီး Lock ချရပါမယ် (သို့မဟုတ်) sync.Map ကို သုံးရပါမယ်။

---

၅။ အနှစ်ချုပ်

Operation	Syntax
တည်ဆောက်ခြင်း	make(map[K]V)
ဖျက်ပစ်ခြင်း	delete(m, key)
အရေအတွက်	len(m)
Iterate လုပ်ခြင်း	for k, v := range m { ... }

Go map ဟာ အရမ်းအသုံးဝင်ပေမဲ့ unordered ဖြစ်တာနဲ့ concurrency ကိစ္စတွေကို သတိထားဖို့ လိုအပ်ပါတယ်။

မဖြစ်မနေသိထားရမည့်အရာများ

၁။ Go Map ၏ အခြေခံတည်ဆောက်ပုံ (Internal Structure)

Go map ကို hash table အဖြစ် အကောင်အထည်ဖော်ထားပြီး အဓိကအားဖြင့် Buckets များဖြင့် ဖွဲ့စည်းထားပါတယ်။

• Buckets: Map တစ်ခုမှာ bucket အများအပြားပါဝင်ပြီး bucket တစ်ခုစီမှာ key-value pair ၈ ခုအထိ သိမ်းဆည်းနိုင်ပါတယ်။

• Hashing: Key တစ်ခုကို သိမ်းဆည်းတော့မယ်ဆိုရင် Go က hash function ကိုသုံးပြီး အဲ့ဒီ key အတွက် hash value တစ်ခုကို တွက်ချက်ပါတယ်။

• Bucket Selection: ရလာတဲ့ hash value ရဲ့ lower bits တွေကို သုံးပြီး အဲ့ဒီ key ကို ဘယ် bucket ထဲမှာ သိမ်းမလဲဆိုတာ ဆုံးဖြတ်ပါတယ်။

---

၂။ Hash Seed နှင့် Hash Flooding Attack ကို ကာကွယ်ခြင်း

ဒါကတော့ map ရဲ့ security ပိုင်းမှာ အရေးအကြီးဆုံး အစိတ်အပိုင်းဖြစ်ပါတယ်။

Hash Flooding Attack ဆိုတာဘာလဲ?

အကယ်၍ attacker တစ်ယောက်က map ရဲ့ hash function အလုပ်လုပ်ပုံကို ကြိုတင်သိနေမယ်ဆိုရင် hash value တူညီတဲ့ (သို့မဟုတ် bucket တစ်ခုတည်းမှာ သွားစုမယ့်) key အများအပြားကို တမင်ဖန်တီးပြီး ပို့လွှတ်နိုင်ပါတယ်။ ဒါကို Hash Collision လို့ ခေါ်ပါတယ်။

• ရလဒ်: Map ရဲ့ performance ဟာ $O(1)$ (အမြန်ဆုံး) ကနေ $O(n)$ (အနှေးဆုံး) အထိ ကျဆင်းသွားပြီး CPU ကို အလွန်အကျွံ သုံးစွဲစေကာ system တစ်ခုလုံးကို ရပ်တန့်သွားစေနိုင်ပါတယ်။ (Denial of Service - DoS)

Hash Seed က ဘယ်လိုကာကွယ်သလဲ?

Go ဟာ map တစ်ခုစီကို runtime မှာ initialize လုပ်တိုင်း Random Hash Seed တစ်ခုကို အသုံးပြုပါတယ်။

• Dynamic Hashing: ဒီ seed ကြောင့် key တစ်ခုတည်း ဖြစ်နေရင်တောင် မတူညီတဲ့ map တွေမှာ ရလာမယ့် hash value တွေက တူမှာမဟုတ်တော့ပါဘူး။

• Unpredictability: Attacker အနေနဲ့ hash function ကို သိနေရင်တောင် ဒီ map ထဲမှာ သုံးထားတဲ့ random seed ကို မသိနိုင်တဲ့အတွက် hash collision ဖြစ်အောင် တိုက်ခိုက်ဖို့ မဖြစ်နိုင်တော့ပါဘူး။

---

၃။ Map ၏ Randomness နှင့် Iteration အလုပ်လုပ်ပုံ

Go developer တွေကြားမှာ အသိများတဲ့ "Map iteration is random" ဆိုတဲ့အချက်ဟာ တကယ်တော့ Go runtime က တမင်တကာ ထည့်သွင်းထားတဲ့ feature တစ်ခုပါ။

• Random Start Bucket: for range နဲ့ map ကို iterate လုပ်တဲ့အခါ Go ဟာ ဘယ် bucket ကနေ စပြီးဖတ်မလဲဆိုတာကို random ရွေးချယ်ပါတယ်။

• Random Start Offset: Bucket တစ်ခုထဲမှာရှိတဲ့ key ၈ ခုထဲက ဘယ် index ကနေ စမလဲဆိုတာကိုပါ random ထပ်ရွေးပါတယ်။

• ရည်ရွယ်ချက်: Developer တွေအနေနဲ့ map ထဲက data အစီအစဉ် (Order) ပေါ်မှာ လုံးဝမှီခိုပြီး code မရေးမိစေဖို့ ဖြစ်ပါတယ်။ အစီအစဉ်တစ်ခုအတိုင်း ထွက်လာမယ်လို့ ယူဆပြီး ရေးမိတဲ့ code တွေဟာ map ကြီးထွားလာတဲ့အခါ (rehash ဖြစ်တဲ့အခါ) bug တွေ ဖြစ်လာနိုင်လို့ Go က ကြိုတင်ကာကွယ်ထားတာပါ။

---

၄။ Go Map အသုံးပြုရာတွင် သတိထားရမည့် အချက်များ

• Nil Maps: var m map[string]int လို့ ကြေညာရုံနဲ့ map ဟာ nil ဖြစ်နေပြီး data ထည့်ရင် panic ဖြစ်ပါလိမ့်မယ်။ အမြဲတမ်း make(map[string]int) နဲ့ initialize လုပ်ရပါမယ်။

• Not Thread-Safe: Map တွေဟာ concurrency အတွက် safe မဖြစ်ပါဘူး။ goroutines အများကြီးကနေ တစ်ပြိုင်နက် write လုပ်ရင် runtime error တက်ပါမယ်။

• Comma OK Idiom: Key တစ်ခုရှိမရှိ စစ်ဆေးတဲ့အခါ val, ok := m[key] ပုံစံကို သုံးရပါမယ်။

Deep Dive: sync.Map ၏ အတွင်းပိုင်းလည်ပတ်ပုံနှင့် Pointer States များ

ပုံမှန် Go Map များသည် Hash Table နှင့် Buckets များပေါ်တွင် အခြေခံသော်လည်း sync.Map သည် Read-heavy လုပ်ငန်းစဉ်များအတွက် ပိုမိုမြန်ဆန်စေရန် Pointer-based စနစ်ကို အသုံးပြုထားသည်။ ၎င်း၏ အနှစ်သာရမှာ Value များကို တိုက်ရိုက်မသိမ်းဘဲ entry struct ဆီသို့ ညွှန်ပြသည့် Pointer (p) ကို အသုံးပြုခြင်းဖြစ်သည်။ ဤ Pointer ၏ ပြောင်းလဲနေသော အခြေအနေ (၃) မျိုးသည် sync.Map ၏ စွမ်းဆောင်ရည်ကို ထိန်းကျောင်းပေးသည်။

Pointer (p) ၏ State ၃ မျိုး

၁။ Normal State (Active)

ဒါကတော့ Entry တစ်ခုက Valid ဖြစ်ပြီး အသုံးပြုလို့ရနေတဲ့ အခြေအနေပါ။

• အလုပ်လုပ်ပုံ: Pointer p သည် တကယ့် Data ရှိရာ Memory လိပ်စာဆီသို့ တိုက်ရိုက်ညွှန်ပြနေသည်။

• ထူးခြားချက်: ဤအခြေအနေတွင် read နှင့် dirty map နှစ်ခုလုံးသည် တူညီသော Pointer ကို မျှဝေသုံးစွဲနေကြသဖြင့် Value တစ်ခုကို Update လုပ်လိုလျှင် Lock ယူစရာမလိုဘဲ Atomic operation ဖြင့်သာ Pointer ကို အသစ်လဲလိုက်ရုံဖြင့် Map နှစ်ခုလုံးတွင် အလိုအလျောက် Update ဖြစ်သွားသည်။

၂။ Deleted State (Nil)

Key တစ်ခုကို Map ထဲမှ ဖျက်လိုက်သောအခါ ချက်ချင်း အပြီးတိုင် ထုတ်ပစ်လိုက်ခြင်း မဟုတ်ဘဲ Soft Delete အနေဖြင့် ထားရှိခြင်းဖြစ်သည်။

• အလုပ်လုပ်ပုံ: Pointer p ကို nil အဖြစ် ပြောင်းလဲသတ်မှတ်လိုက်ခြင်းဖြစ်သည်။

• အခြေအနေ: ဤ Key သည် Map ထဲတွင် ရှိနေဆဲဖြစ်သော်လည်း nil ဖြစ်သွားသည့်အတွက် ရှာဖွေပါက "Not Found" အနေဖြင့်သာ ပြန်လာမည်ဖြစ်သည်။ ၎င်းသည် နောက်တစ်ဆင့်ဖြစ်သော Expunged State သို့ ကူးပြောင်းရန် အချက်ပြမှုလည်း ဖြစ်သည်။

၃။ Expunged State (Hard Deleted)

ဒါကတော့ sync.Map က Map နှစ်ခုကြား Data သန့်ရှင်းရေးလုပ်သည့် အထူး State တစ်ခုဖြစ်သည်။

• အလုပ်လုပ်ပုံ: Entry ကို Sentinel value (အထူးအမှတ်အသား) တစ်ခုဖြင့် အမှတ်အသားပြုလိုက်ပြီး အပြီးတိုင်ဖျက်ရန် ပြင်ဆင်လိုက်ခြင်းဖြစ်သည်။

• ထူးခြားချက်: ဤအခြေအနေတွင် အဆိုပါ Key သည် read map တွင်သာ ကျန်ရှိတော့ပြီး dirty map ထဲတွင် မပါဝင်တော့ပါ။ dirty map ကို read map အဖြစ် နောက်တစ်ကြိမ် မြှင့်တင် (Promote) လိုက်သောအခါမှသာ Memory ထဲမှ အပြီးတိုင် ပျောက်ကွယ်သွားမည်ဖြစ်သည်။

---

ဘာကြောင့် ဤဒီဇိုင်းကို အသုံးပြုသလဲ?

sync.Map သည် ပုံမှန် Map နှင့်မတူဘဲ ဤ Pointer State များဖြင့် လည်ပတ်ရခြင်းမှာ အောက်ပါအချက်များကြောင့်ဖြစ်သည်:

1. Lock-Free Updates: Normal state တွင် ရှိနေစဉ် Data update လုပ်ပါက Lock contention ကို ရှောင်ရှားနိုင်ပြီး Atomic operations များဖြင့်သာ လုပ်ဆောင်နိုင်သဖြင့် ပိုမိုမြန်ဆန်သည်။

2. Efficient Deletion: Key တစ်ခုကို ဖျက်သည့်အခါ Map တည်ဆောက်ပုံကြီးတစ်ခုလုံးကို ချက်ချင်း ပြန်ပြင်စရာမလိုဘဲ Pointer ကိုသာ nil ပြောင်းလဲလိုက်ခြင်းဖြင့် အလုပ်တွင်စေသည်။

3. Read Optimization: read map ကို Lock မလိုဘဲ အမြဲတမ်းဖတ်နိုင်အောင် (Atomic Load) စီစဉ်ထားပြီး၊ အသစ်တိုးလာသော Data များကိုသာ dirty map တွင် Lock ဖြင့် ထိန်းချုပ်ခြင်းဖြင့် Performance ကို မျှတအောင် လုပ်ဆောင်ပေးသည်။