Хранение ключей со связанными значениями в 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
HashMap
для её подключения из коллекций стандартной библиотеки. Из трёх коллекций данная является наименее используемой, поэтому она не подключается в область видимости функцией автоматического импорта (prelude). Хеш-карты также имеют меньшую поддержку со стороны стандартной библиотеки; например, нет встроенного макроса для их конструирования.
Подобно векторам, хеш-карты хранят свои данные в куче. Здесь тип HashMap
имеет в качестве типа ключей String
, а в качестве типа значений тип i32
. Как и векторы, HashMap однородны: все ключи должны иметь одинаковый тип и все значения должны иметь тоже одинаковый тип.
Ещё один способ построения хеш-карты - использование метода collect
на векторе кортежей, где каждый кортеж состоит из двух значений (первое может быть представлено как ключ, а второе как значение хеш-карты). Метод collect
собирает данные в несколько типов коллекций, включая HashMap
. Например, если бы у нас были названия команд и начальные результаты в двух отдельных векторах, то мы могли бы использовать метод zip
для создания вектора кортежей, где имя "Blue" спарено с числом 10, и так далее. Тогда мы могли бы использовать метод collect
, чтобы превратить этот вектор кортежей в HashMap, как показано в листинге 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); }
Листинг 8-21. Создание HashMap из списка команд и списка результатов
Здесь нужна аннотация типа HashMap<_, _>
, поскольку с помощью метода collect
данные можно собрать во множество различных структур данных и Rust не знает, в какую именно вы хотите собрать, пока вы не укажете это явно. Для параметров типа ключа и значения, мы используем подчёркивания и Rust может вывести типы, которые хеш содержит на основе типов данных из двух векторов. В листинге 8-21, тип ключа будет String
, а тип значения будет i32
, так же как в листинге 8-20.
Хеш-карты и владение
Для типов, которые реализуют типаж 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 по ключу, с помощью метода get
, как показано в листинге 8-23:
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" сохранённой в HashMap
Здесь score
будет иметь количество очков, связанное с командой "Blue", результат будет Some(&10)
. Результат обёрнут в вариант перечисления Some
потому что get
возвращает Option<&V>
; если для этого ключа нет значения в HashMap, get
вернёт None
. Из-за такого подхода программе следует обрабатывать Option
, например одним из способов, которые мы рассмотрели в Главе 6.
Мы можем перебирать каждую пару ключ/значение в 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
Обновление данных
Хотя количество ключей и значений может увеличиваться в HashMap, каждый ключ может иметь только одно значение, связанное с ним в один момент времени. Когда вы хотите изменить данные в хеш-карте, необходимо решить, как обрабатывать случай, когда ключ уже имеет назначенное значение. Можно заменить старое значение новым, полностью игнорируя старое. Можно сохранить старое значение и игнорировать новое и добавлять новое значение, если только ключ ещё не имел значения. Или можно было бы объединить старое значение и новое значение. Давайте посмотрим, как сделать каждый из вариантов!
Перезапись старых значений
Если мы вставим ключ и значение в HashMap, а затем вставим тот же ключ с новым значением, то старое значение связанное с этим ключом, будет заменено на новое. Даже несмотря на то, что код в листинге 8-24 вызывает insert
дважды, хеш-карта будет содержать только одну пару ключ/значение, потому что мы вставляем значения для одного и того же ключа - ключа команды "Blue".
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. Замена значения, хранимого в конкретном ключе
Код напечатает {"Blue": 25}
. Начальное значение 10
было перезаписано.
Вставка значения только в том случае, когда ключ не имеет значения
Обычно проверяют, имеется ли значение для конкретного ключа и если нет, то значение для него вставляется. Хеш-карты имеют для этого специальный API называемый entry
, который принимает ключ для проверки в качестве входного параметра. Возвращаемое значение метода entry
- это перечисление Entry
, с двумя вариантами: первый представляет значение, которое может существовать, а второй говорит о том, что значение отсутствует. Допустим, мы хотим проверить, имеется ли ключ и связанное с ним значение для команды "Yellow". Если хеш-карта не имеет значения для такого ключа, то мы хотим вставить значение 50. То же самое мы хотим проделать и для команды "Blue". Используем API entry
в коде листинга 8-25.
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. Использование метода entry
для вставки значения только в том случае, когда ключ не имеет значения
Метод or_insert
определён в Entry
так, чтобы возвращать изменяемую ссылку на соответствующее значение ключа внутри варианта перечисления Entry
, когда этот ключ существует, а если его нет, то вставлять параметр в качестве нового значения этого ключа и возвращать изменяемую ссылку на новое значение. Эта техника намного чище, чем самостоятельное написание логики и, кроме того, она более безопасна и согласуется с правилами заимствования.
При выполнении кода листинга 8-25 будет напечатано {"Yellow": 50, "Blue": 10}
. Первый вызов метода entry
вставит ключ для команды "Yellow" со значением 50, потому что для жёлтой команды ещё не имеется значения в HashMap. Второй вызов entry
не изменит хеш-карту, потому что для ключа команды "Blue" уже имеется значение 10.
Создание нового значения на основе старого значения
Другим распространённым вариантом использования хеш-карт является поиск значения по ключу, а затем обновление этого значения на основе старого значения. Например, в листинге 8-26 показан код, который подсчитывает, сколько раз определённое слово появляется в каком-либо тексте. Мы используем HashMap со словами в качестве ключей и увеличиваем соответствующее слову значение, чтобы отслеживать, сколько раз в тексте мы увидели слово. Если мы впервые увидели слово, то сначала вставляем значение 0.
#![allow(unused)] fn main() { {{#rustdoc_include ../listings/ch08-common-collections/listing-08-26/src/main.rs:here}} }
Листинг 8-26. Подсчёт вхождений слов с использованием хеш-карты, которая хранит слова и количество их упоминаний в тексте
Будет напечатано {"world": 2, "hello": 1, "wonderful": 1}
. Метод or_insert
возвращает изменяемую ссылку (&mut V
) на значение ключа. Мы сохраняем изменяемую ссылку в переменной count
. Для того, чтобы присвоить переменной значение, необходимо произвести разыменование с помощью звёздочки (*
). Изменяемая ссылка удаляется сразу же после выхода из области видимости цикла for
. Все эти изменения безопасны и согласуются с правилами заимствования.
Функция хэширования
По умолчанию HashMap
использует "криптографически сильную" функцию хэширования SipHash, которая может противостоять атакам класса отказ в обслуживании, Denial of Service (DoS). Это не самый быстрый из возможных алгоритмов хеширования, в данном случае производительность идёт на компромисс с обеспечением лучшей безопасности. Если после профилирования вашего кода окажется, что хэш функция используемая по умолчанию очень медленная, вы можете заменить её используя другой 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. Рекомендуем воспользоваться ей при решении упражнений.
Потихоньку мы переходим к более сложным программам, в которых операции могут потерпеть неудачу. Наступило идеальное время для обсуждения обработки ошибок.