The Rust Programming Language

ذخیره کلیدها با مقادیر مرتبط در هش مپ‌ها

آخرین مورد از مجموعه‌های رایج ما، هش مپ است. نوع HashMap<K, V> یک نگاشت از کلیدهایی با نوع K به مقادیری با نوع V را با استفاده از یک تابع هش ذخیره می‌کند، که تعیین می‌کند چگونه این کلیدها و مقادیر در حافظه قرار بگیرند. بسیاری از زبان‌های برنامه‌نویسی از این نوع ساختار داده پشتیبانی می‌کنند، اما اغلب از نام‌های متفاوتی مانند هش، مپ، شیء، جدول هش، دایرکتوری، یا آرایه ارتباطی برای اشاره به آن استفاده می‌کنند.

هش مپ‌ها زمانی مفید هستند که بخواهید داده‌ها را نه با استفاده از یک اندیس، مانند بردارها، بلکه با استفاده از یک کلید که می‌تواند هر نوعی باشد، جستجو کنید. برای مثال، در یک بازی، می‌توانید امتیاز هر تیم را در یک هش مپ ذخیره کنید که هر کلید نام یک تیم و هر مقدار امتیاز آن تیم باشد. با داشتن نام یک تیم، می‌توانید امتیاز آن را بازیابی کنید.

در این بخش، به API اصلی هش مپ‌ها می‌پردازیم، اما امکانات بیشتری در توابع تعریف شده روی HashMap<K, V> در کتابخانه استاندارد وجود دارد. مانند همیشه، مستندات کتابخانه استاندارد را برای اطلاعات بیشتر بررسی کنید.

ایجاد یک هش مپ جدید

یکی از راه‌های ایجاد یک هش مپ خالی استفاده از new و افزودن عناصر با insert است. در لیست ۸-۲۰، ما امتیازات دو تیم به نام‌های Blue و Yellow را پیگیری می‌کنیم. تیم آبی با ۱۰ امتیاز و تیم زرد با ۵۰ امتیاز شروع می‌کنند.

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

    let mut scores = HashMap::new();

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

توجه داشته باشید که ابتدا باید HashMap را از بخش مجموعه‌های کتابخانه استاندارد use کنیم. از میان سه مجموعه رایج ما، این یکی کمتر مورد استفاده قرار می‌گیرد، بنابراین به طور پیش‌فرض در محدوده وارد نمی‌شود. همچنین، هش مپ‌ها از حمایت کمتری از کتابخانه استاندارد برخوردارند؛ برای مثال، هیچ ماکروی داخلی برای ساخت آن‌ها وجود ندارد.

همانند بردارها، هش مپ‌ها داده‌های خود را روی heap ذخیره می‌کنند. این HashMap دارای کلیدهایی از نوع String و مقادیری از نوع i32 است. مانند بردارها، هش مپ‌ها همگن هستند: تمام کلیدها باید از یک نوع باشند و تمام مقادیر نیز باید از یک نوع باشند.

دسترسی به مقادیر در یک هش مپ

می‌توانیم یک مقدار را با ارائه کلید آن به متد get از هش مپ دریافت کنیم، همانطور که در لیست ۸-۲۱ نشان داده شده است.

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);
}

اینجا، مقدار score برابر با مقداری خواهد بود که به تیم Blue مرتبط است، و نتیجه 10 خواهد بود. متد get یک Option<&V> را بازمی‌گرداند؛ اگر هیچ مقداری برای آن کلید در هش مپ وجود نداشته باشد، get مقدار None را بازمی‌گرداند. این برنامه مقدار Option را با فراخوانی copied برای دریافت یک Option<i32> به جای Option<&i32> مدیریت می‌کند، سپس با استفاده از unwrap_or مقدار score را به صفر تنظیم می‌کند اگر scores یک ورودی برای کلید نداشته باشد.

می‌توانیم بر روی هر جفت کلید–مقدار در یک هش مپ مشابه کاری که با بردارها انجام می‌دهیم، با استفاده از یک حلقه for پیمایش کنیم:

