Язык программирования Rust

Хранение ключей со связанными значениями в хэш-мапах

Последний из наших распространённых коллекций — это хэш-мапа. Тип 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);
}

Обратите внимание, что нам нужно сначала 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 будет иметь значение, связанное с командой Синие, и результат будет 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 and field_value are invalid at this point, try using them and
    // see what compiler error you get!
}

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

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

Обновление хэш-мапы

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

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

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

Если мы вставляем ключ и значение в хэш-мапу, а затем вставляем тот же ключ с другим значением, значение, связанное с этим ключом, будет заменено. Хотя код в Листинге 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:?}");
}

Метод or_insert на Entry определён так, чтобы возвращать изменяемую ссылку на значение для соответствующего ключа 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), связанным с хэш-таблицами¹. Это не самая быстрая хэш-функция, но компромисс в виде лучшей безопасности из-за падения производительности того стоит. Если вы профилируете свой код и обнаруживаете, что хэш-функция по умолчанию слишком медленна для ваших целей, вы можете переключиться на другую, указав другого хэшера. Хэшер — это тип, который реализует типаж BuildHasher. Мы поговорим о типажах и их реализации в Главе 10. Вам не обязательно реализовывать свой хэшер с нуля; на crates.io есть библиотеки, которыми делятся другие пользователи Rust, предоставляющие хэшеры, реализующие многие распространённые алгоритмы хэширования.

Краткий итог

Векторы, строки и хэш-мапы предоставят большой объём функциональности, необходимой в программах, когда вам нужно хранить, получать доступ и изменять данные. Вот несколько упражнений, которые вы теперь готовы решить:

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

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

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

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