The Rust Programming Language

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

The last of our common collections is the hash map. The type HashMap<K, V> stores a mapping of keys of type K to values of type V using a hashing function, which determines how it places these keys and values into memory. Many programming languages support this kind of data structure, but they often use a different name, such as hash, map, object, hash table, dictionary, or associative array, just to name a few.

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

В этом разделе мы рассмотрим лишь основной 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). Хеш-таблицы также слабее поддерживаются стандартной библиотекой; например, нет встроенного макроса для их конструирования.

Just like vectors, hash maps store their data on the heap. This HashMap has keys of type String and values of type i32. Like vectors, hash maps are homogeneous: All of the keys must have the same type, and all of the values must have the same type.

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

Мы можем получить значение из хеш-таблицы, использовав метод 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

Managing Ownership in Hash Maps

Для типов, которые реализуют трейт 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.

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

Although the number of key and value pairs is growable, each unique key can only have one value associated with it at a time (but not vice versa: For example, both the Blue team and the Yellow team could have the value 10 stored in the scores hash map).

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

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

Если мы вставим ключ и значение в хеш-таблицу, а затем вставим такой же ключ с новым значением, то старое значение, связанное с этим ключом, будет заменено на новое. Даже несмотря на то, что код в Листинге 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 было перезаписано.

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

It’s common to check whether a particular key already exists in the hash map with a value and then to take the following actions: If the key does exist in the hash map, the existing value should remain the way it is; if the key doesn’t exist, insert it and a value for it.

Хеш-таблицы имеют для этого специальный метод 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, когда этот ключ существует, а если его нет, то вставлять параметр в качестве нового значения этого ключа и возвращать изменяемую ссылку на новое значение. Эта техника намного чище, чем самостоятельное написание логики и, кроме того, она более безопасна и согласуется с правилами заимствования.

Running the code in Listing 8-24 will print {"Yellow": 50, "Blue": 10}. The first call to entry will insert the key for the Yellow team with the value 50 because the Yellow team doesn’t have a value already. The second call to entry will not change the hash map, because the Blue team already has the value 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:?}");
}

This code will print {"world": 2, "hello": 1, "wonderful": 1}. You might see the same key-value pairs printed in a different order: Recall from “Accessing Values in a Hash Map” that iterating over a hash map happens in an arbitrary order.

Метод split_whitespace, выполненный на text, возвращает итератор по подсрезам строки, разделённым пробелами. Метод or_insert возвращает изменяемую ссылку (&mut V) на значение ключа. Мы сохраняем изменяемую ссылку в переменной count, поэтому чтобы присвоить переменной значение, необходимо разыменовать count с помощью звёздочки (*). Изменяемая ссылка удаляется сразу же после выхода из области видимости цикла for, поэтому все эти изменения безопасны и согласуются с правилами заимствования.

Функции хеширования

По умолчанию HashMap использует функцию хеширования SipHash, которая может противостоять атакам класса Denial of Service (DoS) с использованием хеш-таблиц¹. Это не самый быстрый из возможных алгоритмов хеширования, но в данном случае производительность идёт на компромисс с обеспечением лучшей безопасности. Если после профилирования вашего кода окажется, что хеш-функция, используемая по умолчанию, очень медленная, вы можете заменить её используя другой хешер. Хешер — это тип, реализующий трейт BuildHasher. Подробнее о трейтах мы поговорим в Главе 10. Вам совсем не обязательно реализовывать свою собственную функцию хеширования; на crates.io есть достаточное количество библиотек, предоставляющих разные реализации хешеров с множеством общих алгоритмов хеширования.

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

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

1. Дан список целых чисел. Использовав вектор, напишите функции получения медианы (значение элемента из середины списка после его сортировки) и моды (наиболее частое значение; подсказка: используйте хеш-таблицы) списка чисел.
2. Convert strings to Pig Latin. The first consonant of each word is moved to the end of the word and ay is added, so first becomes irst-fay. Words that start with a vowel have hay added to the end instead (apple becomes apple-hay). Keep in mind the details about UTF-8 encoding!
3. Using a hash map and vectors, create a text interface to allow a user to add employee names to a department in a company; for example, “Add Sally to Engineering” or “Add Amir to Sales.” Then, let the user retrieve a list of all people in a department or all people in the company by department, sorted alphabetically.

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

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

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