جداول التعيين في Go

بشكل عام، هناك طريقتان لتنفيذ بنية بيانات جداول التعيين: جدول التجزئة (hash table) وشجرة البحث (search tree)، والفرق هو أن الأول غير مرتب والثاني مرتب. في Go، تنفيذ map يعتمد على الدلاء التجزئة (وهي أيضاً جدول تجزئة)، لذا فهو غير مرتب أيضاً، ولن يتم شرح مبادئ التنفيذ بالتفصيل في هذا المقال لأنه يتجاوز نطاق الأساسيات، وسيتم تحليله بعمق لاحقاً.

TIP

للتعرف على مبادئ map يمكنك زيارة تنفيذ map

التهيئة

في Go، نوع مفتاح map يجب أن يكون قابلاً للمقارنة، مثلاً string و int قابلان للمقارنة، بينما []int غير قابل للمقارنة، وبالتالي لا يمكن استخدامه كمفتاح لـ map. هناك طريقتان لتهيئة map: الأولى هي القيمة الحرفية، والصيغة كالتالي:

map[keyType]valueType{}

بعض الأمثلة:

mp := map[int]string{
   0: "a",
   1: "a",
   2: "a",
   3: "a",
   4: "a",
}

mp := map[string]int{
   "a": 0,
   "b": 22,
   "c": 33,
}

الطريقة الثانية هي استخدام الدالة المدمجة make، بالنسبة لـ map تقبل معاملين: النوع والسعة الأولية، مثال:

mp := make(map[string]int, 8)

mp := make(map[string][]int, 10)

map هو نوع مرجعي، يمكن الوصول لـ map ذي القيمة الصفرية أو غير المُهيأ، لكن لا يمكن تخزين عناصر فيه، لذا يجب تخصيص ذاكرة له:

func main() {
   var mp map[string]int
   mp["a"] = 1
   fmt.Println(mp)
}

panic: assignment to entry in nil map

TIP

عند تهيئة map يجب محاولة تخصيص سعة معقولة لتقليل عدد مرات التوسع.

الوصول

الوصول لـ map يتم مثل الوصول لمصفوفة عبر الفهرس:

func main() {
  mp := map[string]int{
    "a": 0,
    "b": 1,
    "c": 2,
    "d": 3,
  }
  fmt.Println(mp["a"])
  fmt.Println(mp["b"])
  fmt.Println(mp["d"])
  fmt.Println(mp["f"])
}

من خلال الكود يمكن ملاحظة أنه حتى لو لم يكن زوج المفتاح-القيمة "f" موجوداً في map، لا يزال هناك قيمة مُرجعة. map للمفتاح غير الموجود يُرجع القيمة الصفرية للنوع المقابل، وعند الوصول لـ map هناك فعلياً قيمتان مُرجعتان: الأولى هي قيمة النوع المقابل، والثانية قيمة منطقية تمثل ما إذا كان المفتاح موجوداً، مثلاً:

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   if val, exist := mp["f"]; exist {
      fmt.Println(val)
   } else {
      fmt.Println("المفتاح غير موجود")
   }
}

حساب طول map:

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   fmt.Println(len(mp))
}

تخزين القيم

تخزين القيم في map مشابه لتخزين القيم في مصفوفة، مثلاً:

func main() {
   mp := make(map[string]int, 10)
   mp["a"] = 1
   mp["b"] = 2
   fmt.Println(mp)
}

استخدام مفتاح موجود عند تخزين قيمة سيؤدي للكتابة فوق القيمة الأصلية:

func main() {
   mp := make(map[string]int, 10)
   mp["a"] = 1
   mp["b"] = 2
   if _, exist := mp["b"]; exist {
      mp["b"] = 3
   }
   fmt.Println(mp)
}

لكن هناك حالة خاصة، وهي عندما يكون المفتاح math.NaN():

func main() {
  mp := make(map[float64]string, 10)
  mp[math.NaN()] = "a"
  mp[math.NaN()] = "b"
  mp[math.NaN()] = "c"
  _, exist := mp[math.NaN()]
  fmt.Println(exist)
  fmt.Println(mp)
}

false
map[NaN:c NaN:a NaN:b]

