Хеш-таблицы: ключи и значения
Последняя из наших основных коллекций — хеш-таблица. Тип HashMap<K, V>
хранит соответствие ключей типа K значениям типа V и использует для этого
хеш-функцию, которая определяет, как ключи и значения размещаются в памяти.
Такая структура данных есть во многих языках, но называется по-разному: hash,
map, object, hash table, dictionary (словарь) или associative array
(ассоциативный массив) — и это далеко не всё.
Хеш-таблицы удобны, когда данные нужно искать не по индексу, как в векторе, а по ключу, который может быть любого типа. Например, в игре можно хранить счёт каждой команды в хеш-таблице, где ключ — название команды, а значение — её счёт. Зная название команды, можно получить её счёт.
В этом разделе мы рассмотрим основной 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);
}Обратите внимание: сначала нужно подключить HashMap через use из раздела
коллекций стандартной библиотеки. Из трёх наших основных коллекций эта
используется реже всего, поэтому её нет среди того, что прелюдия
автоматически подключает в область видимости. Да и поддержки в стандартной
библиотеке у хеш-таблиц меньше: например, нет встроенного макроса для их
создания.
Как и векторы, хеш-таблицы хранят данные в куче. У этой 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 получит значение, связанное с синей командой, — то есть 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 уже недействительны; попробуйте их
// использовать и посмотрите, какую ошибку выдаст компилятор!
}После того как вызов insert переместил переменные field_name и
field_value в хеш-таблицу, пользоваться ими уже нельзя.
Если вставлять в хеш-таблицу ссылки на значения, сами значения в неё перемещаться не будут. Но значения, на которые указывают ссылки, должны оставаться действительными как минимум столько же, сколько и хеш-таблица. Подробнее об этом мы поговорим в разделе «Проверка ссылок с помощью времён жизни» главы 10.
Изменение хеш-таблицы
Количество пар «ключ — значение» может расти, но с каждым уникальным ключом в
каждый момент связано только одно значение (обратное неверно: например, и у
синих, и у жёлтых в хеш-таблице scores может храниться значение 10).
Когда нужно поменять данные в хеш-таблице, приходится решить, что делать, если у ключа уже есть значение. Можно заменить старое значение новым, совсем не обращая внимания на старое. Можно оставить старое и проигнорировать новое, добавляя новое значение, только если у ключа значения ещё нет. А можно объединить старое значение с новым. Посмотрим, как сделать каждое из этого!
Перезапись значения
Если вставить в хеш-таблицу ключ со значением, а потом вставить тот же ключ с
другим значением, значение, связанное с ключом, будет заменено. Хотя код в
листинге 8-23 вызывает insert дважды, в хеш-таблице окажется только одна
пара «ключ — значение»: оба раза мы вставляем значение для ключа синей
команды.
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, представляющее значение, которое может существовать, а
может и нет. Допустим, мы хотим проверить, есть ли значение у ключа жёлтой
команды. Если нет — вставить значение 50; то же самое для синей команды. С
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 устроен так: если ключ существует, он возвращает
изменяемую ссылку на значение этого ключа; если нет — вставляет свой параметр
как новое значение для ключа и возвращает изменяемую ссылку на это новое
значение. Это куда чище, чем писать такую логику самим, да и с анализатором
заимствований так ладить проще.
Код из листинга 8-24 выведет {"Yellow": 50, "Blue": 10}. Первый вызов
entry вставит ключ жёлтой команды со значением 50, потому что значения у
жёлтых ещё нет. Второй вызов entry хеш-таблицу не изменит: у синих уже есть
значение 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. Это не самый быстрый алгоритм
хеширования, но выигрыш в безопасности стоит потери в производительности. Если
вы профилируете код и обнаружите, что хеш-функция по умолчанию для ваших
задач слишком медленная, можно переключиться на другую, указав другой
хешер (hasher) — тип, реализующий трейт BuildHasher. О трейтах и о том,
как их реализовывать, мы поговорим в главе 10. Писать
свой хешер с нуля не обязательно: на crates.io есть библиотеки от других пользователей Rust с хешерами для многих
распространённых алгоритмов хеширования.
Итоги
Векторы, строки и хеш-таблицы покрывают большую часть того, что нужно программам, когда данные надо хранить, получать и изменять. Вот несколько упражнений, с которыми вы теперь справитесь:
- Дан список целых чисел. С помощью вектора найдите медиану (значение, которое окажется посередине после сортировки) и моду (значение, которое встречается чаще всего; здесь пригодится хеш-таблица).
- Переведите строки на «поросячью латынь» (Pig Latin). Первая согласная каждого слова переносится в конец слова, и к ней добавляется ay: first превращается в irst-fay. К словам, которые начинаются с гласной, в конец добавляется hay (apple превращается в apple-hay). Не забывайте про особенности кодировки UTF-8!
- С помощью хеш-таблицы и векторов сделайте текстовый интерфейс, через который пользователь может добавлять сотрудников в отделы компании: например, «Add Sally to Engineering» или «Add Amir to Sales». Затем дайте пользователю возможность получить список всех сотрудников отдела или всех сотрудников компании по отделам, отсортированный по алфавиту.
В документации по API стандартной библиотеки описаны методы векторов, строк и хеш-таблиц, которые пригодятся для этих упражнений!
Мы переходим к более сложным программам, в которых операции могут завершаться неудачей, — самое время поговорить об обработке ошибок. Этим мы и займёмся!