Хранение ключей со связанными значениями в хэш-картах

Хранение ключей со связанными значениями в HashMap

Последняя коллекция, которую мы рассмотрим, будет hash map (хеш-карта). Тип HashMap<K, V> хранит ключи типа K на значения типа V. Данная структура организует и хранит данные с помощью функции хеширования. Во множестве языков программирования реализована данная структура, но часто с разными наименованиями: такими как hash, map, object, hash table, dictionary или ассоциативный массив.

Хеш-карты полезны, когда нужно искать данные не используя индекс, как это например делается в векторах, а с помощью ключа, который может быть любого типа. Например, в игре вы можете отслеживать счёт каждой команды в хеш-карте, в которой каждый ключ - это название команды, а значение - счёт команды. Имея имя команды, вы можете получить её счёт из хеш-карты.

В этом разделе мы рассмотрим базовый API хеш-карт. Остальной набор полезных функций скрывается в объявлении типа HashMap<K, V>. Как и прежде, советуем обратиться к документации по стандартной библиотеке для получения дополнительной информации.

Создание новой хеш-карты

Создать пустую хеш-карту можно с помощью new, а добавить в неё элементы - с помощью insert. В листинге 8-20 мы отслеживаем счёт двух команд, синей Blue и жёлтой Yellow. Синяя команда набрала 10 очков, а жёлтая команда - 50.

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

    let mut scores = HashMap::new();

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

Листинг 8-20: Создание новой хеш-карты и вставка в неё пары ключей и значений

Обратите внимание, что нужно сначала указать строку use std::collections::HashMap; для её подключения из коллекций стандартной библиотеки. Из трёх коллекций данная является наименее используемой, поэтому она не подключается в область видимости функцией автоматического импорта (prelude). Хеш-карты также имеют меньшую поддержку со стороны стандартной библиотеки; например, нет встроенного макроса для их конструирования.

Подобно векторам, хеш-карты хранят свои данные в куче. Здесь тип HashMap имеет в качестве типа ключей String, а в качестве типа значений тип i32. Как и векторы, HashMap однородны: все ключи должны иметь одинаковый тип и все значения должны иметь тоже одинаковый тип.

Доступ к данным в HashMap

Мы можем получить значение из HashMap по ключу, с помощью метода 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);
}

Листинг 8-21: Доступ к очкам команды "Blue", которые хранятся в хеш-карте

Здесь score будет иметь количество очков, связанное с командой "Blue", результат будет 10. Метод get возвращает Option<&V>; если для какого-то ключа нет значения в HashMap, get вернёт None. Из-за такого подхода программе следует обрабатывать Option, вызывая copied для получения Option<i32> вместо Option<&i32>, затем unwrap_or для установки score в ноль, если scores не содержит данных по этому ключу.

Мы можем перебирать каждую пару ключ/значение в HashMap таким же образом, как мы делали с векторами, используя цикл 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, значения копируются в HashMap. Для значений со владением, таких как 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!
}

Листинг 8-22: Показывает, что ключи и значения находятся во владении HashMap, как только они были вставлены

Мы не можем использовать переменные field_name и field_value после того, как их значения были перемещены в HashMap вызовом метода insert.

Если мы вставим в HashMap ссылки на значения, то они не будут перемещены в HashMap. Значения, на которые указывают ссылки, должны быть действительными хотя бы до тех пор, пока хеш-карта действительна. Мы поговорим подробнее об этих вопросах в разделе "Валидация ссылок при помощи времён жизни" главы 10.

Обновление данных в HashMap

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

Когда вы хотите изменить данные в хеш-карте, необходимо решить, как обрабатывать случай, когда ключ уже имеет назначенное значение. Можно заменить старое значение новым, полностью игнорируя старое. Можно сохранить старое значение и игнорировать новое, или добавлять новое значение, если только ключ ещё не имел значения. Или можно было бы объединить старое значение и новое значение. Давайте посмотрим, как сделать каждый из вариантов!

Перезапись старых значений

Если мы вставим ключ и значение в HashMap, а затем вставим тот же ключ с новым значением, то старое значение связанное с этим ключом, будет заменено на новое. Даже несмотря на то, что код в листинге 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);
}

Листинг 8-23: Замена значения, хранимого в конкретном ключе

Код напечатает {"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);
}

Листинг 8-24: Использование метода entry для вставки значения только в том случае, когда ключ не имеет значения

