Rust 集合型別 – 雜湊映射（HashMap）

簡介

在日常開發中，我們常常需要 「依鍵取值」 的資料結構，例如統計字詞出現次數、快取資料或是實作簡易的資料庫索引。Rust 標準函式庫提供的 HashMap<K, V> 正是為此而設計的通用雜湊映射。它結合了 O(1) 的平均存取效能與安全的所有權模型，讓開發者能在不犧牲效能的前提下，享受到編譯期的嚴格檢查。

本篇文章將從 概念、實作、常見陷阱 與 最佳實踐 逐步說明，適合剛接觸 Rust 的初學者，也能為已有基礎的開發者提供進階的使用技巧。

---

核心概念

1. 為什麼選擇 HashMap？

• 快速查找：在平均情況下，插入、查找與刪除的時間複雜度皆為 O(1)。
• 靈活的鍵值類型：只要鍵 K 實作了 Eq 與 Hash，就能作為雜湊映射的鍵。
• 所有權安全：Rust 會在編譯期檢查借用與所有權，避免常見的競爭條件與記憶體錯誤。

2. 基本操作

操作	方法	說明
建立	HashMap::new()	建立空的雜湊映射
插入	insert(key, value)	若鍵已存在會回傳舊值
取值	get(&key)、get_mut(&key)	回傳 Option<&V> 或 Option<&mut V>
移除	remove(&key)	移除並回傳被刪除的值
迭代	iter()、iter_mut()、into_iter()	依照需求取得只讀、可變或所有權迭代子

下面的範例會一步步示範這些操作。

程式碼範例 1：建立與基本插入/取值

use std::collections::HashMap;

fn main() {
    // 建立一個空的 HashMap，鍵是字串，值是整數
    let mut scores: HashMap<String, i32> = HashMap::new();

    // 插入資料
    scores.insert("Alice".to_string(), 10);
    scores.insert("Bob".to_string(), 20);

    // 取值：若鍵不存在會得到 None
    if let Some(alice_score) = scores.get("Alice") {
        println!("Alice 的分數是 {}", alice_score);
    }

    // 使用 entry API 更新或插入
    scores.entry("Charlie".to_string()).or_insert(0);
    println!("{:?}", scores);
}

重點：HashMap 需要 use std::collections::HashMap;，且插入的鍵必須是 擁有所有權（如 String），或使用 &'static str 等靜態字面值。

3. 所有權與借用的互動

HashMap 在插入鍵值時會 取得鍵和值的所有權。因此，插入後原變數若是 String，將無法再被使用，除非使用 clone()（會產生額外的記憶體拷貝）或 &str 參考。

let key = String::from("team");
let value = 5;
let mut map = HashMap::new();
map.insert(key, value); // key 的所有權已移動到 map

// 下面這行會編譯錯誤：value 已被移動
// println!("{}", key);

如果希望保留原始變數，可以使用 借用（&str）作為鍵，前提是雜湊映射的鍵型別支援借用（如 HashMap<&str, i32>）：

let mut map: HashMap<&str, i32> = HashMap::new();
let key = "team";
map.insert(key, 5);
println!("仍可使用 key: {}", key);

4. entry API：避免重複插入的慣用寫法

entry 會回傳一個 Entry 列舉，提供 or_insert、or_insert_with、and_modify 等方法，讓我們在「鍵不存在時插入」或「鍵已存在時修改」的情境下寫出更簡潔的程式碼。

use std::collections::HashMap;

fn main() {
    let mut word_counts = HashMap::new();

    let text = "hello world hello rust";
    for word in text.split_whitespace() {
        // 若 word 不存在則插入 0，接著再加 1
        *word_counts.entry(word).or_insert(0) += 1;
    }

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

5. 迭代與排序

HashMap 本身不保證元素的順序。如果需要依鍵或值排序，必須先收集到 Vec 再排序。

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("c", 3);
    map.insert("a", 1);
    map.insert("b", 2);

    // 依鍵字母排序
    let mut kv_vec: Vec<(&str, i32)> = map.iter().map(|(&k, &v)| (k, v)).collect();
    kv_vec.sort_by_key(|&(k, _)| k);
    println!("依鍵排序: {:?}", kv_vec);
}

6. 自訂雜湊函式

預設的雜湊演算法是 SipHash，在大多數情況下已足夠安全與快速。但在需要 更高效能（如大量整數鍵）或 特定安全需求 時，可自行指定雜湊建構子：

use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use std::collections::hash_map::DefaultHasher;

// 使用 std::collections::hash_map::RandomState（預設）或自訂
type MyHasher = BuildHasherDefault<DefaultHasher>;

fn main() {
    let mut map: HashMap<u64, &str, MyHasher> = HashMap::default();
    map.insert(42, "answer");
    println!("{:?}", map);
}

---

常見陷阱與最佳實踐

陷阱	說明	解決方式
鍵值被移動	插入後原變數無法再使用	使用 clone()（若成本可接受）或改用 &str / Arc<String>
迭代時同時修改	直接在 for (k, v) in map.iter_mut() 內插入或刪除會 panic	使用 entry 或先收集要刪除的鍵，再統一刪除
HashMap 失去順序	期待輸出順序與插入順序相同	若需要有序映射，考慮 BTreeMap
大量重建	每次 insert 都重新計算雜湊，效能下降	事先使用 with_capacity 預估容量
自訂雜湊的安全性	使用不安全的雜湊函式可能導致 DoS 攻擊	除非確定需求，保持預設 SipHash

最佳實踐

1. 預先分配容量：HashMap::with_capacity(預估鍵數) 可以減少重新分配的開銷。
2. 盡量使用 entry：它讓「先檢查後插入」的模式更安全且更具可讀性。
3. 避免在迭代中直接刪除：先收集要刪除的鍵，或使用 retain 方法。
4. 選擇合適的鍵型別：若鍵是小型整數，使用 u32、usize 等原始類型可獲得最佳效能。
5. 考慮 BTreeMap：當需要有序遍歷或範圍查詢時，BTreeMap 會比 HashMap 更合適。

---

實際應用場景

1. 文字統計
   計算文件中每個單詞出現的次數，常用 HashMap<String, usize> 搭配 entry。

2. 快取（Cache）
   在 Web 服務或 CLI 工具中，使用 HashMap<RequestKey, Response> 以 O(1) 時間取得先前計算結果，提升效能。

3. 圖形演算法
   在 BFS/DFS 中，使用 HashMap<NodeId, bool> 記錄節點是否已訪問。

4. 設定與參數解析
   讀取 key=value 格式的設定檔時，可直接把每一行解析成 HashMap<String, String>，方便後續查詢。

5. 關聯式資料
   小型資料庫或記憶體內的索引結構，使用 HashMap<PrimaryKey, Record> 直接對應資料列。

---

總結

• HashMap 是 Rust 中最常用的 鍵值對集合，提供 常數時間 的插入、查找與刪除。
• 理解 所有權與借用 的互動是避免鍵值被意外移動的關鍵。
• entry API 是處理「若不存在則插入」或「若已存在則更新」的慣用寫法，能寫出更簡潔且安全的程式碼。
• 常見的陷阱包括迭代時修改、忘記預分配容量以及對順序的錯誤假設，遵循 最佳實踐 可有效提升效能與可讀性。
• 從文字統計到快取、圖形演算法與設定解析，HashMap 的應用範圍廣泛，是每位 Rust 開發者必備的工具。

掌握了上述概念與技巧後，你就能在 實務專案 中自信地使用 HashMap，寫出既 高效 又 安全 的程式碼。祝開發順利！