Rust HashMap: كيفية البحث عن البيانات وإدراجها بكفاءة

كيفية البحث عن البيانات وإدراجها بكفاءة في HashMap باستخدام Rust: نظرة تحت الغطاء

هل سبق لك أن كتبت كودًا بلغة Rust وفكرت: "كيف يمكنني التحقق مما إذا كان المفتاح موجودًا في HashMap، وإذا لم يكن موجودًا، إدراج قيمة جديدة؟" هذا السؤال يؤرق آلاف المطورين على Stack Overflow. وليس من دون سبب: الحل الساذج قد يقتل أداء تطبيقك. اليوم لن نقدم الإجابة فقط - بل سنتعمق داخل Rust HashMap ونرى كيف تعمل. ستتعرف على لماذا استخدام get و insert بشكل منفصل هو طريق للألم، وكيفية استخدام entry API بشكل صحيح.

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

المشكلة: استدعاءان - عمل مضاعف

تخيل مهمة نموذجية: لديك HashMap تحتاج فيها إلى حساب عدد تكرارات الكلمات في نص. يبدو الحل الساذج كالتالي:

use std::collections::HashMap;\n\nfn count_words_naive(words: &[&str]) -> HashMap<String, u32> {\n    let mut map = HashMap::new();\n    \n    for word in words {\n        if map.contains_key(*word) {\n            let count = map.get(*word).unwrap();\n            map.insert(word.to_string(), count + 1);\n        } else {\n            map.insert(word.to_string(), 1);\n        }\n    }\n    \n    map\n}\n

ما المشكلة هنا؟ نحن نصل إلى HashMap مرتين لكل كلمة: أولاً contains_key، ثم get، ثم insert. كل استدعاء يعني حساب التجزئة، البحث في السلة و مقارنة المفاتيح. بالنسبة لنص قصير، هذا غير ملحوظ، ولكن بالنسبة لملايين السجلات، فهي كارثة.

تحت الغطاء: كيف تعمل HashMap في Rust

لفهم لماذا هذا سيء، دعنا نفهم كيف تعمل HashMap في Rust. الأساس هو جدول تجزئة بالعنونة المفتوحة (Robin Hood hashing). إليك النقاط الرئيسية:

\n
• التجزئة: يتم تحويل المفتاح إلى رمز تجزئة باستخدام دالة تجزئة (افتراضيًا SipHash-2-4).
\n
• السلال (buckets): يحدد رمز التجزئة الفهرس في مصفوفة السلال. في Rust، كل سلة هي فتحة يمكن أن تكون فارغة أو مشغولة أو محذوفة.
\n
• التصادمات: عندما يقع مفتاحان مختلفان في نفس السلة، يحاول Robin Hood hashing "سرقة" مكان من الجار "الأكثر ثراءً" لموازنة مسافات البحث.
\n
• إعادة التحجيم: عندما تمتلئ الجدول (عامل التحميل ~0.9)، يتضاعف حجمه، ويتم إعادة تجزئة جميع العناصر.
\n

الآن تخيل: كل استدعاء لـ get أو insert هو دورة كاملة: تجزئة، بحث حسب الفهرس، مقارنة المفاتيح (ربما عدة مرات بسبب التصادمات). استدعاءان = عمل مضاعف. وماذا لو حدثت إعادة تحجيم بين الاستدعاءات؟ عمل ثلاثي!

الحل: Entry API - شريان النجاة الخاص بك

تقدم Rust حلاً أنيقًا - Entry API. هذه آلية تسمح بإجراء البحث وربما الإدراج في تمريرة واحدة. إليك كيف يبدو الكود الصحيح لحساب الكلمات:

use std::collections::HashMap;\n\nfn count_words_efficient(words: &[&str]) -> HashMap<String, u32> {\n    let mut map = HashMap::new();\n    \n    for word in words {\n        let entry = map.entry(word.to_string());\n        *entry.or_insert(0) += 1;\n    }\n    \n    map\n}\n

مختصر، جميل، فعال. ولكن كيف يعمل هذا تحت الغطاء؟ دعنا نحلله خطوة بخطوة.

الخطوة 1: طريقة entry()

استدعاء map.entry(key) يُرجع تعداد Entry، والذي يمكن أن يكون في حالتين:

\n
• Entry::Occupied - المفتاح موجود بالفعل في الجدول.
\n
• Entry::Vacant - المفتاح غير موجود، ولدينا مكان جاهز للإدراج.
\n

هام: في هذه