سنناقش تنفيذ الخريطة بلغة بدون وصفات عامة ، وننظر في ماهية جدول التجزئة ، وكيف يتم ترتيبه في Go ، وما هي إيجابيات وسلبيات هذا التطبيق ، وما الذي يجب الانتباه إليه عند استخدام هذا الهيكل.
التفاصيل تحت خفض.
تحذير! إذا كنت معتادًا بالفعل على جداول التجزئة في Go ، فإنني أنصحك بتخطي الأساسيات والذهاب إلى
هنا ، وإلا فهناك خطر من التعب من اللحظة الأكثر إثارة للاهتمام.
ما هو جدول التجزئة
بادئ ذي بدء ، سوف أذكركم بجدول التجزئة. هذا هو هيكل البيانات الذي يسمح لك بتخزين أزواج قيمة المفتاح ، وكقاعدة عامة ، تمتلك وظائف:
- رسم الخرائط:
map(key) → value
- إدراجات:
insert(map, key, value)
- الحذف:
delete(map, key)
- البحث:
lookup(key) → value
تجزئة الجدول في الذهاب اللغة
يتم تمثيل جدول التجزئة بلغة go بواسطة الكلمة الأساسية للخريطة ويمكن الإعلان عنها بإحدى الطرق أدناه (المزيد عنها لاحقًا):
m := make(map[key_type]value_type) m := new(map[key_type]value_type) var m map[key_type]value_type m := map[key_type]value_type{key1: val1, key2: val2}
يتم تنفيذ العمليات الرئيسية على النحو التالي:
- إدراج:
m[key] = value
- إزالة:
delete(m, key)
- بحث:
value = m[key]
أو
value, ok = m[key]
يرحل حول طاولة في الذهاب
النظر في البرنامج التالي:
package main import "fmt" func main() { m := map[int]bool{} for i := 0; i < 5; i++ { m[i] = ((i % 2) == 0) } for k, v := range m { fmt.Printf("key: %d, value: %t\n", k, v) } }
إطلاق 1:
key: 3, value: false key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true
تشغيل 2:
key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true key: 3, value: false
كما ترون ، يختلف الإخراج من تشغيل إلى آخر. وكل ذلك لأن الخريطة في Go غير مرتبة ، وهذا هو ، ليس مرتبة. هذا يعني أنك لا تحتاج إلى الاعتماد على النظام عند التجول. يمكن العثور على السبب في الكود المصدري لوقت تشغيل اللغة:
يتم تحديد موقع البحث
بشكل عشوائي ، تذكر هذا! تقول الشائعات أن مطوري وقت التشغيل يجبرون المستخدمين على عدم الاعتماد على الطلب.
الذهاب بحث الجدول
لنلقِ نظرة على الكود مرة أخرى. لنفترض أننا نريد إنشاء أزواج "رقم" - "عدد مرات 10":
package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} fmt.Println(m, m[0], m[1], m[2]) }
نطلق:
map[0:0 1:10] 0 10 0
ونحن نرى أنه عندما حاولنا الحصول على قيمة اثنين (نسينا طرحها) ، حصلنا على 0. نجد سطورًا في
الوثائق تشرح هذا السلوك: "محاولة جلب قيمة خريطة مع مفتاح غير موجود في الخريطة ستُرجع القيمة الصفرية إلى نوع الإدخالات في الخريطة. "، ولكن المترجمة إلى الروسية ، وهذا يعني أنه عندما نحاول الحصول على القيمة من الخريطة ، ولكن ليس هناك ، نحصل على" قيمة نوع الصفر "، والتي في حالة الرقم 0. ماذا تفعل ، إذا كنا نريد التمييز بين الحالات 0 وغياب 2؟ للقيام بذلك ، توصلنا إلى شكل خاص من "الواجب المتعدد" - نموذج حيث تقوم الخريطة بدلاً من القيمة الفردية المعتادة بإرجاع زوج: القيمة نفسها وبوليانية أخرى تجيب على السؤال ما إذا كان المفتاح المطلوب موجودًا في الخريطة أم لا "
صحيح أن الجزء السابق من الكود سيبدو كما يلي:
package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} m2, ok := m[2] if !ok {
وعند بدء التشغيل نحصل على:
map[0:0 1:10] 0 10 20
إنشاء جدول في Go.
لنفترض أننا نريد حساب عدد مرات تواجد كل كلمة في سلسلة ، وبدء قاموس لذلك والاطلاع عليها.
package main func main() { var m map[string]int for _, word := range []string{"hello", "world", "from", "the", "best", "language", "in", "the", "world"} { m[word]++ } for k, v := range m { println(k, v) } }
هل ترى مصيدة
غوفر ؟ - وهو!
عندما نحاول بدء مثل هذا البرنامج ، نشعر بالذعر ورسالة "التعيين للدخول في خريطة النيل". وكل ذلك لأن mapa هو نوع مرجعي ولا يكفي الإعلان عن متغير ، فأنت بحاجة إلى تهيئة:
m := make(map[string]int)
أقل قليلاً سيكون من الواضح لماذا هذا يعمل بهذه الطريقة. في البداية ، تم تقديم 4 طرق بالفعل لإنشاء خريطة ، اثنتان منها درسناها - هذا الإعلان كمتغير وخلق من خلال الصنع. يمكنك أيضًا إنشاء باستخدام تصميم "
الحرف المركبة "
map[key_type]value_type{}
وإذا كنت ترغب في ذلك ، حتى مع التهيئة على الفور مع القيم ، فإن هذه الطريقة صالحة أيضًا أما بالنسبة للإنشاء باستخدام جديد - في رأيي ، فليس من المنطقي ، لأن هذه الوظيفة تخصص ذاكرة لمتغير وتُرجع مؤشرًا إليها مملوءًا بقيمة صفرية من النوع ، والتي في حالة الخريطة ستكون صفرية (نحصل على نفس النتيجة مثل في فار ، بتعبير أدق مؤشر عليه).
كيف يتم تمرير الخريطة إلى وظيفة؟
لنفترض أن لدينا وظيفة تحاول تغيير الرقم الذي تم تمريره إليها. دعونا نرى ما يحدث قبل وبعد المكالمة:
package main func foo(n int) { n = 10 } func main() { n := 15 println("n before foo =", n) foo(n) println("n after foo =", n) }
أعتقد أن المثال واضح تمامًا ، لكنه لا يزال يتضمن الاستنتاج:
n before foo = 15 n after foo = 15
كما خمنت على الأرجح ، جاءت الدالة n بالقيمة ، وليس بالرجوع إليها ، لذلك لم يتغير المتغير الأصلي.
دعونا نفعل خدعة مماثلة mapa:
package main func foo(m map[int]int) { m[10] = 10 } func main() { m := make(map[int]int) m[10] = 15 println("m[10] before foo =", m[10]) foo(m) println("m[10] after foo =", m[10]) }
وها هو:
m[10] before foo = 15 m[10] after foo = 10
لقد تغيرت القيمة. "حسنا ، يتم تمرير Mapa بالإشارة؟" ، أنت تسأل.
لا. لا توجد روابط في Go. من المستحيل إنشاء متغيرين بعنوان واحد ، كما في C ++ على سبيل المثال. ولكن بعد ذلك يمكنك إنشاء متغيرين للإشارة إلى نفس العنوان (ولكن هذه مؤشرات ، وهي في Go).
لنفترض أن لدينا وظيفة fn تستعد الخريطة m. في الوظيفة الرئيسية ، نعلن ببساطة عن متغير ، ونرسله للتهيئة وننظر فيما حدث بعد ذلك.
package main import "fmt" func fn(m map[int]int) { m = make(map[int]int) fmt.Println("m == nil in fn?:", m == nil) } func main() { var m map[int]int fn(m) fmt.Println("m == nil in main?:", m == nil) }
الاستنتاج:
m == nil in fn?: false
m == nil in main?: true
لذلك ، تم تمرير المتغير m
بالقيمة ، لذلك ، كما في حالة تمرير int منتظم إلى الدالة ، فإنه لم يتغير (تم تغيير النسخة المحلية من القيمة في fn). ثم لماذا تتغير القيمة الكاذبة في حد ذاتها؟ للإجابة على هذا السؤال ، خذ بعين الاعتبار الكود من وقت تشغيل اللغة:
الخريطة في Go هي مجرد مؤشر لبنية hmap. هذا هو إجابة السؤال لماذا ، على الرغم من حقيقة أن الخريطة يتم تمريرها إلى الدالة من حيث القيمة ، فإن القيم نفسها تتغير فيها - كل ما يتعلق بالمؤشر. تحتوي بنية hmap أيضًا على ما يلي: عدد العناصر ، وعدد "الجرافات" (المقدمة باعتبارها لوغاريتم لتسريع العمليات الحسابية) ، والبذور للتجزئة العشوائية (لتجعل من الصعب إضافة - حاول التقاط المفاتيح بحيث توجد تصادمات مستمرة) ، وجميع أنواع مجالات الخدمة والأهم من ذلك ، مؤشر إلى مجموعات حيث يتم تخزين القيم. لنلقِ نظرة على الصورة:
تُظهر الصورة صورة تخطيطية للهيكل الموجود في الذاكرة - يوجد رأس hmap ، حيث يكون المؤشر عبارة عن خريطة في Go (يتم إنشاؤه عند التعريف بـ var ، لكن لم تتم تهيئته ، مما يتسبب في تعطل البرنامج عند محاولة إدراجه). حقل الجرافات هو مستودع للأزواج ذات القيمة الرئيسية ، وهناك العديد من الجرافات ، كل منها يحتوي على 8 أزواج. أولاً في "المجموعة" توجد فتحات لبتات التجزئة الإضافية (يُسمى e0..e7 e - لأن وحدات التجزئة
الإضافية ). فيما يلي المفاتيح والقيم كقائمة بجميع المفاتيح أولاً ، ثم قائمة بجميع القيم.
وفقًا لتجزئة الوظيفة ، يتم تحديد "الجرافة" التي نضعها في القيمة ، داخل كل "دلو" يمكن أن يكون هناك ما يصل إلى 8 تصادمات ، في نهاية كل "دلو" يوجد مؤشر لواحد إضافي ، إذا تجاوزت المجموعة السابقة.
كيف تنمو الخريطة؟
في شفرة المصدر ، يمكنك العثور على السطر:
وهذا هو ، إذا كان هناك متوسط أكثر من 6.5 عنصر في كل مجموعة ، تحدث زيادة في صفيف الجرافات. في هذه الحالة ، يتم تخصيص الصفيف أكثر من مرتين ، ويتم نسخ البيانات القديمة فيه في أجزاء صغيرة في كل إدخال أو حذف ، حتى لا يتم إنشاء تأخير كبير جدًا. لذلك ، ستكون جميع العمليات أبطأ قليلاً في عملية إخلاء البيانات (عند البحث أيضًا ، يتعين علينا البحث في مكانين). بعد الإخلاء الناجح ، تبدأ البيانات الجديدة في الاستخدام.
أخذ عنوان عنصر الخريطة.
نقطة أخرى مثيرة للاهتمام - في بداية استخدام اللغة التي أردت القيام بها مثل هذا:
package main import ( "fmt" ) func main() { m := make(map[int]int) m[1] = 10 a := &m[1] fmt.Println(m[1], *a) }
لكن Go تقول: "لا يمكن أن تأخذ عنوان m [1]". يفسر سبب استحالة أخذ عنوان القيمة في إجراء إخلاء البيانات. تخيل أننا أخذنا عنوان القيمة ، ثم نما mapa ، تم تخصيص ذاكرة جديدة ، تم إخلاء البيانات ، تم حذف البيانات القديمة ، أصبح المؤشر غير صحيح ، لذا فإن هذه العمليات محظورة.
كيف يتم تطبيق الخريطة دون الأدوية الجنيسة؟
لا واجهة فارغة ، ولا توليد الشفرة له علاقة به ؛ كل شيء هو استبداله في وقت الترجمة. النظر في ما هي وظائف مألوفة من الذهاب إلى:
v := m["k"] → func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer v, ok := m["k"] → func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) m["k"] = 9001 → func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer delete(m, "k") → func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)
نرى أن هناك وظائف mapaccess لعمليات الوصول ، لكتابة وحذف mapassign و mapdelete ، على التوالي. تستخدم جميع العمليات unsafe.Pointer ، والذي لا يهتم بالنوع الذي يشير إليه ، ويتم وصف المعلومات الخاصة بكل قيمة بواسطة
واصف النوع .
type mapType struct { key *_type elem *_type ...} type _type struct { size uintptr alg *typeAlg ...} type typeAlg struct { hash func(unsafe.Pointer, uintptr) uintptr equal func(unsafe.Pointer, unsafe.Pointer) bool...}
MapType يخزن واصفات (_type) من المفتاح والقيمة. بالنسبة للواصف النوعي ، يتم تعريف العمليات (typeAlg) المقارنة ، وأخذ التجزئة والحجم ، وما إلى ذلك ، حتى نعرف دائمًا كيفية إنتاجها.
أكثر قليلاً عن كيفية عمله. عندما نكتب v = m [k] (نحاول الحصول على قيمة v من المفتاح k) ، يقوم المترجم بإنشاء شيء مثل التالي:
kPointer := unsafe.Pointer(&k) vPointer := mapaccess1(typeOf(m), m, kPointer) v = *(*typeOfvalue)vPointer
بمعنى ، نأخذ مؤشرًا إلى مفتاح ، بنية mapType ، نكتشف منه أيًا من واصفات المفتاح والقيمة ، والمؤشر إلى hmap نفسه (أي ، الخريطة) ونمرّرها جميعًا إلى mapaccess1 ، والتي ستُرجع المؤشر إلى القيمة. نحن يلقي المؤشر إلى النوع المطلوب ، dereference والحصول على القيمة.
الآن دعونا نلقي نظرة على رمز البحث من وقت التشغيل (والذي تم تكييفه قليلاً للقراءة):
func lookup(t *mapType, m *mapHeader, key unsafe.Pointer) unsafe.Pointer {
تبحث الوظيفة عن المفتاح في الخريطة وتُرجع مؤشرًا إلى القيمة المطابقة ، فالوسيطات مألوفة لنا بالفعل - هذا هو mapType ، الذي يخزن واصفات الأنواع والقيم الأساسية ، وتعيين نفسه (mapHeader) ومؤشر إلى الذاكرة التي تخزن المفتاح. نرجع مؤشر إلى الذاكرة التي تخزن القيمة.
if m == nil || m.count == 0 { return zero }
بعد ذلك ، نتحقق مما إذا كان المؤشر إلى رأس الخريطة ليس خاليًا ، وإذا كان هناك 0 عنصرًا ويعيد قيمة فارغة ، إذا كان الأمر كذلك.
hash := t.key.hash(key, m.seed)
نحسب تجزئة المفتاح (نعرف كيفية حساب مفتاح معين من واصف نوع). ثم نحاول أن نفهم ما هو "الجرافة" التي تحتاج إلى الذهاب إليها ونرى (ما تبقى من القسمة على عدد "الجرافات" ، الحسابات تتسارع قليلاً). ثم نحسب التجزئة الإضافية (نأخذ أهم 8 بتات من التجزئة) ونحدد موضع "الجرد" في الذاكرة (حساب العنوان).
for { for i := 0; i < 8; i++ { if b.extra[i] != extra {
البحث ، إذا نظرت ، ليس معقدًا للغاية: فنحن نمر بسلاسل سلاسل "الجرافات" ، وننتقل إلى السلسلة التالية ، إذا لم تجدها. يبدأ البحث في "الجرافة" بمقارنة سريعة للتجزئة الإضافية (وهذا هو السبب في أن هذه e0 ... e7 في بداية كل منها عبارة عن علامة "مصغرة" للزوج للمقارنة السريعة). إذا لم تكن متطابقة ، فانتقل إلى أبعد من ذلك ، إذا كانت غير متطابقة ، فسنقوم بالتحقق بعناية أكبر - حيث نحدد المكان الذي يشتبه في أنه يتم البحث عنه في الذاكرة ، مقارنة ما إذا كان مساوياً لما تم طلبه. إذا كانت مساوية ، حدد موضع القيمة في الذاكرة والعودة. كما ترون ، لا شيء خارق للطبيعة.
استنتاج
استخدم الخرائط ، ولكن تعرف وفهم كيف تعمل! يمكنك تجنب حدوث هذه المشكلة من خلال فهم بعض التفاصيل الدقيقة - لماذا لا يمكنك تحمل عنوان القيمة ، ولماذا يقع كل شيء أثناء الإعلان دون التهيئة ، ولماذا من الأفضل تخصيص الذاكرة مقدمًا ، إذا كان عدد العناصر معروفًا (سنتجنب عمليات الإخلاء) وأكثر من ذلك بكثير.
المراجع:
"اذهبوا إلى خرائط في العمل" ، أندرو جيراند"كيف ينفّذ وقت التشغيل الخرائط بكفاءة" ، ديف تشيني"فهم النوع في الذهاب" ، وليام كينيديداخل تطبيق الخريطة ، كيث راندالخريطة شفرة المصدر ، الذهاب وقت التشغيلالمواصفات golangالذهاب فعالةالصور غوفر