كيفية استخدام النوع HashMap لتخزين البيانات في رست Rust

نستعرض في هذا المقال آخر التجميعات الشائعة في رست التي تحدثنا عنها سابقًا خلال رحلتنا في سلسلة البرمجة بلغة رست ألا وهي الخريطة المعمّاة hash map.

الخريطة المعماة HashMap

يخزّن النوع HashMap<K, V>‎ ربطًا ما بين القيم من النوع K التي تمثل المفاتيح والقيم من النوع V التي تمثل القيم باستخدام دالة التعمية hashing function، التي تحدد أين يجب وضع هذه المفاتيح والقيم في الذاكرة. تدعم كثيرًا من لغات البرمجة هذا النوع من هيكل البيانات إلا أنها غالبًا ما تستخدم اسمًا مختلفًا مثل النوع hash، أو خريطة map، أو كائن object، أو جدول hash، أو قاموس dictionary، أو مصفوفة مترابطة associative array والقائمة تطول.

الخرائط المعمّاة مفيدة عندما تريد البحث عن بيانات دون استخدام دليل لها كما هو الحال في الأشعة vectors وإنما باستخدام مفتاح key قد يكون من أي نوع بيانات. على سبيل المثال، يمكنك تتبع نتيجة كل فريق في لعبة ما باستخدام الخريطة المعمّاة باستخدام اسم الفريق مفتاحًا للقيمة ونتيجة كل فريق مثل قيم، ويمكنك بالتالي الحصول على نتيجة الفريق باستخدام اسمه.

سنستعرض مبادئ الواجهة البرمجية الخاصة بالخرائط المعمّاة في هذا المقال، إلا أن هناك المزيد من الأشياء المثيرة للاهتمام الموجودة ضمن الدوال المُعرّفة في HashMap<K, V>‎ ضمن المكتبة القياسية، ولكن عليك التحقق من توثيق المكتبة القياسية إذا أردت المزيد من التفاصيل.

إنشاء خريطة معماة HashMap جديدة

إحدى الطرق لإنشاء خريطة معمّاة فارغة هي باستخدام new وإضافة العناصر باستخدام insert. نتابع في الشيفرة 20 نتيجة فريقّين اسمهما أزرق Blue وأصفر Yellow، إذ يبدأ الفريق الأزرق بعشر نقاط والفريق الأصفر بخمسين نقطة.

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

[الشيفرة 20: إنشاء خريطة معماة جديدة وإضافة بعض المفاتيح والقيم إليها]

لاحظ أننا بحاجة كتابة use لتضمين HashMap من الجزء الذي يحتوي على التجميعات من المكتبة القياسية، وهذه هي التجميعة الأقل استخدامًا من التجميعات الثلاث الشائعة التي تكلمنا عنها، لذا فهي غير مضمّنة تلقائيًا في مقدمة البرنامج، إضافةً لما سبق، تملك الخرائط المعمّاة دعمًا أقل في المكتبة القياسية من التجميعات الأخرى وليس هناك ماكرو موجود مسبقًا لإنشاء خريطة معمّاة على سبيل المثال.

تخزّن الخرائط المعماة البيانات في الكومة heap كما هو الحال في الأشعة، إذ تحتوي الخريطة المُعمّاة السابقة على مفاتيح من النوع String وقيم من النوع i32، وكما هو الحال في الأشعة أيضًا فإن الخرائط المعماة متجانسة، بمعنى أن جميع المفاتيح يجب أن تكون من نفس النوع وكذلك الحال بالنسبة للقيم.

الوصول إلى القيم في الخريطة المعماة

يمكننا الحصول على قيمة في الخريطة المعماة باستخدام مفتاحها وتابع get كما هو موضح في الشيفرة 21.

   fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    let team_name = String::from("Blue");
    let score = scores.get(&team_name).copied().unwrap_or(0);
}

[الشيفرة 21: الوصول إلى نتيجة الفريق الأزرق المخزنة في الخريطة المعمّاة]

سيأخذ score القيمة المرتبطة مع الفريق الأزرق وستكون النتيجة 10. يُعيد التابع get قيمةً من النوع Option<&V>‎ وبالتالي إذا لم يكن هناك أي قيمة للمفتاح المحدد في الخريطة المعمّاة، فسيعيد التابع get القيمة None. يتعامل هذا البرنامج مع Option باستدعاء unwrap_or لضبط score إلى صفر إذا كان score لا يحتوي على قيمة للمفتاح المحدّد.

يمكننا المرور على كل زوج مفتاح/قيمة في الخريطة المعمّاة بطريقة مشابهة لما نفعل في الأشعة عن طريق حلقة for:

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    for (key, value) in &scores {
        println!("{}: {}", key, value);
    }

