Rust 集合型別 — 性能考量

簡介

在日常開發中，集合型別（如 Vec<T>、HashMap<K, V>、BTreeMap<K, V>）是處理大量資料的基礎工具。雖然 Rust 的標準函式庫已經為這些容器提供了安全且高效的實作，但在不同的使用情境下，選擇不當仍會造成記憶體浪費、CPU 時間過長，甚至產生不可預期的行為。

本篇文章將從 記憶體布局、資料存取模式、快取友好性 三個面向，說明各種集合型別的性能特徵，並提供實作範例、常見陷阱與最佳實踐，協助讀者在寫程式時做出更適切的選擇。

---

核心概念

1. Vec<T> – 連續記憶體的動態陣列

Vec<T> 是最常使用的集合型別，它在堆上以 連續的記憶體區塊 儲存元素，因而具備以下特性：

• 快取友好：連續存取時，CPU 快取命中率高，遍歷速度快。
• 摺疊成本：插入或刪除元素時，若不是在尾端，會觸發搬移（memmove），成本為 O(n)。
• 容量與再配置：Vec 會在容量不足時自動 倍增（預設 2 倍），此過程會重新配置記憶體並搬移舊資料。

範例 1：預先分配容量避免多次再配置

fn main() {
    // 假設要一次放入 10_000 個元素
    let mut v: Vec<u32> = Vec::with_capacity(10_000);
    for i in 0..10_000 {
        v.push(i);
    }
    // 此時不會觸發任何再配置，效能更佳
    println!("len = {}, cap = {}", v.len(), v.capacity());
}

說明：with_capacity 讓 Vec 直接一次分配足夠的空間，避免在迴圈中多次搬移。

範例 2：使用 retain 取代手動 remove

fn main() {
    let mut v = vec![1, 2, 3, 4, 5, 6];
    // 移除所有偶數
    v.retain(|&x| x % 2 != 0);
    // retain 只遍歷一次，內部使用 O(n) 的搬移，效能優於多次 `remove`
    println!("{:?}", v); // [1, 3, 5]
}

說明：retain 會一次遍歷整個向量，將符合條件的元素「就地」搬移，避免多次 remove 產生的 O(n²) 成本。

2. HashMap<K, V> – 基於雜湊的鍵值對容器

HashMap 使用 開放位址法（Open Addressing）或 鏈結法（Chaining）實作雜湊表，主要特性如下：

• 平均 O(1) 的查找、插入與刪除，但最壞情況仍可能退化為 O(n)。
• 快取不友好：雜湊值的分布使得元素在記憶體中分散，遍歷時快取命中率較低。
• 負載因子（load factor）：當表格填滿度超過預設閾值（約 0.75），會觸發 重新雜湊，此過程相當耗時。

範例 3：適當設定容量避免頻繁 rehash

use std::collections::HashMap;

fn main() {
    // 預估會放入 5_000 個鍵值對
    let mut map: HashMap<u32, String> = HashMap::with_capacity(5_000);
    for i in 0..5_000 {
        map.insert(i, format!("value-{}", i));
    }
    println!("len = {}, capacity ≈ {}", map.len(), map.capacity());
}

說明：with_capacity 讓 HashMap 直接配置足夠的 bucket，減少在插入過程中觸發的 rehash。

範例 4：使用 Entry API 減少二次查找

use std::collections::HashMap;

fn main() {
    let mut count: HashMap<&str, usize> = HashMap::new();
    let words = ["apple", "banana", "apple", "orange", "banana", "apple"];

    for w in words.iter() {
        // Entry::or_insert 只會做一次雜湊查找
        *count.entry(w).or_insert(0) += 1;
    }

    println!("{:?}", count); // {"apple": 3, "banana": 2, "orange": 1}
}

說明：entry 讓我們在同一次雜湊查找中完成「插入或取得」的動作，避免了「先 get 再 insert」的雙重查找。

3. BTreeMap<K, V> – 基於 B-Tree 的有序映射

BTreeMap 使用 B-Tree 結構，提供 有序遍歷 的能力，特性包括：

• O(log n) 的查找、插入與刪除，對於大量資料仍保持穩定的性能。
• 快取友好：B-Tree 的節點大小（預設 4 KiB）與 CPU 快取行大小相近，遍歷時快取命中率較高。
• 適合範圍查詢（range）與「前綴搜尋」等需求。

