Введение
Добро пожаловать в раздел Хранение ключей с ассоциированными значениями в хеш - таблицах (hash maps). Этот практикум является частью Rust Book. Вы можете практиковать свои навыки программирования на Rust в LabEx.
В этом практикуме мы рассмотрим концепцию хеш - таблиц (hash maps) и узнаем, как их можно использовать для хранения ключей с ассоциированными значениями.
Хранение ключей с ассоциированными значениями в хеш - таблицах (hash maps)
Последней из наших общих коллекций является хеш - таблица (hash map). Тип HashMap<K, V> хранит соответствие между ключами типа K и значениями типа V с использованием хеш - функции, которая определяет, как эти ключи и значения помещаются в память. Многие языки программирования поддерживают такой тип структуры данных, но они часто называют его по - другому, например, хеш (hash), отображение (map), объект (object), хеш - таблица (hash table), словарь (dictionary) или ассоциативный массив (associative array) и так далее.
Хеш - таблицы полезны, когда вы хотите искать данные не по индексу, как это можно сделать с векторами, а по ключу, который может быть любого типа. Например, в игре вы можете отслеживать счет каждой команды в хеш - таблице, где каждый ключ - это название команды, а значения - счет каждой команды. Указав название команды, вы можете получить ее счет.
В этом разделе мы рассмотрим базовый API хеш - таблиц, но в функциях, определенных для HashMap<K, V> в стандартной библиотеке, скрыто еще много полезных возможностей. Как всегда, для получения более подробной информации обратитесь к документации стандартной библиотеки.
Создание новой хеш - таблицы (hash map)
Один из способов создать пустую хеш - таблицу - использовать метод new и добавлять элементы с помощью метода insert. В листинге 8 - 20 мы отслеживаем очки двух команд с названиями Blue и Yellow. Команда Blue начинает с 10 очков, а команда Yellow - с 50.
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 из раздела коллекций стандартной библиотеки. Из наших трех общих коллекций эта - наименее часто используемая, поэтому она не включается в набор функций, автоматически импортируемых в область видимости в прелюдии. Хеш - таблицы также имеют меньшую поддержку со стороны стандартной библиотеки; например, нет встроенной макроса для их создания.
Как и векторы, хеш - таблицы хранят свои данные в куче. Эта хеш - таблица HashMap имеет ключи типа String и значения типа i32. Как и векторы, хеш - таблицы однородны: все ключи должны иметь один и тот же тип, и все значения также должны иметь один и тот же тип.
Получение значений из хеш - таблицы (hash map)
Мы можем получить значение из хеш - таблицы, передав его ключ методу get, как показано в листинге 8 - 21.
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>; если в хеш - таблице нет значения для данного ключа, метод get вернет None. Эта программа обрабатывает Option, вызывая метод copied для получения Option<i32> вместо Option<&i32>, а затем unwrap_or для установки значения score равным нулю, если в scores нет записи для данного ключа.
Мы можем перебирать каждую пару ключ - значение в хеш - таблице аналогично тому, как мы это делаем с векторами, используя цикл for:
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
Хеш - таблицы и владение (Ownership)
Для типов, реализующих трейт Copy, таких как i32, значения копируются в хеш - таблицу. Для значений с собственностью, таких как String, значения перемещаются, и хеш - таблица становится владельцем этих значений, как показано в листинге 8 - 22.
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: Демонстрация того, что ключи и значения принадлежат хеш - таблице после их вставки
Мы не можем использовать переменные field_name и field_value после того, как они были перемещены в хеш - таблицу при вызове метода insert.
Если мы вставляем ссылки на значения в хеш - таблицу, значения не будут перемещены в хеш - таблицу. Значения, на которые ссылаются ссылки, должны быть действительными как минимум столько же времени, сколько действительна хеш - таблица. Мы более подробно поговорим об этих вопросах в разделе "Проверка ссылок с помощью времени жизни (Validating References with Lifetimes)".
Обновление хеш - таблицы (hash map)
Хотя количество пар ключ - значение в хеш - таблице может увеличиваться, каждый уникальный ключ может иметь только одно значение, связанное с ним в каждый момент времени (но не наоборот: например, и команда Blue, и команда Yellow могут иметь значение 10, хранящееся в хеш - таблице scores).
Когда вы хотите изменить данные в хеш - таблице, вам нужно решить, как обрабатывать случай, когда для ключа уже есть назначенное значение. Вы можете заменить старое значение новым, полностью игнорируя старое. Вы можете сохранить старое значение и проигнорировать новое, добавив новое значение только в том случае, если для данного ключа еще нет значения. Или вы можете объединить старое и новое значения. Давайте посмотрим, как сделать каждую из этих операций!
Перезапись значения
Если мы вставляем ключ и значение в хеш - таблицу, а затем вставляем тот же ключ с другим значением, то значение, связанное с этим ключом, будет заменено. Несмотря на то, что код в листинге 8 - 23 вызывает метод insert дважды, хеш - таблица будет содержать только одну пару ключ - значение, потому что мы вставляем значение для ключа команды Blue оба раза.
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 представляет собой перечисление (enum) под названием Entry, которое представляет собой значение, которое может существовать или не существовать. Предположим, что мы хотим проверить, есть ли у ключа для команды Yellow связанное с ним значение. Если нет, мы хотим вставить значение 50, и то же самое для команды Blue. Используя API entry, код выглядит как в листинге 8 - 24.
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, если этот ключ существует, и если нет, он вставляет переданный параметр в качестве нового значения для этого ключа и возвращает изменяемую ссылку на новое значение. Этот подход намного чище, чем написание такой логики самостоятельно, и, кроме того, лучше работает с механизмом проверки заимствования (borrow checker).
При запуске кода из листинга 8 - 24 будет выведено {"Yellow": 50, "Blue": 10}. Первый вызов entry вставит ключ для команды Yellow со значением 50, потому что у команды Yellow еще нет значения. Второй вызов entry не изменит хеш - таблицу, потому что у команды Blue уже есть значение 10.
Обновление значения на основе старого значения
Другой распространенный случай использования хеш - таблиц (hash maps) - это поиск значения по ключу и его обновление на основе старого значения. Например, в листинге 8 - 25 показан код, который подсчитывает, сколько раз каждое слово встречается в некотором тексте. Мы используем хеш - таблицу, где ключами являются слова, и увеличиваем значение, чтобы отслеживать, сколько раз мы встретили это слово. Если это первое появление слова, мы сначала вставим значение 0.
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}. Возможно, вы увидите те же пары ключ - значение, выведенные в другом порядке: помните, что из раздела "Доступ к значениям в хеш - таблице" итерирование по хеш - таблице происходит в произвольном порядке.
Метод split_whitespace возвращает итератор по подстрокам, разделенным пробелами, в значении переменной text. Метод or_insert возвращает изменяемую ссылку (&mut V) на значение для указанного ключа. Здесь мы сохраняем эту изменяемую ссылку в переменной count, поэтому, чтобы присвоить новое значение, мы должны сначала разыменовать count с помощью звездочки (*). Изменяемая ссылка выходит из области видимости в конце цикла for, поэтому все эти изменения безопасны и разрешены правилами заимствования (borrowing rules).
Хэш - функции (Hashing functions)
По умолчанию HashMap использует хэш - функцию под названием SipHash, которая обеспечивает устойчивость против атак отказа в обслуживании (DoS - denial - of - service), связанных с хэш - таблицами. Это не самая быстрая доступная хэш - функция, но компромисс между улучшением безопасности и снижением производительности стоит того. Если вы профилируете свой код и обнаружите, что хэш - функция по умолчанию слишком медленная для ваших целей, вы можете переключиться на другую функцию, указав другой хэшер (hasher). Хэшер - это тип, который реализует трейт (trait) BuildHasher. Мы поговорим о трейтах и о том, как их реализовывать, в главе 10. Вам не обязательно реализовывать собственный хэшер с нуля; на https://crates.io есть библиотеки, предоставляемые другими пользователями Rust, которые содержат хэшеры, реализующие многие распространенные хэш - алгоритмы.
Итоги
Поздравляем! Вы завершили лабораторную работу "Сохранение ключей с связанными значениями в хэш - таблицах" (Storing Keys With Associated Values in Hash Maps). Вы можете попрактиковаться в других лабораторных работах в LabEx, чтобы улучшить свои навыки.