fn main() {
    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، مقادیر منتقل شده و هش مپ مالک آن‌ها خواهد شد، همانطور که در لیست ۸-۲۲ نشان داده شده است.

fn main() {
    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 and field_value are invalid at this point, try using them and
    // see what compiler error you get!
}

پس از انتقال متغیرهای field_name و field_value به هش مپ با فراخوانی insert، دیگر نمی‌توانیم از آن‌ها استفاده کنیم.

اگر مراجع به مقادیر را درون هش مپ وارد کنیم، مقادیر به هش مپ منتقل نخواهند شد. مقادیری که مراجع به آن‌ها اشاره می‌کنند باید حداقل تا زمانی که هش مپ معتبر است، معتبر باقی بمانند. درباره این مسائل در بخش “تأیید مراجع با عمرها” در فصل ۱۰ بیشتر صحبت خواهیم کرد.

به‌روزرسانی یک هش مپ

اگرچه تعداد جفت‌های کلید و مقدار قابل افزایش است، هر کلید یکتا فقط می‌تواند یک مقدار مرتبط داشته باشد (اما نه بالعکس: برای مثال، هر دو تیم Blue و Yellow می‌توانند مقدار 10 را در هش مپ scores ذخیره کنند).

وقتی می‌خواهید داده‌ها را در یک هش مپ تغییر دهید، باید تصمیم بگیرید چگونه با حالتی که یک کلید قبلاً دارای مقدار است برخورد کنید. می‌توانید مقدار قدیمی را با مقدار جدید جایگزین کنید و مقدار قدیمی را کاملاً نادیده بگیرید. می‌توانید مقدار قدیمی را نگه دارید و مقدار جدید را نادیده بگیرید، فقط مقدار جدید را اضافه کنید اگر کلید ندارد قبلاً یک مقدار. یا می‌توانید مقدار قدیمی و مقدار جدید را با هم ترکیب کنید. بیایید ببینیم چگونه هر یک از این کارها را انجام دهیم!

بازنویسی یک مقدار

اگر یک کلید و مقدار را به یک هش مپ وارد کنیم و سپس همان کلید را با یک مقدار متفاوت وارد کنیم، مقداری که با آن کلید مرتبط است جایگزین خواهد شد. حتی اگر کد در لیست ۸-۲۳ دوبار insert را فراخوانی کند، هش مپ فقط یک جفت کلید–مقدار را شامل خواهد شد زیرا ما مقدار مرتبط با کلید تیم Blue را در هر دو بار وارد می‌کنیم.

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

    let mut scores = HashMap::new();

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

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

این کد مقدار {"Blue": 25} را چاپ خواهد کرد. مقدار اصلی 10 بازنویسی شده است.

اضافه کردن یک کلید و مقدار فقط اگر کلید وجود ندارد

بررسی اینکه آیا یک کلید خاص در هش مپ دارای مقدار است یا خیر و سپس انجام اقدامات زیر رایج است: اگر کلید در هش مپ وجود دارد، مقدار موجود باید همانطور که هست باقی بماند؛ اگر کلید وجود ندارد، آن را به همراه یک مقدار وارد کنید.

هش مپ‌ها یک API خاص برای این کار دارند که به نام entry شناخته می‌شود و کلیدی که می‌خواهید بررسی کنید را به عنوان پارامتر می‌گیرد. مقدار بازگشتی متد entry یک enum به نام Entry است که نشان‌دهنده مقداری است که ممکن است وجود داشته باشد یا نداشته باشد. فرض کنید می‌خواهیم بررسی کنیم که آیا کلید تیم Yellow دارای مقدار مرتبط است یا خیر. اگر ندارد، می‌خواهیم مقدار 50 را وارد کنیم، و همینطور برای تیم Blue. با استفاده از API entry، کد به شکل لیست ۸-۲۴ خواهد بود.

fn main() {
    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:?}");
}

متد or_insert روی Entry به گونه‌ای تعریف شده است که یک مرجع قابل تغییر به مقدار مرتبط با کلید Entry برمی‌گرداند اگر آن کلید وجود داشته باشد، و اگر نه، پارامتر را به عنوان مقدار جدید برای این کلید وارد کرده و یک مرجع قابل تغییر به مقدار جدید بازمی‌گرداند. این تکنیک بسیار تمیزتر از نوشتن منطق به صورت دستی است و علاوه بر این، با بررسی‌کننده قرض بهتر کار می‌کند.

اجرای کد در لیست ۸-۲۴ مقدار {"Yellow": 50, "Blue": 10} را چاپ خواهد کرد. اولین فراخوانی به entry کلید تیم Yellow را با مقدار 50 وارد می‌کند زیرا تیم Yellow قبلاً مقداری ندارد. دومین فراخوانی به entry هش مپ را تغییر نمی‌دهد زیرا تیم Blue قبلاً مقدار 10 را دارد.

به‌روزرسانی یک مقدار بر اساس مقدار قدیمی

یکی دیگر از موارد استفاده رایج برای هش مپ‌ها این است که مقدار یک کلید را جستجو کرده و سپس بر اساس مقدار قدیمی آن را به‌روزرسانی کنیم. برای مثال، لیست ۸-۲۵ کدی را نشان می‌دهد که تعداد دفعات ظاهر شدن هر کلمه در یک متن را می‌شمارد. ما از یک هش مپ با کلمات به عنوان کلید و مقدار برای نگهداری تعداد دفعات ظاهر شدن هر کلمه استفاده می‌کنیم. اگر این اولین بار باشد که یک کلمه را مشاهده می‌کنیم، ابتدا مقدار 0 را وارد می‌کنیم.

fn main() {
    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:?}");
}