ستطبع الشيفرة البرمجية السابقة كل زوج بترتيب عشوائي:

Yellow: 50
Blue: 10

الخرائط المعماة والملكية

تُنسخ القيم التي تطبّق السمة Copy، مثل i32 إلى الخريطة المعماة؛ بينما تُنقل القيم للأنواع المملوكة، مثل String وتصبح الخريطة المعماة مالكةً لهذه القيم كما هو موضح في الشيفرة 22.

    use std::collections::HashMap;

    let field_name = String::from("Favorite color");
    let field_value = String::from("Blue");

    let mut map = HashMap::new();
    map.insert(field_name, field_value);
    // ‫يصبح كل من field_name و field_value غير صالح بحلول هذه النقطة
    // حاول استخدامهما وانظر إلى خطأ المصرف الذي ستحصل عليه

[الشيفرة 22: توضيح أن المفاتيح والقيم تصبح مملوكة من قبل الخريطة المعماة فور إدخالها إليها]

لا يمكننا استخدام القيمتين field_name و field_value بعد نقلهما إلى الخريطة المعماة باستدعاء التابع insert.

لن تُنقل القيم إلى الخريطة المعماة في حال أضفنا مراجعًا القيم، إلا أن القيم التي تُشير إليها هذه المراجع يجب أن تكون صالحة طالما الخريطة المعماة صالحة على أقل تقدير، وسنتحدث مفصلًا عن هذه المشاكل لاحقًا.

تحديث قيم خريطة معماة

على الرغم من كون أزواج القيمة والمفتاح قابلة للزيادة إلا أنه يجب أن يقابل كل مفتاح فريد قيمة واحدة فقط (العكس ليس صحيحًا، على سبيل المثال قد تكون نتيجة كل من الفريق الأزرق والأصفر 10 في الخريطة المعماة scores في الوقت ذاته).

عليك أن تحدد التصرف الذي ستفعله عند تعديل القيم الموجودة في الخريطة المعمّاة والوصول إلى مفتاح له قيمة مسبقة، إذ يمكنك في هذه الحالة استبدال القيمة القديمة بالقيمة الجديدة وإهمال القيمة القديمة كليًا، أو تستطيع جمع القيمة القديمة مع القيمة الجديدة. دعنا ننظر إلى كيفية تحقيق كلا الطريقتين.

الكتابة على القيمة

إذا أدخلنا مفتاحًا وقيمةً إلى خريطة معمّاة، ثمّ أدخلنا المفتاح ذاته مع قيمة مختلفة، ستُستبدل القيم المرتبطة بذلك المفتاح. على الرغم من أن الشيفرة 23 تستدعي التابع insert مرتين، إلا أن الخريطة المعماة الناتجة ستحتوي على زوج مفتاح/قيمة واحد لأننا أدخلنا قيمةً لمفتاح الفريق الأزرق في المرتين.

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Blue"), 25);

    println!("{:?}", scores);

[الشيفرة 23: استبدال قيمة مخزّنة في خريطة معمّاة باستخدام مفتاحها]

ستطبع الشيفرة البرمجية السابقة ‎{"Blue": 25}، إذ كُتِبَ على القيمة 10 السابقة القيمة 25.

إضافة مفتاح وقيمة فقط في حال عدم وجود المفتاح

من الشائع أن نكون بحاجة للتحقق من مفتاح فيما إذا كان موجود مسبقًا أم لا في خريطة المعمّاة مع قيمة ما، ومن ثم إجراء التالي: نبقي القيمة الموجود كما هي إذا كان المفتاح موجودًا في الخريطة المعماة، وإلا فنضيف المفتاح مع القيمة إذا لم نجد المفتاح.

لدى الخرائط المعماة واجهة برمجية خاصة بتلك العملية وهي التابع entry الذي يأخذ المفتاح التي تريد أن تتحقق منه مثل معامل، ويُعيد معددًا اسمه Entry يمثّل القيمة الموجودة أو غير الموجودة. دعنا نقول بأننا نريد أن نتحقق إذا كان مفتاح الفريق الأصفر يحتوي على قيمة؛ وإذا لم تكن هناك قيمة موجودة، نريد عندها إضافة القيمة 50 وينطبق الأمر ذاته على الفريق الأزرق. تبدو الشيفرة البرمجية باستخدام الواجهة البرمجية الخاصة بالتابع entry كما هو موضح في الشيفرة 24.

    use std::collections::HashMap;

    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);

    scores.entry(String::from("Yellow")).or_insert(50);
    scores.entry(String::from("Blue")).or_insert(50);

    println!("{:?}", scores);

