Хранение ключей со связанными значениями в хеш-картах
Последняя из наших общих коллекций — это хеш-карта. Тип 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 из части коллекций стандартной библиотеки. Из наших трёх общих коллекций эта используется реже всего, поэтому она не включена в функциональность, автоматически импортируемую в прелюдию. Хеш-карты также имеют меньшую поддержку со стороны стандартной библиотеки; например, для них нет встроенного макроса для конструирования.
Как и векторы, хеш-карты хранят свои данные в куче. Эта 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 и field_value здесь недействительны; попробуйте использовать их и
// посмотрите, какую ошибку компилятора вы получите!
}
Мы не можем использовать переменные field_name и field_value после того, как они были перемещены в хеш-карту вызовом insert.
Если мы вставляем в хеш-карту ссылки на значения, значения не будут перемещены в хеш-карту. Значения, на которые указывают ссылки, должны быть действительны как минимум столько же, сколько действительна хеш-карта. Мы поговорим больше об этих вопросах в разделе «Проверка ссылок с помощью времён жизни» главы 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:?}");
}
entry для вставки, только если ключ ещё не имеет значенияМетод 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, предоставляющие хешеры, реализующие многие распространённые алгоритмы хеширования.
Итоги
Векторы, строки и хеш-карты обеспечат большой объём функциональности, необходимой в программах, когда нужно хранить, получать доступ и изменять данные. Вот несколько упражнений, которые вы теперь готовы решить:
- Дан список целых чисел. Используйте вектор, чтобы вернуть медиану (при сортировке значение в средней позиции) и моду (значение, которое встречается чаще всего; здесь будет полезна хеш-карта) списка.
- Преобразуйте строки в поросячью латынь. Первая согласная каждого слова перемещается в конец слова и добавляется ay, поэтому first становится irst-fay. Слова, начинающиеся с гласной, вместо этого получают hay, добавленное в конец (apple становится apple-hay). Помните о деталях кодировки UTF-8!
- Используя хеш-карту и векторы, создайте текстовый интерфейс, позволяющий пользователю добавлять имена сотрудников в отдел компании; например, «Добавить Салли в Инженерию» или «Добавить Амира в Продажи». Затем позвольте пользователю получить список всех людей в отделе или всех людей в компании по отделам, отсортированный по алфавиту.
Документация API стандартной библиотеки описывает методы, которые есть у векторов, строк и хеш-карт, и которые будут полезны для этих упражнений!
Мы переходим к более сложным программам, в которых операции могут завершаться неудачей, поэтому это идеальное время, чтобы обсудить обработку ошибок. Мы сделаем это далее!