Rust HashMap: как эффективно искать и вставлять данные

Онлайн-тренажер Python для начинающих

Изучайте Python легко и без перегрузки теорией. Решайте практические задачи с автоматической проверкой, получайте подсказки на русском языке и пишите код прямо в браузере — без необходимости что-либо устанавливать.

Начать курс

Как эффективно искать и вставлять данные в HashMap на Rust: заглядываем под капот

Вы когда-нибудь писали код на Rust и думали: "Как же мне одновременно проверить, есть ли ключ в HashMap, и если нет — вставить новое значение?" Этот вопрос мучает тысячи разработчиков на Stack Overflow. И не зря: наивное решение может убить производительность вашего приложения. Сегодня мы не просто дадим ответ — мы залезем внутрь Rust HashMap и посмотрим, как она устроена. Вы узнаете, почему get и insert по отдельности — это путь к боли, и как правильно использовать entry API.

Эта статья — для тех, кто уже знаком с основами Rust, но хочет глубже понять, как работают коллекции под капотом. Поехали!

Проблема: два вызова — двойная работа

Представьте типичную задачу: у вас есть HashMap, в которой нужно подсчитать количество вхождений слов в тексте. Наивный подход выглядит так:

use std::collections::HashMap;

fn count_words_naive(words: &[&str]) -> HashMap<String, u32> {
    let mut map = HashMap::new();
    
    for word in words {
        if map.contains_key(*word) {
            let count = map.get(*word).unwrap();
            map.insert(word.to_string(), count + 1);
        } else {
            map.insert(word.to_string(), 1);
        }
    }
    
    map
}

Что здесь плохо? Мы дважды обращаемся к HashMap для каждого слова: сначала contains_key, потом get, а затем ещё и insert. Каждый вызов — это вычисление хэша, поиск в корзине и сравнение ключей. Для короткого текста это незаметно, но для миллионов записей — катастрофа.

Под капотом: как устроена HashMap в Rust

Чтобы понять, почему это плохо, давайте разберёмся, как работает HashMap в Rust. В основе лежит хэш-таблица с открытой адресацией (Robin Hood hashing). Вот ключевые моменты:

Хэширование: Ключ преобразуется в хэш-код с помощью хэш-функции (по умолчанию SipHash-2-4).
Корзины (buckets): Хэш-код определяет индекс в массиве корзин. В Rust каждая корзина — это слот, который может быть пустым, занятым или удалённым.
Коллизии: Когда два разных ключа попадают в одну корзину, Robin Hood hashing пытается "украсть" место у более "богатого" соседа, чтобы сбалансировать расстояния поиска.
Ресайзинг: Когда таблица заполняется (load factor ~0.9), она увеличивается в 2 раза, и все элементы перехешируются.

Теперь представьте: каждый вызов get или insert — это полный цикл: хэширование, поиск по индексу, сравнение ключей (возможно, несколько раз из-за коллизий). Два вызова = двойная работа. А если между вызовами произошёл ресайзинг? Тройная!

Решение: Entry API — ваш спасательный круг

Rust предлагает элегантное решение — Entry API. Это механизм, который позволяет выполнить поиск и, возможно, вставку за один проход. Вот как выглядит правильный код для подсчёта слов:

use std::collections::HashMap;

fn count_words_efficient(words: &[&str]) -> HashMap<String, u32> {
    let mut map = HashMap::new();
    
    for word in words {
        let entry = map.entry(word.to_string());
        *entry.or_insert(0) += 1;
    }
    
    map
}

Кратко, красиво, эффективно. Но как это работает под капотом? Давайте разберём по шагам.

Шаг 1: Метод entry()

Вызов map.entry(key) возвращает перечисление Entry, которое может быть в двух состояниях:

Entry::Occupied — ключ уже существует в таблице.
Entry::Vacant — ключа нет, и у нас есть готовое место для вставки.

Важно: на этом этапе хэш уже вычислен, и поиск выполнен один раз. Entry API хранит ссылку на найденную корзину (или место, куда можно вставить).

Шаг 2: Метод or_insert()

Метод or_insert(default) делает следующее:

Если Entry — Occupied: возвращает мутабельную ссылку на существующее значение.
Если Entry — Vacant: вставляет переданное значение по умолчанию и возвращает ссылку на него.

В нашем примере or_insert(0) вставляет 0, если ключа нет, а затем мы увеличиваем значение на 1. Всё за один проход по таблице!

Ещё более эффективные варианты

Иногда нужно не просто вставить значение, а выполнить сложную логику. Для этого есть дополнительные методы:

use std::collections::HashMap;

fn advanced_entry_example() {
    let mut map: HashMap<String, Vec<u32>> = HashMap::new();
    
    // or_insert_with — вставляет результат замыкания, только если ключа нет
    map.entry("key1".to_string())
       .or_insert_with(|| vec![1, 2, 3]);
    
    // and_modify — изменяет существующее значение
    map.entry("key2".to_string())
       .and_modify(|v| v.push(42))
       .or_insert(vec![42]);
    
    // key() — получает ссылку на ключ (полезно для owned keys)
    if let Some(entry) = map.entry("key1".to_string()).key() {
        println!("Key: {}", entry);
    }
}

Обратите внимание: or_insert_with вызывает замыкание только если ключа нет. Это экономит ресурсы, если создание значения дорогое.

Производительность: цифры не врут

Давайте сравним производительность наивного подхода и Entry API. Я написал небольшой бенчмарк (вы можете запустить его с помощью cargo bench):

use std::collections::HashMap;
use std::time::Instant;

fn benchmark() {
    let data: Vec<String> = (0..100_000).map(|i| format!("word_{}", i)).collect();
    
    // Наивный подход
    let start = Instant::now();
    let mut map1 = HashMap::new();
    for word in &data {
        if map1.contains_key(word) {
            let count = map1.get(word).unwrap();
            map1.insert(word.clone(), count + 1);
        } else {
            map1.insert(word.clone(), 1);
        }
    }
    println!("Naive: {:?}", start.elapsed());
    
    // Entry API
    let start = Instant::now();
    let mut map2 = HashMap::new();
    for word in &data {
        *map2.entry(word.clone()).or_insert(0) += 1;
    }
    println!("Entry: {:?}", start.elapsed());
}

Результаты (на моём ноутбуке):