Bài 132: BTreeMap & BTreeSet — Sorted Variant

Sau bài học, bạn sẽ:

• Hiểu BTreeMap<K, V> là map sorted theo Ord của key, implement bằng B-tree balanced.
• Phân biệt trait bound: HashMap cần Hash + Eq, BTreeMap cần Ord (và do đó cả Eq + PartialOrd).
• Biết ba khả năng đắt giá của BTreeMap mà HashMap không có: iterate sorted, .range(a..b), .first_key_value()/.last_key_value().
• Dùng được BTreeSet<T> tương tự BTreeMap, hữu ích khi cần tập unique đã sorted sẵn.
• Cheat sheet quyết định: HashMap mặc định cho lookup; BTreeMap khi cần ordering, range, deterministic, hoặc time-series.

std::collections::BTreeMap<K, V> là map associative trong stdlib Rust, implement bằng B-tree balanced — cấu trúc cây nhiều con tương tự B-tree quen thuộc trong database, mỗi node giữ nhiều key liền nhau để tận dụng cache line CPU. Khác hashmap chỗ key không bị băm, mà được giữ SORTED theo Ord ở mọi thời điểm.

Hệ quả trực tiếp: lookup, insert, remove đều là O(log n) thay vì O(1) amortized như HashMap. Đổi lại mọi operation đều ổn định — không có trường hợp xấu O(n) như HashMap khi hash collision, không phụ thuộc hash function, output luôn deterministic giữa các lần chạy.

use std::collections::BTreeMap;

fn main() {
    let mut scores: BTreeMap<String, i32> = BTreeMap::new();
    scores.insert("charlie".into(), 85);
    scores.insert("alice".into(), 92);
    scores.insert("bob".into(), 78);

    // Iterate luôn theo thứ tự key tăng dần.
    for (name, score) in &scores {
        println!("{name}: {score}");
    }
    // alice: 92
    // bob: 78
    // charlie: 85
}

So sánh nhanh: cùng input nhưng dùng HashMap, output sẽ ra theo thứ tự ngẫu nhiên (phụ thuộc seed của RandomState) — chạy hai lần có thể ra hai thứ tự khác nhau. Với BTreeMap thì luôn alice → bob → charlie.

Ba điểm khác biệt cốt lõi:

• Thứ tự: HashMap unordered (thứ tự phụ thuộc seed hash), BTreeMap ordered theo Ord của key.
• Phức tạp: HashMap lookup/insert O(1) amortized, BTreeMap O(log n) deterministic.
• Trait bound key: HashMap cần K: Hash + Eq, BTreeMap cần K: Ord (kéo theo Eq + PartialOrd).

Demo iterate khác nhau giữa hai loại:

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

fn main() {
    let pairs = [("c", 3), ("a", 1), ("b", 2)];

    let h: HashMap<_, _> = pairs.iter().cloned().collect();
    let b: BTreeMap<_, _> = pairs.iter().cloned().collect();

    println!("HashMap : {:?}", h);
    // HashMap : {"a": 1, "c": 3, "b": 2}   ← thứ tự không xác định

    println!("BTreeMap: {:?}", b);
    // BTreeMap: {"a": 1, "b": 2, "c": 3}   ← luôn sorted
}

Về trait bound: f64 không implement Ord (vì có NaN) — không thể làm key trực tiếp cho BTreeMap. Ngược lại, một struct chỉ implement Ord mà không có Hash thì dùng được với BTreeMap nhưng không dùng được với HashMap. Đây là tình huống thực: nhiều type có natural ordering nhưng không có hash hợp lý.

Cân nhắc BTreeMap khi gặp một trong các tình huống sau:

• Cần iterate theo thứ tự key: in báo cáo theo alphabet, dump config, export sang JSON cần ổn định cho diff.
• Range query: lấy hết key trong khoảng [a, b) — ví dụ tất cả event trong cửa sổ thời gian, tất cả user có id nằm trong segment.
• Deterministic output: test snapshot, golden file, log có thứ tự ổn định để dễ diff giữa các lần chạy.
• Key có Ord nhưng không Hash: struct có natural ordering (timestamp, version, semver) chưa derive hash.
• Time-series: key là DateTime hay u64 timestamp, cần lookup nhanh phần tử mới nhất, lấy slice theo khoảng thời gian.
• Cần min/max thường xuyên: với HashMap phải iterate toàn bộ O(n); với BTreeMap chỉ O(log n) cho cả hai đầu.

