Hashmaps & 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.
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;

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 обычно лучше.