範例 5：利用 range 取得區間資料

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    for i in 0..20 {
        map.insert(i, format!("v{}", i));
    }

    // 取得鍵值在 5..=10 之間的所有項目
    for (k, v) in map.range(5..=10) {
        println!("{} => {}", k, v);
    }
}

說明：range 直接在 B-Tree 上定位起始與結束節點，效率遠高於在 HashMap 上手動過濾。

4. HashSet<T> 與 BTreeSet<T> – 集合型別的特殊化

HashSet 與 BTreeSet 分別是 HashMap、BTreeMap 的鍵值對只保留鍵的版本。性能特徵與其底層容器相同，使用時請留意：

• 去重：插入前會自動檢查是否已存在，成本為 O(1)（HashSet）或 O(log n)（BTreeSet）。
• 遍歷順序：HashSet 無序、BTreeSet 有序。若需要有序輸出，請直接使用 BTreeSet。

範例 6：HashSet 用於快速去重

use std::collections::HashSet;

fn main() {
    let data = vec![1, 2, 3, 2, 4, 1, 5];
    let mut uniq = HashSet::new();

    for x in data {
        uniq.insert(x); // 重複的值不會被插入
    }

    println!("unique: {:?}", uniq); // {1, 2, 3, 4, 5}
}

---

常見陷阱與最佳實踐

陷阱	可能的後果	建議的做法
未預估容量，直接使用 Vec::new()、HashMap::new()	產生大量 realloc + memcpy，效能下降	使用 with_capacity 依需求提前配置
在 Vec 中頻繁 insert(0, …)	每次都會搬移整個向量，O(n²)	改用 VecDeque 或 LinkedList（若插入頻繁且不需快取）
使用 HashMap 作為有序集合	失去鍵值排序，範圍查詢效率低	改用 BTreeMap，或在 HashMap 上自行維護排序索引
使用 String 作為 HashMap 的鍵，未考慮字串切片	產生不必要的字串複製，佔用記憶體	使用 &'a str 或 Cow<'a, str>，或 HashMap<&'a str, V>
忽略負載因子，導致頻繁 rehash	大量 CPU 時間花在雜湊與搬移	依據資料量設定適當的 capacity，或使用 hashbrown::HashMap 調整 max_load_factor

其他實用技巧

1. Vec::shrink_to_fit：在大量刪除後，可呼叫此方法釋放多餘的容量。
2. HashMap::reserve：與 with_capacity 類似，但可在已有容器上提前分配空間。
3. BTreeMap::split_off：可將一棵 B-Tree 分割成兩棵，適合平行處理大量資料。
4. 使用 FxHashMap（rustc_hash crate）：在單執行緒、對安全性要求不高的情況下，可得到更快的雜湊效能。

---

實際應用場景

場景	建議使用的集合型別	為何選擇
即時遊戲的玩家列表（大量插入、刪除、快速查找）	HashMap<PlayerId, PlayerInfo>	O(1) 查找、插入，且不需要排序
金融系統的歷史交易紀錄（需要依時間範圍查詢）	BTreeMap<Timestamp, Transaction>	支援高效的範圍查詢 (range)
文字處理的詞頻統計	HashMap<String, usize> 或 FxHashMap	大量唯一鍵，雜湊表提供快速累加
圖形渲染的頂點緩衝區	Vec<Vertex>（連續記憶體）	GPU 需要緊密排列的資料，快取友好
編譯器的 Symbol Table	HashMap<Symbol, SymbolInfo> + Vec<Scope>	雜湊表提供快速符號解析，Vec 管理作用域堆疊
日誌系統的唯一錯誤碼集合	HashSet<ErrorCode>	只需判斷是否已出現，HashSet 提供 O(1) 判斷

---

總結

• Vec：適合 連續存取、大量遍歷與尾端插入；提前配置容量可避免不必要的搬移。
• HashMap / HashSet：提供 常數時間 的查找與插入，適合 鍵值唯一、不需要排序的情況；注意負載因子與容量設定。
• BTreeMap / BTreeSet：在需要 有序遍歷、範圍查詢 或 快取友好 的情境下表現更佳。
• 最佳實踐：根據 資料特性（大小、是否有序、存取模式）選擇最適合的容器，並使用 with_capacity、reserve、shrink_to_fit 等方法主動管理記憶體。

透過正確的集合型別選擇與細部的效能調校，我們可以在 Rust 中寫出 安全、快速且可預測 的程式碼。祝開發順利，玩得開心！