Hash Maps
Последняя коллекция, которую мы рассмотрим в нашей книге будет hash map.
HashMap<K, V> сохраняет ключи типа K и значения типа V. Данная структура организует и хранит данные
с помощью функции хэширования. Во множестве библиотек языков программирования
реализована данная структура и функционал. Все они, что неудивительно, имеют разные
наименования: hash, map, object, hash table, или ассоциированный массив.
Использование HashMap<K, V> удобно, когда доступ к элементам структуры необходимо
осуществлять по ключу (который может иметь любой тип). Например, в игре, вы можете
сохранять счет игроков в хэше, где имя игрока - это ключ, значение - счёт. По имени
игрока вы можете получить его счёт.
В этой главе мы рассмотрим только основные возможности API HashMap. Более подробную информацию вы можете получить в документации.
Создание нового HashMap<K, V>
С помощью метода new можно создать новый HashMap<K, V>. Метод insert
предназначен для добавления элементов.
Пример:
use std::collections::HashMap; fn main() { let mut scores = HashMap::new(); scores.insert(String::from("Blue"), 10); scores.insert(String::from("Yellow"), 50); println!("{:?}", scores); }
Обратите внимание на необходимость импорта HashMap. Эта коллекция не имеет
создающего макроса.
Также как и вектор, данные хранятся в куче. Также как и вектор HashMap имеет
однародную структуру.
Ещё один способ создания HashMap, использование метода вектора кортежей collect,
где каждый кортеж содержит ключ и его значение. Этот метод может объединять любые
типы данных, даже HashMap. Например, если у нас есть список команд и значения
счёта этих команд в двух различных векторах, мы можем использовать метод zip,
чтобы создать вектор кортежей где элементы с одинаковыми индексами образуют пары
"ключ-значение". Далее, мы можем использовать метод collect для создания `HashMap:
use std::collections::HashMap; fn main() { use std::collections::HashMap; let teams = vec![String::from("Blue"), String::from("Yellow")]; let initial_scores = vec![10, 50]; let scores: HashMap<_, _> = teams.iter().zip(initial_scores.iter()).collect(); println!("{:?}", scores); }
Такой необычный тип данных HashMap<_, _> необходим, т.к. метод collect может
содержать данные разных типов и Rust не может заранее проверить их соответствие.
Владение
Для типов данных, которые реализовали поведение Copy, значения копируются в хэш:
use std::collections::HashMap; fn main() { 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 println!("{:?}", map); }
После внесения данные в хэш строковые переменные уже не действительны. Если так случается, что в хэш вносятся ссылки, значение этих ссылочных данных должно быть действительным до конца срока жизни хэша. Более подробно об этом мы поговорим в главе 10.
Доступ к данным
Для получения данных из HashMap используется метод get:
use std::collections::HashMap; fn main() { 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); println!("{} {:?}", team_name, score); }
Здесь установлено соответствие Blue значению score. В результате выборки данных
по ключу мы получим Some(&10). Результат содержится в Some, т.к. get
возвращает Option<&V>. Если данные не были найдены, то возвращается None.
Обход данных (пар "ключ-значение") в хэш:
use std::collections::HashMap; fn main() { 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
Обновление данных
В то время, как количество ключей и значений растёт, каждый уникальный ключ может иметь только одно значение, ассоциированное с ним. Если вы хотите изменить это значение, вы должны решить каким образом это лучше сделать. Можно заменить старое значение на новое, вы можете оставлять старое и игнорировать новое, добавляя только новые значения. Или вы можете комбинировать старые и новые значения.
Перезаписывание старых данных
Если мы внесём ключ и значение в хэш, а потом внесём этот же ключ с другим значением,
значение замениться. Несмотря на то, что метод insert вызывается дважды, сохраняется
только одна пара "ключ-значение":
use std::collections::HashMap; fn main() { let mut scores = HashMap::new(); scores.insert(String::from("Blue"), 10); scores.insert(String::from("Blue"), 25); println!("{:?}", scores); }
Будет напечатано {"Blue": 25}. Первое значение 10 будет перезаписано.
Внесение данных в хэш, только если нет данных
Весьма часто необходимо знать присвоено ли определенному ключу какое-либо значение.
Если не присвоено - привязать к этому ключу значение. HashMap имеет специальную
API для этой цели - entry, которая получает ключ в качестве аргумента. Результатом
работы этой функции является значение перечисления Entry. Давайте проверим есть
ли значени по ключу Yellow:
use std::collections::HashMap; fn main() { 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); }
Метод or_insert перечисления Entry возвращает значение ключа Entry если он
существует, и если он не существует, сохраняет новое значение. Этот метод весьма
удобен.
Результат - будет напечатано {"Yellow": 50, "Blue": 10}.
Обновление значения основанное на предыдущих данных
Ещё один весьма распространённый способ использования хэш, это поиск значений основанных на предыдущем. К примеру, если вы хотите посчитать сколько раз слово встречается в тексте, вы можете использовать хэш со словом в качестве ключа и увеличивать на единицу каждый раз, когда вы будете встречать это слово.
use std::collections::HashMap; fn main() { 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}. Метод or_insert
возвращает изменяемую ссылку (&mut V) по ключу. Мы сохраняем изменяемую ссылку
в переменной count. Для того, чтобы присвоить переменной значение, необходимо
произвести разименование с помощью звёздочки (*). Изменяемая ссылка удаляется
сразу же после выхода из области видимости цикла for. Все эти изменения безопасны
и согласуются с правилами заимствования.
Функция хэширования
По умолчанию HashMap использует криптографическую защитную функцию, которая может
противостоять DOS-атакам. В этой реализации используется не самый быстрый алгоритм
хэширования, но достаточно защищенный. Если после профилирования вашего кода окажется,
что хэш функция очень медленная, вы можете её заменить на другую подобную функцию
(hasher). Эта функция реализует поведение BuildHasher. Подробнее о поведении
вы узнаете в главе 10. Вам совсем не обязательно реализовывать свою собственную функцию
хэширования. crates.io имеет достаточное количество библиотек для этих целей.
Summary
Векторы, строки и хэш-карты помогают вам, когда необходимо сохранять, получать доступ и модифицировать данные. Для закрепления рассмотренного материала, пожалуйста, выполните следующие учебные задания:
- Есть список целых чисел. Создайте функцию, входной параметр, которой вектор и возвращает: среднее; медиану (значение центрального элемента списка); значение, которое есть в списке набольшее количество раз.
- Сконвертируюйте строку в Pig Latin, где первая согласная каждого слова перемещается в конец и добавлением окончания “ay”. Пример, “first” - “irst-fay”. Если слово начинается на гласную, добавляет в конец слова суффикс “hay”. Пример, “apple” - “apple-hay”.
- Используя хэш мапы и векторы, создайте программу, позволяющую принимать текстовые данные и хранить структуры информации. Необходимо иметь возможность вводить имя работника в отдел компании. Например, добавьте Александра в отдел инжиниринга, добавьте Эмира в отдел продаж. Далее предоставьте возможность получить список всех введенных работников. Отсортируйте эти данные в алфавитном порядке, сгруппируйте данные по отделам.
Документация к стандартной библиотеке достаточно подробна и будет вам помогать в решении поставленных задач.
В следующей главе мы рассмотрим работу с ошибками и сообщениями о них. Как их предотвратить и как описать ошибки.