Ngược lại, mặc định vẫn dùng HashMap khi chỉ cần lookup nhanh không quan tâm thứ tự — nó vẫn là lựa chọn tốt nhất cho 80% use case.

Tin tốt: phần lớn API quen từ HashMap đều có trên BTreeMap với cùng signature. Đổi HashMap thành BTreeMap trong khai báo thường compile được luôn (trừ khi key của bạn chỉ Hash mà không Ord).

use std::collections::BTreeMap;

fn main() {
    let mut m: BTreeMap<&str, i32> = BTreeMap::new();

    m.insert("a", 1);
    m.insert("b", 2);

    let v = m.get("a");                    // Option<&V>
    let exists = m.contains_key("b");       // bool
    let removed = m.remove("a");            // Option<V>

    // entry API hoạt động y hệt HashMap.
    *m.entry("c").or_insert(0) += 10;
    *m.entry("c").or_insert(0) += 5;
    println!("{:?}", m);  // {"b": 2, "c": 15}
}

Các method có sẵn giống HashMap bao gồm insert, get, get_mut, remove, contains_key, keys, values, values_mut, iter, iter_mut, entry, len, is_empty, clear, retain. Một khác biệt nhỏ về output: iterator của BTreeMap luôn trả phần tử theo thứ tự sorted của key — tận dụng được ngay mà không cần collect-sort thủ công.

Đây là tính năng đặc trưng của B-tree mà HashMap không có. m.range(a..b) trả iterator các (K, V) có key nằm trong khoảng — chạy trong O(log n + k) với k là số phần tử match. HashMap muốn làm được điều tương tự phải iterate toàn bộ O(n) rồi lọc.

use std::collections::BTreeMap;

fn main() {
    let mut events: BTreeMap<u64, &str> = BTreeMap::new();
    events.insert(1_700_000_000, "login");
    events.insert(1_700_000_120, "view");
    events.insert(1_700_000_300, "purchase");
    events.insert(1_700_000_450, "logout");
    events.insert(1_700_001_000, "login");

    // Lấy event trong cửa sổ [1_700_000_100, 1_700_000_500).
    for (ts, name) in events.range(1_700_000_100..1_700_000_500) {
        println!("{ts}: {name}");
    }
    // 1700000120: view
    // 1700000300: purchase
    // 1700000450: logout
}

Range nhận mọi RangeBounds chuẩn của Rust: a..b, a..=b, ..b, a.., ... Phiên bản mut là .range_mut(a..b) cho phép sửa value qua iterator. Đây là lý do BTreeMap gần như mặc định trong time-series, log indexed by timestamp, và mọi tình huống cần slice theo khoảng key.

Stable từ Rust 1.66, hai method này trả ngay min/max key cùng value của BTreeMap trong O(log n) — chỉ phải đi xuống nhánh trái/phải nhất của B-tree.

use std::collections::BTreeMap;

fn main() {
    let mut m: BTreeMap<u32, &str> = BTreeMap::new();
    m.insert(50, "fifty");
    m.insert(10, "ten");
    m.insert(80, "eighty");
    m.insert(30, "thirty");

    if let Some((k, v)) = m.first_key_value() {
        println!("min: {k} -> {v}");   // min: 10 -> ten
    }
    if let Some((k, v)) = m.last_key_value() {
        println!("max: {k} -> {v}");   // max: 80 -> eighty
    }
}

Còn có .pop_first() và .pop_last() nhận luôn ownership và xóa phần tử ra khỏi map — biến BTreeMap thành priority queue dùng được ngay khi cần lấy phần tử nhỏ nhất hoặc lớn nhất. HashMap không có cặp method này; muốn min/max phải iterate .iter().min_by_key(...) với cost O(n).