[الشيفرة 24: استخدام التابع entry لإدخال قيمة فقط في حال لا يحتوي المفتاح على قيمة مرتبطة به]

التابع or_insert في Entry معرّف ليُعيد مرجعًا قابلًا للتعديل يشير إلى قيمة المفتاح Entry إذا كان المفتاح المحدد موجودًا، وإلا سيدخل قيمة المعامل على أنها قيمة جديدة للمفتاح وسيُعيد مرجعًا قابلًا للتعديل إلى القيمة الجديدة، وهذه الطريقة أفضل من كتابة المنطق ذلك بأنفسنا، كم أنها تعمل بصورةٍ أفضل مع مدقق الاستعارة borrow checker.

بتشغيل الشيفرة 24، نحصل على الخرج {Yellow": 50, "Blue": 10"}، إذ سيتسبب الاستدعاء الأول للتابع entry بإضافة مفتاح الفريق الأصفر بالقيمة 50 لأن الفريق الأصفر لا يحتوي على أي قيمة بعد، بينما لن يُغيّر الاستدعاء الثاني للتابع entry الخريطة المعمّاة لأن مفتاح الفريق الأزرق موجود مسبقًا بقيمة 10.

تحديث قيمة بحسب قيمتها السابقة

حالة أخرى لاستخدام الخرائط المعماة هي بالبحث عن قيمة المفتاح ومن ثم التعديل عليها بناءً على قيمتها القديمة، على سبيل المثال توضح الشيفرة 25 برنامجًا يعدّ عدد مرات ظهور كل كلمة في النص، إذ نستخدم هنا خريطة معماة تحتوي على الكلمات مثل مفاتيح بحيث نزيد قيمة كل كلمة حتى نراقب عدد ظهور كلمة ما، وإذا رأينا الكلمة للمرة الأولى فإننا نضيفها إلى الخريطة بالقيمة 0.

    use std::collections::HashMap;

    let text = "hello world wonderful world";

    let mut map = HashMap::new();

    for word in text.split_whitespace() {
        let count = map.entry(word).or_insert(0);
        *count += 1;
    }

    println!("{:?}", map);

[الشيفرة 25: عدّ عدد مرات ظهور الكلمات باستخدام خريطة معماة تخزّن الكلمة وعدد مرات ظهورها]

ستطبع الشيفرة البرمجية {world": 2, "hello": 1, "wonderful": 1"}.

قد تجد أزواج قيمة/مفتاح متماثلة بترتيب مختلف عن ذلك، لذلك نذكر هنا أننا تكلمنا في الفقرات السابقة وقلنا أن المرور على قيم الخريطة المعماة يكون بترتيب عشوائي.

يُعيد التابع split_whitespace مؤشرًا يشير إلى الشرائح الجزئية ضمن text والمفصول ما بينها بالمسافة، بينما يعيد التابع or_insert مرجعًا قابلًا للتعديل (‎&mut V) إلى قيمة المفتاح المُحدّد، ونخزّن هنا المرجع القابل للتعديل في المتغير count، لذا ومن أجل الإسناد إلى تلك القيمة علينا أولًا أن نُحصّل المتغير count باستخدام رمز النجمة *. تخرج المراجع القابلة للتعديل من النطاق في نهاية الحلقة for، لذا جميع هذه التغييرات آمنة ومسموحة استنادًا لقوانين الاستعارة.

دوال التعمية hashing function

تستخدم الخريطة المعماة HashMap افتراضيًا دالة تعمية hashing function تدعى SipHash، وهي دالة توفر حمايةً لخرائط التعمية ضد هجمات الحرمان من الخدمة Denial of Service -أو اختصارًا DoS- إلا أنها ليست أسرع خوارزميات التعمية المتاحة ولكنها تقدم حمايةً أفضل، والتراجع في السرعة مقابل ذلك يستحقّ المساومة.

إذا راجعت شيفرتك البرمجية ورأيت أن دالة التعمية الاعتيادية بطيئة جدًا مقارنةً بحاجتك، فيمكنك استبدالها بدالة أخرى بتحديد مُعَمّي hasher؛ والمعمّي هو النوع الذي يطبّق السمة BuildHasher وسنناقش السمات بالتفصيل لاحقًا. ليس من الضروري كتابة المعمّي الخاص بك بنفسك، إذ يحتوي crates.io على مكتبات شاركها مستخدمو رست آخرون لتقديم تطبيق معمّي معيّن باستخدام خوارزميات التعمية الشهيرة.

ترجمة -وبتصرف- لقسم من الفصل Common Collections من كتاب The Rust Programming Language.