Хранение пар ключ-значение с помощью хеш-таблиц

Последней коллекцией, которую мы рассмотрим, будет хеш-таблица. Тип HashMap<K, V> хранит ключи типа K ко значениям типа V, используя функцию хеширования. Во множестве языков программирования есть данная структура, но часто она по-разному называется: hash_, map, object, словарь или ассоциативный массив.

Хеш-таблицы полезны, когда нужно искать данные, используя не индекс (как в случае с векторами), а ключ, который может быть любого типа. Например, в игре вы можете сохранять счёт каждой команды в хеш-таблице, в которой каждый ключ — это название команды, а значение — её счёт. Имея имя команды, вы можете получить её счёт из хеш-таблицы.

В этом разделе мы рассмотрим лишь основной API хеш-таблиц, но стандартная библиотека содержит ещё очень много полезного для HashMap<K, V>. Как и прежде, советуем обращаться к документации стандартной библиотеки для получения дополнительной информации.

Создание хеш-таблицы

One way to create an empty hash map is to use new and to add elements with insert. In Listing 8-20, we’re keeping track of the scores of two teams whose names are Blue and Yellow. The Blue team starts with 10 points, and the Yellow team starts with 50.


fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Синяя"), 10);
    scores.insert(String::from("Жёлтая"), 50);
}

Обратите внимание, что сначала нужно подключить HashMap из стандартной библиотеки с помощью use. Из трёх коллекций данная является наименее используемой, поэтому она не входит в функционал, по умолчанию подключаемый к области видимости (коротко говоря, в prelude). Хеш-таблицы также слабее поддерживаются стандартной библиотекой; например, нет встроенного макроса для их конструирования.

Подобно векторам, хеш-таблицы хранят свои данные в куче. Здесь тип HashMap имеет в качестве типа ключей String, а в качестве типа значений — i32. Как и векторы, HashMap однородны: все ключи должны иметь одинаковый тип, и все значения тоже должны иметь одинаковый тип.

Получение данных из хеш-таблицы

Мы можем получить значение из хеш-таблицы, использовав метод get и передав ему ключ, как показано в Листинге 8-21.


fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Синяя"), 10);
    scores.insert(String::from("Жёлтая"), 50);

    let team_name = String::from("Синяя");
    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("Синяя"), 10);
    scores.insert(String::from("Жёлтая"), 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("Любимая команда:");
    let field_value = String::from("Синяя");

    let mut map = HashMap::new();
    map.insert(field_name, field_value);
    // field_name и field_value отсюда и далее недоступны. Но вы попробуйте использовать
    // их и посмотрите, что за ошибку компиляции получите!
}

Мы не можем использовать переменные field_name и field_value после того, как их значения были перемещены в хеш-таблицу вызовом метода insert.

Если мы вставим в хеш-таблицу ссылки на значения, то значения не будут перемещены в хеш-таблицу. Значения, на которые указывают ссылки, должны быть действительными как минимум пока действительна хеш-таблица. Мы поговорим подробнее об этих вопросах в разделе "Валидация ссылок по времени жизни" Главы 10.

Обновление данных в хеш-таблице

Хотя количество ключей и значений в хеш-таблице может быть изменено, каждый ключ в один момент может иметь только одно значение (обратное утверждение неверно: команды "Синяя" и "Жёлтая" могут хранить в хеш-таблице scores одинаковое количество очков: например, 10).

Если вы хотите изменить данные в хеш-таблице, необходимо решить, как обрабатывать случай, когда ключ уже имеет связанное значение. Можно заменить старое значение новым, полностью проигнорировав старое. Можно сохранить старое значение и проигнорировать новое, если только в хеш-таблице ещё не было этого ключа. Или можно было бы вычислить на основе старого и нового значений третье. Давайте посмотрим, как реализовать каждый из вариантов!

Перезапись значения

Если мы вставим ключ и значение в хеш-таблицу, а затем вставим такой же ключ с новым значением, то старое значение, связанное с этим ключом, будет заменено на новое. Даже несмотря на то, что код в Листинге 8-23 вызывает insert дважды, хеш-таблица будет содержать только одну пару ключ-значение, потому что мы вставляем значения для одного и того же ключа — ключа синей команды.


fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Синяя"), 10);
    scores.insert(String::from("Синяя"), 25);

    println!("{scores:?}");
}

Код напечатает {"Синяя": 25}. Начальное значение 10 было перезаписано.

Вставка значения только в том случае, если ключ вводится впервые

Обычно проверяют, существует ли конкретный ключ в хеш-таблице, приписано ли ему какое-либо значение, а затем предпринимаются следующие действия: если ключ в хеш-таблице есть, то существующее значение должно оставаться таким, какое оно есть. Если же ключ отсутствует, то вставляют его и его значение.

Хеш-таблицы имеют для этого специальный метод entry, который принимает ключ, наличие которого нужно проверить. Возвращаемое значение метода entry — это перечисление Entry, представляющего значение, которое может как присутствовать, так и отсутствовать. Допустим, мы хотим проверить, имеется ли ключ и связанное с ним значение для жёлтой команды. Если хеш-таблица не имеет значения для такого ключа, то мы хотим вставить значение 50. То же самое мы хотим проделать и для синей команды. Использование entry показано в коде Листинга 8-24.


fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();
    scores.insert(String::from("Синяя"), 10);

    scores.entry(String::from("Жёлтая")).or_insert(50);
    scores.entry(String::from("Синяя")).or_insert(50);

    println!("{scores:?}");
}

Метод or_insert определён в Entry так, чтобы возвращать изменяемую ссылку на соответствующее значение ключа внутри варианта перечисления Entry, когда этот ключ существует, а если его нет, то вставлять параметр в качестве нового значения этого ключа и возвращать изменяемую ссылку на новое значение. Эта техника намного чище, чем самостоятельное написание логики и, кроме того, она более безопасна и согласуется с правилами заимствования.

При выполнении кода Листинга 8-24 будет напечатано {"Жёлтая": 50, "Синяя": 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, которая может противостоять атакам класса Denial of Service (DoS) с использованием хеш-таблиц¹. Это не самый быстрый из возможных алгоритмов хеширования, но в данном случае производительность идёт на компромисс с обеспечением лучшей безопасности. Если после профилирования вашего кода окажется, что хеш-функция, используемая по умолчанию, очень медленная, вы можете заменить её используя другой хешер. Хешер — это тип, реализующий трейт BuildHasher. Подробнее о трейтах мы поговорим в Главе 10. Вам совсем не обязательно реализовывать свою собственную функцию хеширования; на crates.io есть достаточное количество библиотек, предоставляющих разные реализации хешеров с множеством общих алгоритмов хеширования.

https://en.wikipedia.org/wiki/SipHash

Подведём итоги

Векторы, строки и хеш-таблицы предоставят большое количество функционала для программ, когда необходимо сохранять, извлекать и модифицировать данные. Теперь вы готовы решить следующие учебные задания:

Дан список целых чисел. Использовав вектор, напишите функции получения медианы (значение элемента из середины списка после его сортировки) и моды (наиболее частое значение; подсказка: используйте хеш-таблицы) списка чисел.
Переведите текст с английского на поросячью латынь. Первая согласная каждого слова перемещается в конец и к ней добавляется окончание ay (пример: first станет irst-fay). К слову, начинающемуся на гласную, в конец добавляется hay (пример: apple становится apple-hay). Помните о деталях работы с кодировкой UTF-8!
Используя хеш-таблицу и векторы, создайте текстовый интерфейс, позволяющий пользователю приписывать сотрудников по их именам к отделам компании. Например, Add Sally to Engineering или Add Amir to Sales. Затем позвольте пользователю получить список всех людей из отдела или всех людей в компании, отсортированный по отделам в алфавитном порядке.

Документация API стандартной библиотеки содержит описания методов векторов, строк и хеш-таблиц. Рекомендуем пользоваться ей при решении упражнений!

Потихоньку мы переходим к более сложным программам, в которых операции могут потерпеть неудачу. Наступил идеальный момент для обсуждения обработки ошибок.

The Rust Programming Language