透過雜湊映射儲存鍵值配對

我們最後一個常見的集合是雜湊映射(hash map)HashMap<K, V> 型別會儲存一個鍵(key)型別 K 對應到一個數值(value)型別 V。它透過雜湊函式(hashing function)來決定要將這些鍵與值放在記憶體何處。許多程式語言都有支援這種類型的資料結構,不過通常它們會提供不同的名稱,像是 hash、map、object、hash table、dictionary 或 associative array 等等。

雜湊映射適合用於當你不想像向量那樣用索引搜尋資料,而是透過一個可以為任意型別的鍵來搜尋的情況。舉例來說,在比賽中我們可以使用雜湊映射來儲存每隊的分數,每個鍵代表隊伍名稱,而每個值代表隊伍分數。給予一個隊伍名稱,你就能取得該隊伍分數。

我們會在此段落介紹雜湊映射的基本 API,但還有很多實用的函式定義在標準函式庫的 HashMap<K, V> 中,所以別忘了查閱標準函式庫的技術文件來瞭解更多資訊。

建立新的雜湊映射

其中一種建立空的雜湊映射的方式是使用 new 並透過 insert 加入新元素。在範例 8-20 我們追蹤兩支隊伍的分數,分別為藍隊與黃隊。藍隊初始分數有 10 分,黃隊則有 50 分。

fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("藍隊"), 10);
    scores.insert(String::from("黃隊"), 50);
}

範例 8-20:建立新的雜湊映射並插入一些鍵值

注意到我們需要先使用 use 將標準函式庫的 HashMap 集合引入。在我們介紹的三個常見集合中,此集合是最少被用到的,所以它並沒有包含在 prelude 內讓我們能自動參考。雜湊映射也沒有像前者那麼多標準函式庫提供的支援,像是內建建構它們的巨集。

和向量一樣,雜湊映射會將它們的資料儲存在堆積上。此 HashMap 的鍵是 String 型別而值是 i32 型別。和向量一樣,雜湊函式宣告後就都得是同類的,所有的鍵都必須是同型別,且所有的值也都必須是同型別。

取得雜湊映射的數值

我們可以透過 get 方法並提供鍵來取得其在雜湊映射對應的值,如範例 8-21 所示。

fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("藍隊"), 10);
    scores.insert(String::from("黃隊"), 50);

    let team_name = String::from("藍隊");
    let score = scores.get(&team_name).copied().unwrap_or(0);
}

範例 8-21:取得雜湊映射中藍隊的分數

score 在此將會是對應藍隊的分數,而且結果會是 10。結果是使用 Some 的原因是因為 get 回傳的是 Option<&V>。如果雜湊映射中該鍵沒有對應值的話,get 就會回傳 None。所以程式會需要透過我們在第六章談到的方式處理 Option

我們也可以使用 for 迴圈用類似的方式來遍歷雜湊映射中每個鍵值配對:

fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("藍隊"), 10);
    scores.insert(String::from("黃隊"), 50);

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

此程式會以任意順序印出每個配對:

黃隊: 50
藍隊: 10

雜湊映射與所有權

像是 i32 這種有實作 Copy 特徵的型別其數值可以被拷貝進雜湊映射之中。但對於像是 String 這種擁有所有權的數值則會被移動到雜湊映射,並成為該數值新的擁有者,如範例 8-22 所示。

fn main() {
    use std::collections::HashMap;

    let field_name = String::from("Favorite color");
    let field_value = String::from("藍隊");

    let mut map = HashMap::new();
    map.insert(field_name, field_value);
    // field_name 和 field_value 在這之後就不能使用了,你可以試著使用它們並看看編譯器回傳什麼錯誤
}

範例 8-22:展示當鍵值插入雜湊映射後就會擁有它們

我們之後就無法使用變數 field_namefield_value,因為它們的值已經透過呼叫 insert 被移入雜湊映射之中。

如果我們插入雜湊映射的數值是參考的話,該值就不會被移動到雜湊映射之中。不過該值的參考就必須一直有效,至少直到該雜湊映射離開作用域為止。我們會在第十章的「透過生命週期驗證參考」段落討落更多細節。

更新雜湊映射

雖然鍵值配對的數量可以增加,但每個鍵同一時間就只能有一個對應的值而已。(反之並不成立:比如藍隊黃隊可以同時都在 scores 雜湊映射內儲存 10 分)

當你想要改變雜湊映射的資料的話,你必須決定如何處理當一個鍵已經有一個值的情況。你可以不管舊的值,直接用新值取代。你也可以保留舊值、忽略新值,只有在該鍵尚未擁有對應數值時才賦值給它。或者你也可以將舊值與新值組合起來。讓我們看看分別怎麼處理吧!

覆蓋數值

如果我們在雜湊映射插入一個鍵值配對,然後又在相同鍵插入不同的數值的話,該鍵相對應的數值就會被取代。如範例 8-23 雖然我們呼叫了兩次 insert,但是雜湊映射只會保留一個鍵值配對,因為我們向藍隊的鍵插入了兩次數值。

fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("藍隊"), 10);
    scores.insert(String::from("藍隊"), 25);

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

範例 8-23:替換某個特定鍵對應的數值

此程式碼會印出 {"藍隊": 25},原本的數值 10 會被覆蓋。

只在鍵不存在的情況下插入鍵值

通常檢查雜湊映射有沒有存在某個特定的鍵值是很常見的。我們接下來的動作通常就是檢查如果鍵存在於雜湊映射的話,就不改變其值。但如果鍵不存在的話,就插入數值給它。

雜湊映射提供了一個特別的 API 叫做 entry 讓你可以用想要檢查的鍵作為參數。entry 方法的回傳值是一個列舉叫做 Entry,它代表了一個可能存在或不存在的數值。假設我們想要檢查黃隊的鍵有沒有對應的數值。如果沒有的話,我們想插入 50。而對藍隊也一樣。使用 entry API 的話,程式碼會長得像範例 8-24。

fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("藍隊"), 10);

    scores.entry(String::from("黃隊")).or_insert(50);
    scores.entry(String::from("藍隊")).or_insert(50);

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

範例 8-24:使用 entry 方法在只有該鍵尚無任何數值時插入數值

Entry 中的 or_insert 方法定義了如果 Entry 的鍵有對應的數值的話,就回傳該值的可變參考;如果沒有的話,那就插入參數作為新數值,並回傳此值的可變參考。這樣的技巧比我們親自寫邏輯還來的清楚,而且更有利於借用檢查器的檢查。

執行範例 8-25 的程式碼會印出 {"黃隊": 50, "藍隊": 10}。第一次 entry 的呼叫會對黃隊插入數值 50,因為黃隊尚未有任何數值。第二次 entry 的呼叫則不會改變雜湊映射,因為藍隊已經有數值 10。

依據舊值更新數值

雜湊映射還有另一種常見的用法是,依照鍵的舊數值來更新它。舉例來說,範例 8-25 展示了一支如何計算一些文字內每個單字各出現多少次的程式碼。我們使用雜湊映射,鍵為單字然後值為我們每次追蹤計算對應單字出現多少次的次數。如果我們是第一次看到該單字的話,我們插入數值 0。

fn main() {
    use std::collections::HashMap;

    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);
}

範例 8-25:使用雜湊映射儲存單字與次數來計算每個字出現的次數

此程式碼會印出 {"world": 2, "hello": 1, "wonderful": 1}。你可能會看到鍵值配對的順序不太一樣,回想一下「取得雜湊映射的數值」段落中提過遍歷雜湊映射的順序是任意的。

split_whitespace 方法會遍歷 text 中被空格分開來的切片。or_insert 方法會回傳該鍵對應數值的可變參考(&mut V)。在此我們將可變參考儲存在 count 變數中,所以要賦值的話,我們必須先使用 * 來解參考(dereference)count。可變參考會在 for 結束時離開作用域,所以所有的改變都是安全的且符合借用規則。

雜湊函式

HashMap 預設是使用一種叫做 SipHash 的雜湊函式(hashing function),這可以透過 1 雜湊表(hash table)抵禦阻斷服務(Denial of Service, DoS)的攻擊。這並不是最快的雜湊演算法,但為了提升安全性而犧牲一點效能是值得的。如果你做評測時覺得預設的雜湊函式太慢無法滿足你的需求的話,你可以指定不同的 hasher 來切換成其他雜湊函式。Hasher 是一個有實作 BuildHasher 特徵的型別。我們會在第十章討論到特徵以及如何實作它們。你不必從頭自己實作一個 hasher,crates.io 上有其他 Rust 使用者分享的函式庫,其中就有不少提供許多常見雜湊演算法的 hasher 實作。

總結

當你的程式需要儲存、取得、修改資料時,向量、字串與雜湊映射可以提供大量的功能。以下是一些你應該能夠解決的練習題:

  • 給予一個整數列表,請使用向量並回傳中位數(排序列表後正中間的值)以及眾數(出現最多次的值,雜湊映射在此應該會很有用)。
  • 將字串轉換成 pig latin。每個單字的第一個字母為子音的話,就將該字母移到單字後方,並加上「ay」,所以「first」會變成「irst-fay」。而單字第一個字母為母音的話,就在單字後方加上「hay」,所以「apple」會變成「apple-hay」。請注意要考慮到 UTF-8 編碼!
  • 使用雜湊映射與向量來建立文字介面,讓使用者能新增員工名字到公司內的一個部門。舉來來說「將莎莉加入工程部門」或「將阿米爾加入業務部門」。然後讓使用者可以索取一個部門所有的員工列表,或是依據部門用字典順序排序,取得公司內所有的員工。

標準函式庫的 API 技術文件有詳細介紹向量、字串與雜湊映射的所有方法,這對於這些練習題應該會很有幫助!

我們現在已經開始遇到有可能會運作失敗的複雜程式了,所以接下來正是來討論錯誤處理的時候!