Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Зберігання ключів із пов’язаними значеннями в хеш-мапах (Storing Keys with Associated Values in Hash Maps)

Останньою з наших загальних колекцій є хеш-мапа. Тип HashMap<K, V> зберігає відображення ключів типу K у значення типу V, використовуючи функцію хешування, яка визначає, як вона розміщує ці ключі та значення в пам’яті. Багато мов програмування підтримують цей вид структури даних, але вони часто використовують іншу назву, наприклад hash, map, object, hash table, dictionary або associative array, щоб назвати лише деякі.

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

У цьому розділі ми розглянемо базовий API хеш-мап, але багато інших переваг приховано у функціях, визначених для HashMap<K, V> стандартною бібліотекою. Як завжди, дивіться документацію стандартної бібліотеки для отримання додаткової інформації.

Створення нової хеш-мапи

Один зі способів створити порожню хеш-мапу — це використати new і додавати елементи за допомогою insert. У Лістингу 8-20 ми відстежуємо рахунки двох команд, чиї назви — Blue та Yellow. Команда Blue починає з 10 очок, а команда Yellow починає з 50.

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

    let mut scores = HashMap::new();

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

Зверніть увагу, що спочатку нам потрібно use HashMap із розділу колекцій стандартної бібліотеки. Із наших трьох загальних колекцій ця використовується найрідше, тому вона не входить до можливостей, які автоматично підключаються в область видимості в prelude. Хеш-мапи також мають меншу підтримку з боку стандартної бібліотеки; наприклад, для їх створення немає вбудованого макроса.

Так само, як і вектори, хеш-мапи зберігають свої дані в купі. Ця HashMap має ключі типу String і значення типу i32. Як і вектори, хеш-мапи є однорідними: усі ключі мають мати той самий тип, і всі значення мають мати той самий тип.

Доступ до значень у хеш-мапі

Ми можемо отримати значення з хеш-мапи, передавши її ключ у метод get, як показано у Лістингу 8-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);
}

Тут 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, значення будуть переміщені, і хеш-мапа буде володільцем цих значень, як показано у Лістингу 8-22.

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.

Якщо ми вставляємо посилання на значення в хеш-мапу, значення не будуть переміщені в хеш-мапу. Значення, на які вказують посилання, мають бути дійсними протягом принаймні такого самого часу, як і хеш-мапа. Ми ще поговоримо про ці питання в “Validating References with Lifetimes” у Розділі 10.

Оновлення хеш-мапи

Хоча кількість пар ключів і значень може збільшуватися, кожен унікальний ключ може мати лише одне значення, пов’язане з ним, у певний момент часу (але не навпаки: наприклад, і команда Blue, і команда Yellow могли б мати значення 10, збережене в хеш-мапі scores).

Коли ви хочете змінити дані в хеш-мапі, ви маєте вирішити, як обробити випадок, коли ключ уже має призначене значення. Ви можете замінити старе значення новим, повністю ігноруючи старе значення. Ви можете залишити старе значення та ігнорувати нове, додаючи нове значення лише якщо ключ не вже має значення. Або ви можете поєднати старе значення і нове значення. Давайте подивимося, як зробити кожен із цих варіантів!

Перезапис значення

Якщо ми вставляємо ключ і значення в хеш-мапу, а потім вставляємо той самий ключ з іншим значенням, значення, пов’язане з цим ключем, буде замінено. Хоча код у Лістингу 8-23 двічі викликає 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, — це перелічення під назвою Entry, який представляє значення, яке може існувати або не існувати. Припустімо, ми хочемо перевірити, чи має ключ для команди Yellow пов’язане з ним значення. Якщо ні, ми хочемо вставити значення 50, і те саме для команди Blue. Використовуючи API entry, код виглядає як у Лістингу 8-24.

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, якщо цей ключ існує, а якщо ні, він вставляє параметр як нове значення для цього ключа і повертає змінне посилання на нове значення. Ця техніка набагато чистіша, ніж написання логіки самостійно, і, крім того, краще узгоджується з перевірником запозичень.

Запуск коду у Лістингу 8-24 надрукує {"Yellow": 50, "Blue": 10}. Перший виклик entry вставить ключ для команди Yellow зі значенням 50, тому що команда Yellow уже не має значення. Другий виклик entry не змінить хеш-мапу, тому що команда Blue уже має значення 10.

Оновлення значення на основі старого значення

Інший поширений випадок використання хеш-мап — це пошук значення ключа, а потім оновлення його на основі старого значення. Наприклад, у Лістингу 8-25 показано код, який підраховує, скільки разів кожне слово з’являється в певному тексті, використовуючи хеш-мапу, де ключі — це слова, а значення — це кількість входжень для цього слова. Якщо це перший раз, коли ми бачимо слово, ми спочатку вставимо значення 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 повертає ітератор по підзрізах, розділених пробільними символами, значення в text. Метод or_insert повертає змінне посилання (&mut V) на значення для вказаного ключа. Тут ми зберігаємо це змінне посилання в змінній count, тож щоб присвоїти це значення, ми спочатку маємо розіменувати count за допомогою зірочки (*). Змінне посилання виходить з області видимості наприкінці циклу for, тому всі ці зміни є безпечними й дозволеними правилами запозичення.

Функції хешування

За замовчуванням HashMap використовує функцію хешування під назвою SipHash, яка може забезпечити захист від атак відмови в обслуговуванні (DoS), пов’язаних із хеш-таблицями1. Це не найшвидший доступний алгоритм хешування, але компроміс заради кращої безпеки, який супроводжується падінням продуктивності, того вартий. Якщо ви профілюєте свій код і виявите, що типова функція хешування занадто повільна для ваших потреб, ви можете переключитися на іншу функцію, вказавши інший хешер. Хешер — це тип, який реалізує трейт BuildHasher. Ми поговоримо про трейти та про те, як їх реалізовувати, у Розділі 10. Вам не обов’язково реалізовувати власний хешер з нуля; crates.io має бібліотеки, якими діляться інші користувачі Rust і які надають хешери, що реалізують багато поширених алгоритмів хешування.

Підсумок

Вектори, рядки та хеш-мапи надають велику кількість функціональності, необхідної в програмах, коли вам потрібно зберігати, отримувати доступ і змінювати дані. Ось кілька вправ, які тепер ви маєте змогу розв’язати:

  1. Маючи список цілих чисел, використайте вектор і поверніть медіану (після сортування значення в серединній позиції) і моду (значення, яке трапляється найчастіше; тут буде корисною хеш-мапа) списку.
  2. Перетворіть рядки на Pig Latin. Першу приголосну кожного слова переміщено в кінець слова, і додається ay, тож first стає irst-fay. Слова, що починаються з голосної, натомість отримують додане в кінці hay (apple стає apple-hay). Пам’ятайте про деталі кодування UTF-8!
  3. Використовуючи хеш-мапу та вектори, створіть текстовий інтерфейс, щоб дозволити користувачу додавати імена працівників до відділу в компанії; наприклад, “Add Sally to Engineering” або “Add Amir to Sales.” Потім дозвольте користувачу отримати список усіх людей у відділі або всіх людей у компанії за відділами, відсортований за абеткою.

Документація API стандартної бібліотеки описує методи, які мають вектори, рядки та хеш-мапи, і які будуть корисні для цих вправ!

Ми переходимо до складніших програм, у яких операції можуть зазнавати збоїв, тож це ідеальний час, щоб обговорити обробку помилок. Далі ми зробимо саме це!

  1. https://en.wikipedia.org/wiki/SipHash ↩