این کد مقدار {"world": 2, "hello": 1, "wonderful": 1} را چاپ خواهد کرد. ممکن است همین جفت‌های کلید–مقدار را به ترتیب دیگری مشاهده کنید: به بخش “دسترسی به مقادیر در یک هش مپ” رجوع کنید که توضیح می‌دهد پیمایش بر روی یک هش مپ به صورت دلخواه انجام می‌شود.

متد split_whitespace یک iterator بر روی زیررشته‌هایی که با فضای خالی جدا شده‌اند از مقدار موجود در text بازمی‌گرداند. متد or_insert یک مرجع قابل تغییر (&mut V) به مقدار مرتبط با کلید مشخص برمی‌گرداند. اگر آن کلید وجود داشته باشد، مقدار بازگشتی همان مقدار موجود است؛ و اگر نه، پارامتر را به عنوان مقدار جدید برای این کلید وارد می‌کند و مرجع قابل تغییر به مقدار جدید را بازمی‌گرداند. در اینجا، ما این مرجع قابل تغییر را در متغیر count ذخیره می‌کنیم، بنابراین برای تخصیص مقدار به آن، باید ابتدا count را با استفاده از عملگر ستاره (*) dereference کنیم. مرجع قابل تغییر در انتهای حلقه for از محدوده خارج می‌شود، بنابراین تمام این تغییرات ایمن هستند و قوانین قرض‌گیری را نقض نمی‌کنند.

توابع هش

به طور پیش‌فرض، HashMap از یک تابع هش به نام SipHash استفاده می‌کند که مقاومت در برابر حملات انکار سرویس (DoS) مربوط به جداول هش¹ را فراهم می‌کند. این سریع‌ترین الگوریتم هش موجود نیست، اما مبادله برای امنیت بهتر با کاهش عملکرد ارزشمند است. اگر کد خود را پروفایل کنید و متوجه شوید که تابع هش پیش‌فرض برای اهداف شما بسیار کند است، می‌توانید با مشخص کردن یک هش‌کننده دیگر آن را تغییر دهید. یک هش‌کننده نوعی است که ویژگی BuildHasher را پیاده‌سازی می‌کند. درباره ویژگی‌ها (traits) و نحوه پیاده‌سازی آن‌ها در فصل ۱۰ صحبت خواهیم کرد. نیازی نیست حتماً هش‌کننده خود را از ابتدا پیاده‌سازی کنید؛ در crates.io کتابخانه‌هایی موجود هستند که توسط کاربران Rust به اشتراک گذاشته شده‌اند و هش‌کننده‌هایی با بسیاری از الگوریتم‌های هش رایج ارائه می‌دهند.

خلاصه

بردارها، رشته‌ها، و هش مپ‌ها مقدار زیادی از قابلیت‌های مورد نیاز برای ذخیره، دسترسی، و تغییر داده‌ها در برنامه‌ها را فراهم می‌کنند. در اینجا چند تمرین وجود دارد که اکنون باید قادر به حل آن‌ها باشید:

1. با داشتن یک لیست از اعداد صحیح، از یک بردار استفاده کرده و میانه (وقتی مرتب‌سازی شود، مقداری که در موقعیت وسط قرار دارد) و مد (مقداری که بیشترین بار ظاهر می‌شود؛ یک هش مپ در اینجا مفید خواهد بود) لیست را بازگردانید.
2. رشته‌ها را به زبان لاتین خوکی تبدیل کنید. اولین صامت هر کلمه به انتهای کلمه منتقل شده و ay به آن اضافه می‌شود، بنابراین first به irst-fay تبدیل می‌شود. کلماتی که با یک حرف صدادار شروع می‌شوند، hay به انتهای آن‌ها اضافه می‌شود (apple به apple-hay تبدیل می‌شود). جزئیات مربوط به کدگذاری UTF-8 را در نظر داشته باشید!
3. با استفاده از یک هش مپ و بردارها، یک رابط متنی ایجاد کنید تا به کاربر امکان اضافه کردن نام کارمندان به یک دپارتمان در شرکت را بدهد؛ برای مثال، “Add Sally to Engineering” یا “Add Amir to Sales”. سپس به کاربر اجازه دهید لیستی از تمام افراد در یک دپارتمان یا تمام افراد در شرکت بر اساس دپارتمان، مرتب شده به صورت حروف الفبا، بازیابی کند.

مستندات API کتابخانه استاندارد متدهایی را که بردارها، رشته‌ها، و هش مپ‌ها دارند و برای این تمرین‌ها مفید خواهند بود توصیف می‌کنند!

ما وارد برنامه‌های پیچیده‌تری شده‌ایم که در آن‌ها عملیات ممکن است با شکست مواجه شوند، بنابراین زمان مناسبی است تا درباره مدیریت خطا صحبت کنیم. این کار را در ادامه انجام خواهیم داد!