Как эффективно выполнять поиск и вставку в HashMap в Rust?

Использование Entry API — идиоматичное и эффективное решение

Ваша интуиция верна: многократные обращения к HashMap через contains_key, get и insert действительно неэффективны. Каждая операция требует хеширования и поиска, что для миллионов записей даёт значительные накладные расходы. В Rust для таких сценариев существует элегантное решение — Entry API.

Вот оптимальный код для вашей задачи:

use std::collections::HashMap;

fn main() {
    let text = "hello world hello rust rust rust";
    let mut map: HashMap<&str, u32> = HashMap::new();

    for word in text.split_whitespace() {
        *map.entry(word).or_insert(0) += 1;
    }

    // Вывод топ-10
    let mut entries: Vec<(&str, u32)> = map.into_iter().collect();
    entries.sort_by(|a, b| b.1.cmp(&a.1));
    for (word, count) in entries.iter().take(10) {
        println!("{}: {}", word, count);
    }
}

Как это работает?

Метод entry() принимает ключ и возвращает перечисление Entry:

• Entry::Occupied — если ключ уже существует в HashMap
• Entry::Vacant — если ключа нет

Метод or_insert(0) делает две вещи:

• Если ключа нет — вставляет значение по умолчанию (0) и возвращает ссылку на него
• Если ключ есть — просто возвращает ссылку на существующее значение

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

Почему это эффективно?

• Одно хеширование вместо трёх. Entry API вычисляет хеш ключа один раз и использует его для поиска/вставки.
• Нет лишних копирований. entry() работает с ссылками, а не с владением.
• Идиоматичность. Код короче, понятнее и соответствует стандартным практикам Rust.

Для больших файлов — оптимизация с String

Если вы читаете строки из файла, используйте String вместо &str:

use std::collections::HashMap;
use std::fs::File;
use std::io::{BufRead, BufReader};

fn main() -> Result<(), std::io::Error> {
    let file = File::open("large_file.txt")?;
    let reader = BufReader::new(file);
    let mut map: HashMap<String, u32> = HashMap::new();

    for line in reader.lines() {
        let line = line?;
        for word in line.split_whitespace() {
            *map.entry(word.to_string()).or_insert(0) += 1;
        }
    }
    Ok(())
}

Обратите внимание: word.to_string() создаёт новую строку для вставки, но это неизбежно, если данные не живут дольше чтения файла. Для максимальной производительности рассмотрите крейт fxhash (более быстрый хеш) или ahash.

use std::collections::HashMap;

fn main() {
    let text = "hello world hello rust rust rust";
    let map = text.split_whitespace()
        .fold(HashMap::new(), |mut acc, word| {
            *acc.entry(word).or_insert(0) += 1;
            acc
        });

    println!("{:?}", map);
}