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

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

Последняя из наших распространенных коллекций – хеш-карта. Тип HashMap<K, V> хранит соответствие ключей типа K значениям типа V с помощью хеш-функции, которая определяет, как размещать эти ключи и значения в памяти. Многие языки программирования поддерживают такую структуру данных, но часто используют для нее другое имя, например hash, map, object, hash table, dictionary или associative array, если назвать лишь несколько вариантов.

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

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

Создание новой хеш-карты

Один способ создать пустую хеш-карту – использовать new и добавлять элементы с помощью insert. В листинге 8-20 мы отслеживаем счет двух команд, имена которых Blue и Yellow. Команда Blue начинает с 10 очков, а команда Yellow – с 50.

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

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
}

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

Как и векторы, хеш-карты хранят свои данные в куче. У этой 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 получит значение, связанное с командой Blue, и результатом будет 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.

Обновление хеш-карты

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

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

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

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

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 – enum под названием Entry, представляющий значение, которое может существовать или не существовать. Допустим, мы хотим проверить, связано ли значение с ключом команды Yellow. Если нет, мы хотим вставить значение 50; то же самое сделаем для команды Blue. При использовании 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 вставит ключ команды Yellow со значением 50, потому что у команды Yellow еще нет значения. Второй вызов entry не изменит хеш-карту, потому что у команды Blue уже есть значение 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. Преобразуйте строки в Pig Latin. Первая согласная каждого слова переносится в конец слова, и добавляется 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 ↩