Метод or_insert определён в Entry так, чтобы возвращать изменяемую ссылку на соответствующее значение ключа внутри варианта перечисления Entry, когда этот ключ существует, а если его нет, то вставлять параметр в качестве нового значения этого ключа и возвращать изменяемую ссылку на новое значение. Эта техника намного чище, чем самостоятельное написание логики и, кроме того, она более безопасна и согласуется с правилами заимствования.

При выполнении кода листинга 8-24 будет напечатано {"Yellow": 50, "Blue": 10}. Первый вызов метода entry вставит ключ для команды "Yellow" со значением 50, потому что для жёлтой команды ещё не имеется значения в HashMap. Второй вызов entry не изменит хеш-карту, потому что для ключа команды "Blue" уже имеется значение 10.

Создание нового значения на основе старого значения

Другим распространённым вариантом использования хеш-карт является поиск значения по ключу, а затем обновление этого значения на основе старого значения. Например, в листинге 8-25 показан код, который подсчитывает, сколько раз определённое слово встречается в некотором тексте. Мы используем HashMap со словами в качестве ключей и увеличиваем соответствующее слову значение, чтобы отслеживать, сколько раз мы встретили это слово. Если мы впервые встретили слово, то сначала вставляем значение 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);
}

Листинг 8-25: Подсчёт количества вхождений слов с использованием хеш-карты, которая хранит слова и счётчики

Этот код напечатает {"world": 2, "hello": 1, "wonderful": 1}. Если вы увидите, что пары ключ/значение печатаются в другом порядке, то вспомните, что мы писали в секции "Доступ к данным в HashMap", что итерация по хеш-карте происходит в произвольном порядке.

Метод split_whitespace возвращает итератор по срезам строки, разделённых пробелам, для строки text. Метод or_insert возвращает изменяемую ссылку (&mut V) на значение ключа. Мы сохраняем изменяемую ссылку в переменной count, для этого, чтобы присвоить переменной значение, необходимо произвести разыменование с помощью звёздочки (*). Изменяемая ссылка удаляется сразу же после выхода из области видимости цикла for, поэтому все эти изменения безопасны и согласуются с правилами заимствования.

Функция хеширования

По умолчанию HashMap использует функцию хеширования SipHash, которая может противостоять атакам класса отказ в обслуживании, Denial of Service (DoS) с использованием хеш-таблиц siphash. Это не самый быстрый из возможных алгоритмов хеширования, в данном случае производительность идёт на компромисс с обеспечением лучшей безопасности. Если после профилирования вашего кода окажется, что хеш-функция, используемая по умолчанию, очень медленная, вы можете заменить её используя другой hasher. Hasher - это тип, реализующий трейт BuildHasher. Подробнее о типажах мы поговорим в Главе 10. Вам совсем не обязательно реализовывать свою собственную функцию хеширования; crates.io имеет достаточное количество библиотек, предоставляющих разные реализации hasher с множеством общих алгоритмов хеширования.

Итоги

Векторы, строки и хеш-карты предоставят большое количество функционала для программ, когда необходимо сохранять, получать доступ и модифицировать данные. Теперь вы готовы решить следующие учебные задания:

Есть список целых чисел. Создайте функцию, используйте вектор и верните из списка: среднее значение; медиану (значение элемента из середины списка после его сортировки); моду списка (mode of list, то значение которое встречается в списке наибольшее количество раз; HashMap будет полезна в данном случае).
Преобразуйте строку в кодировку "поросячьей латыни" (Pig Latin). Первая согласная каждого слова перемещается в конец и к ней добавляется окончание "ay", так "first" станет "irst-fay". Слову, начинающемуся на гласную, в конец добавляется "hay" ("apple" становится "apple-hay"). Помните о деталях работы с кодировкой UTF-8!
Используя хеш-карту и векторы, создайте текстовый интерфейс позволяющий пользователю добавлять имена сотрудников к названию отдела компании. Например, "Add Sally to Engineering" или "Add Amir to Sales". Затем позвольте пользователю получить список всех людей из отдела или всех людей в компании, отсортированных по отделам в алфавитном порядке.

Документация API стандартной библиотеки описывает методы у векторов, строк и HashMap. Рекомендуем воспользоваться ей при решении упражнений.

Потихоньку мы переходим к более сложным программам, в которых операции могут потерпеть неудачу. Наступило идеальное время для обсуждения обработки ошибок.

The Rust Programming Language