HashMap & BTreeMap

Hashmap<K, V, S = RandomState>

Это изменяемая структура словарь (“dictionary” в Python), которая хранит пары “ключ->значение”. В Rust Prelude она не входит, макроса создания не имеет. Поэтому нужно указывать библиотеку явно и явно создавать структуру.

use std::collections::HashMap;  
  
fn main() {  
    let mut scores = HashMap::new();  
    scores.insert(String::from("Alpha"),1);  
    scores.insert(String::from("Beta"),2);  
    scores.insert(String::from("Gamma"),3); 
}

Все ключи Hashmap должны быть уникальны и одного типа, все значения должны быть одного типа.

Warning

Значения с кучи типа String перемещаются (move) в Hashmap, который становится их владельцем.

Взятие значения по ключу из Hashmap с помощью get нужно сопровождать проверкой - есть ли в памяти запрашиваемые ключ и значение:

let name = String::from("Gamma");  
if let Some(letter_num) = scores.get(&name) {  
    println!("{}",letter_num);  
} else { println!("Value not in HashMap!"); }

Итерация по Hashmap похожа на итерацию по вектору:

for (key, value) in &scores {  
    println!("{key} -> {value}"); }

Обновление Hashmap

Есть ряд стратегий обновления значений в Hashmap:

Перезаписывать всегда

scores.insert(String::from("Gamma"),3); // вставка дважды значений по одному 
scores.insert(String::from("Gamma"),6); // ключу сохранит последнее значение

Записывать значение, если у ключа его нет:

scores.entry(String::from("Delta")).or_insert(4); // entry проверяет наличие
// значения, or_insert возвращает mut ссылку на него, либо записывает новое 
// значение и возвращает mut ссылку на это значение.

Записывать значение, если ключа нет. Если же у ключа есть значение, модифицировать его:

use std::collections::HashMap;

let mut map: HashMap<&str, u32> = HashMap::new();

map.entry("poneyland") // первое добавление
   .and_modify(|e| { *e += 1 })
   .or_insert(42);     // добавит ключ "poneyland: 42"
assert_eq!(map["poneyland"], 42);

map.entry("poneyland") // второе добавление найдёт ключ со значением
   .and_modify(|e| { *e += 1 }) // и модифицирует его
   .or_insert(42);
assert_eq!(map["poneyland"], 43);

Записывать значение, если ключа нет, в виде результата функции. Эта функция получает ссылку на значение ключа key, который передаётся в .entry(key):

use std::collections::HashMap;

let mut map: HashMap<&str, usize> = HashMap::new();
map
  .entry("poneyland")
  .or_insert_with_key(|key| key.chars().count());

assert_eq!(map["poneyland"], 9);

Поднимать старое значение ключа, проверять его перед перезаписью:

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); // {"wonderful": 1, "hello": 1, "world": 2}

Инициализация HashMap со значениями по-умолчанию

Поведение аналогично типу defaultdict в Python. Заполнять ключами HashMap:

в случае отсутствия ключа, создавать его со значением по-умолчанию (0);
в случае присутствия ключа, добавлять к значению +1. Аналогичный подход реализуется с fold(), а также с помощью itertools::counts() :

use std::collections::HashMap;
pub fn main() {
    let num_vec = vec![1, 2, 1, 3, 5, 2, 1, 4, 6];
    let mut number_count: HashMap<i32, i32> = HashMap::new();
    for key in num_vec {
        *number_count.entry(key).or_default() += 1;
    }
    for (k, v) in number_count {
        print!("{} -> {}; ", k, v);
    }
}
// 4 -> 1; 1 -> 3; 2 -> 2; 6 -> 1; 5 -> 1; 3 -> 1;

Метод entry позволяет избежать проверки contains_key вручную.

Более простой аналог с for_each():

let mut number_count = HashMap::new();
num_vec.iter().for_each(|s| {
    *number_count.entry(s).or_insert(0) += 1;
});

Удаление элемента

use std::collections::HashMap;

let mut map: HashMap<&str, i32> = HashMap::from([
    ("a", 1),
    ("b", 2),
    ("c", 3),
]);
map.remove("b"); // удаляет по ключу "b"
println!("{:?}", map); // {"a": 1, "c": 3}