BTreeSet<T> là cặp song sinh của HashSet<T>, quan hệ tương tự như BTreeMap với HashMap. Phần tử là unique, được giữ sorted theo Ord, hỗ trợ đủ các phép tập hợp intersection, union, difference, symmetric_difference.

use std::collections::BTreeSet;

fn main() {
    let mut s: BTreeSet<i32> = BTreeSet::new();
    s.insert(5);
    s.insert(1);
    s.insert(3);
    s.insert(1);  // duplicate, bị bỏ qua

    for x in &s {
        print!("{x} ");
    }
    println!();
    // 1 3 5  ← luôn sorted

    // Range trên set cũng dùng được.
    let mid: Vec<i32> = s.range(2..=4).copied().collect();
    println!("{:?}", mid);  // [3]
}

Use case điển hình của BTreeSet: deduplicate một stream số hoặc string và xuất ra theo thứ tự (chỉ một bước, không cần collect rồi sort); maintain set ID dạng u64 cần xem được min/max nhanh; build "sorted unique list" cho UI dropdown.

Lý thuyết Big-O nói HashMap O(1) thắng BTreeMap O(log n), nhưng thực tế phụ thuộc kích thước và pattern truy cập:

• Lookup đơn lẻ với n lớn: HashMap nhanh hơn rõ rệt — hash + index trỏ thẳng vào bucket, không phải đi log n level cây.
• Lookup với n nhỏ (vài chục đến vài trăm): hai bên xấp xỉ, đôi khi BTreeMap còn nhanh hơn nhờ cache-friendly — B-tree giữ nhiều key liền nhau trong một node, ít cache miss hơn.
• Iterate toàn bộ: BTreeMap thường nhỉnh hơn vì layout liên tục theo nhánh, prefetcher CPU dễ đoán.
• Range query / min / max / sorted iterate: BTreeMap thắng tuyệt đối — HashMap phải iterate full + sort, là O(n log n).
• Hash collision attack: HashMap default có random seed chống tốt; BTreeMap không có vấn đề này vì không dùng hash.

Quy tắc thực dụng: chọn HashMap cho lookup-heavy workload thuần túy; chọn BTreeMap khi cần ít nhất một trong các thao tác sorted (range, min/max, iterate ổn định). Nếu data nhỏ (< vài trăm phần tử) và bạn cần thứ tự, BTreeMap gần như miễn phí.

• BTreeMap implement bằng B-tree balanced, key luôn sorted theo Ord; lookup/insert/remove O(log n).
• Trait bound: HashMap cần Hash + Eq, BTreeMap cần Ord (kéo theo Eq + PartialOrd).
• API thông dụng (insert, get, remove, contains_key, entry) giống HashMap; iterate trả phần tử sorted.
• Ba thứ HashMap không có: .range(a..b), .first_key_value()/.last_key_value(), deterministic output.
• BTreeSet là cặp song sinh — unique đã sorted, dùng được mọi phép set.
• Mặc định vẫn HashMap; chuyển sang BTreeMap khi cần ordering, range, deterministic, time-series, hoặc key không Hash được.

Tự trả lời, đáp án ở cuối:

1. Tại sao f64 không dùng làm key BTreeMap được? Workaround thông dụng?
2. Cho một HashMap<String, u32> log lượt view trang. Cần xuất top 5 trang theo tên alphabet. Đổi sang BTreeMap có giúp gì không, hay có cách khác?
3. BTreeMap có khoảng 100 phần tử. Lookup đơn lẻ chậm hơn HashMap rõ rệt không? Vì sao?
4. Cần lưu event time-series với key u64 timestamp, hay phải lấy event trong cửa sổ 5 phút gần nhất. Chọn HashMap hay BTreeMap?
5. Viết hàm trả ra phần tử nhỏ nhất + lớn nhất của một BTreeMap<u32, String> với một lệnh gọi mỗi đầu.

Bài 133: Choosing Right Collection Cho Bài Toán — cheat sheet decision tree chọn giữa Vec, VecDeque, HashMap, BTreeMap, HashSet, BTreeSet theo đặc tính bài toán (cần index, cần order, cần lookup nhanh, cần dedup) kèm benchmark sơ bộ ba pattern phổ biến.