Хешмапа у

Про концепцію Хешмапа

HashMap - це контейнер, який можна використовувати для зберігання пар ключ-значення. В інших мовах програмування цю структуру даних іноді називають асоціативним масивом або хеш-таблицею. Мапа містить набір ключів, кожен з яких зіставлено з певним значенням. Користувач може отримати збережене значення, передавши відповідний ключ. Користувачі також можуть додавати й видаляти ключі та повʼязані з ними значення.

HashMap - це узагальнена колекція (як і більшість колекцій у стандартній бібліотеці), тому як ключі вона підтримує найрізноманітніші типи, зокрема визначені користувачем структури та кортежі. Її значення можуть мати будь-який тип.

Створення HashMap

HashMap створюють за допомогою функції HashMap::new(). Наведений нижче фрагмент коду створює HashMap, у якому назвам команд зіставлено їхній рахунок.

use std::collections::HashMap;

let mut scores = HashMap::new();

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

Доступ до значень у HashMap

Якщо ми знаємо, що значення є в HashMap, то доречно скористатися оператором індексації ([]). Наприклад, щоб отримати рахунок команди Blue, можна використати scores["Blue"]. Однак, якщо відповідної пари ключ-значення в мапі немає, ця операція призведе до паніки.

Крім оператора індексації, є ще два способи отримати доступ до значень, збережених у HashMap. Перший спосіб - скористатися функцією-членом get:

if let Some(blue_score) = scores.get("Blue") {
    println!("Blue scored: {blue_score} \n");
}

get дає доступ до значення, збереженого за запитаним ключем. Він повертає None, якщо переданого ключа немає в HashMap, і Some(value), якщо ключ існує. Докладніше про Options у Rust можна дізнатися з концепту Options.

Інший спосіб отримати доступ до значень, збережених у HashMap, - скористатися методом entry. Метод entry (або entry API) повертає посилання на запис пари ключ-значення в HashMap. Цей запис відображає стан цього ключа в хеші. Якщо ключа немає, то в записі немає значення (і це дає змогу вставити його).

let mut vote_counter: HashMap<_, usize> = HashMap::new();
let votes = ["Blue", "Red", "Red", "Blue", "Red", "Blue", "Blue"];
for vote in votes {
    let count = vote_counter.entry(vote).or_default();
    *count += 1;
}

println!("{vote_counter:#?}");

Цей API робить деякі поширені способи доступу дуже зручними; йому присвячено цілий концепт (Entry API).

Ефективність

HashMap доволі швидкий і має амортизовану складність сталого часу (O(1)) для всіх операцій з одним ключем.

Обмеження трейтів

HashMap - це узагальнена структура даних: вона підтримує довільні типи як ключі та значення, але з одним обмеженням: щоб тип можна було використовувати як тип ключа, він повинен мати реалізацію двох трейтів: Eq і Hash. На тип значення жодних обмежень трейтів немає.