Альтернатива: Если не нужно сдвигать элементы, можно использовать .swap_remove(index) (быстрее, O(1), но меняет порядок):

let mut numbers = vec![1, 2, 3, 4];
numbers.swap_remove(1); // заменяет на последний элемент и удаляет его
println!("{:?}", numbers); // [1, 4, 3]

Сортировка HashMap

Если нужно отсортировать по значениям придётся:

Преобразовать HashMap в вектор пар (ключ, значение);
Отсортировать его;
Собрать обратно (если нужно).

use std::collections::HashMap;

let mut hmap: HashMap<&str, i32> = HashMap::from([
    ("b", 3),("a", 1),("c", 2),]);
let mut hsorted = hmap.into_iter().collect::<Vec<(&str, i32)>>();
hsorted.sort_by(|a, b| a.1.cmp(&b.1)); // сортировка по значению
println!("{:?}", hsorted); // [("a", 1), ("c", 2), ("b", 3)]

BTreeMap<K, V, A = Global>

Упорядоченная по ключам K структура данных на основе B-дерева. Ключевые отличия от HashMap:

Свойство	HashMap	BTreeMap
Внутренняя структура	Хэш таблица	Дерево поиска
Упорядоченность	Не гарантированная	Ключи всегда упорядочены
Скорость	O(1)	O(log n)
Требования	`Hash + Eq`	`Ord`
Потребление памяти	Выше	Ниже

Применение

Когда нужно сразу сортировать данные:

    let mut scores = BTreeMap::new();
    scores.insert("Charlie", 85);
    scores.insert("Alice", 92);
    scores.insert("Bob", 78);

    // Итерация сразу в отсортированном порядке по ключам
    for (name, score) in &scores {
        println!("{}: {}", name, score); // Alice, Bob, Charlie
    }

    // Получить 1ый и последний элементы
    println!("{:?}", scores.first_key_value()); // ("Alice", 92)
    println!("{:?}", scores.last_key_value()); // ("Charlie", 85)

Работа с диапазонами значений:

    // Диапазоны заданы кортежами (нижняя_граница, верхняя_граница)
    let mut price_ranges = BTreeMap::new();
    price_ranges.insert((0, 10), "Budget");
    price_ranges.insert((11, 50), "Standard");
    price_ranges.insert((51, 100), "Premium");
    price_ranges.insert((101, 1000), "Luxury");

    let query_price = 42;

    // Поиск по диапазонам (линейный в данном случае)
    for ((low, high), category) in &price_ranges {
        if query_price >= *low && query_price <= *high {
            println!(
                "Price ${} is in category: {} (range: {}-{})",
                query_price, category, low, high
            );
            break;
        } }

Порядок при сериализации в JSON:

use serde_json 

let mut config = BTreeMap::new();
config.insert("zebra", "animal");
config.insert("apple", "fruit");
config.insert("banana", "fruit");

// сериализация в JSON с порядком элементов
let json = serde_json::to_string_pretty(&config).unwrap();
println!("{}", json); // ключи будут в порядке: apple, banana, zebra

Сравнение HashMap vs BTreeMap по скорости

use std::collections::{BTreeMap, HashMap};
use std::time::Instant;

fn main() {
    let n = 100_000;
    
    // HashMap insertion
    let start = Instant::now();
    let mut hash_map = HashMap::new();
    for i in 0..n {
        hash_map.insert(i, i * 2);
    }
    println!("HashMap insert: {:?}", start.elapsed());

    // BTreeMap insertion
    let start = Instant::now();
    let mut btree_map = BTreeMap::new();
    for i in 0..n {
        btree_map.insert(i, i * 2);
    }
    println!("BTreeMap insert: {:?}", start.elapsed());
}
// HashMap insert: 50.855881ms
// BTreeMap insert: 102.619694ms

Для небольших коллекций (< 1000 элементов) или когда требуется отсортированный порядок, BTreeMap часто предпочтительнее. Для больших коллекций, где нужна максимальная скорость, а порядок не имеет значения, HashMap обычно лучше.