من خلال النتيجة يمكن ملاحظة أن نفس قيمة المفتاح لم يتم الكتابة فوقها، بل يمكن وجود عدة نسخ، ولا يمكن تحديد وجودها، وبالتالي لا يمكن جلب القيمة بشكل طبيعي. لأن NaN معرف بمعيار IEE754، وتنفيذه يتم بواسطة تعليمة التجميع UCOMISD، وهي تعليمة مقارنة أعداد فاصلة عائمة مزدوجة الدقة بدون ترتيب، وتأخذ بعين الاعتبار حالة NaN، وبالتالي تكون النتيجة أن أي رقم لا يساوي NaN، و NaN لا يساوي نفسه، وهذا يسبب اختلاف قيمة التجزئة في كل مرة. نوقش هذا الأمر بشكل مكثف في المجتمع، لكن الجهة الرسمية ترى أنه لا حاجة للتعديل، لذا يجب تجنب استخدام NaN كمفتاح لـ map قدر الإمكان.

الحذف

func delete(m map[Type]Type1, key Type)

حذف زوج مفتاح-قيمة يتطلب استخدام الدالة المدمجة delete، مثلاً:

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   fmt.Println(mp)
   delete(mp, "a")
   fmt.Println(mp)
}

map[a:0 b:1 c:2 d:3]
map[b:1 c:2 d:3]

تجدر الإشارة إلى أنه إذا كانت القيمة NaN، لا يمكن حتى حذف زوج المفتاح-القيمة:

func main() {
   mp := make(map[float64]string, 10)
   mp[math.NaN()] = "a"
   mp[math.NaN()] = "b"
   mp[math.NaN()] = "c"
   fmt.Println(mp)
   delete(mp, math.NaN())
   fmt.Println(mp)
}

map[NaN:c NaN:a NaN:b]
map[NaN:c NaN:a NaN:b]

الاجتياز

من خلال for range يمكن اجتياز map، مثلاً:

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   for key, val := range mp {
      fmt.Println(key, val)
   }
}

c 2
d 3
a 0
b 1

يمكن ملاحظة أن النتيجة غير مرتبة، مما يؤكد أن map يُخزن بدون ترتيب. تجدر الإشارة إلى أن NaN وإن كان لا يمكن جلبه بشكل طبيعي، يمكن الوصول إليه من خلال الاجتياح، مثلاً:

func main() {
   mp := make(map[float64]string, 10)
   mp[math.NaN()] = "a"
   mp[math.NaN()] = "b"
   mp[math.NaN()] = "c"
   for key, val := range mp {
      fmt.Println(key, val)
   }
}

NaN a
NaN c
NaN b

المسح

قبل go1.21، لمسح map كان يجب حذف كل مفتاح map:

func main() {
  m := map[string]int{
    "a": 1,
    "b": 2,
  }
  for k, _ := range m {
    delete(m, k)
  }
  fmt.Println(m)
}

لكن go1.21 حدّث دالة clear، فلا حاجة للعملية السابقة، فقط clear واحدة تكفي للمسح:

func main() {
  m := map[string]int{
    "a": 1,
    "b": 2,
  }
  clear(m)
  fmt.Println(m)
}

المخرجات:

map[]

Set

Set هو مجموعة غير مرتبة لا تحتوي على عناصر مكررة، Go لا توفر بنية بيانات مماثلة، لكن مفاتيح map غير مرتبة ولا يمكن تكرارها، لذا يمكن استخدام map كبديل لـ set:

func main() {
  set := make(map[int]struct{}, 10)
  for i := 0; i < 10; i++ {
    set[rand.Intn(100)] = struct{}{}
  }
  fmt.Println(set)
}

map[0:{} 18:{} 25:{} 40:{} 47:{} 56:{} 59:{} 81:{} 87:{}]

TIP

الهيكل الفارغ لا يشغل ذاكرة

ملاحظات

map ليس بنية بيانات آمنة للتزامن، فريق Go يرى أن استخدام map في معظم الحالات لا ينطوي على سيناريوهات تزامن عالي، وإدخال أقفال تبادلية سيقلل الأداء بشكل كبير، ولدى map آلية اكتشاف قراءة/كتابة داخلياً، وإذا حدث تعارض سيُطلق fatal error. مثلاً الحالات التالية لديها احتمالية كبيرة لإطلاق fatal:

func main() {

   group.Add(10)
   // map
   mp := make(map[string]int, 10)
   for i := 0; i < 10; i++ {
      go func() {
         // عملية كتابة
         for i := 0; i < 100; i++ {
            mp["helloworld"] = 1
         }
         // عملية قراءة
         for i := 0; i < 10; i++ {
            fmt.Println(mp["helloworld"])
         }
         group.Done()
      }()
   }
   group.Wait()
}

fatal error: concurrent map writes

في هذه الحالة، يجب استخدام sync.Map كبديل.

جداول التعيين في Go ​

التهيئة ​

الوصول ​

تخزين القيم ​

الحذف ​

الاجتياز ​

المسح ​

Set ​

ملاحظات ​