透過雜湊映射儲存鍵值配對
我們最後一個常見的集合是雜湊映射(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); }
注意到我們需要先使用 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); }
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 在這之後就不能使用了,你可以試著使用它們並看看編譯器回傳什麼錯誤 }
我們之後就無法使用變數 field_name
和 field_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); }
此程式碼會印出 {"藍隊": 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); }
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); }
此程式碼會印出 {"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 技術文件有詳細介紹向量、字串與雜湊映射的所有方法,這對於這些練習題應該會很有幫助!
我們現在已經開始遇到有可能會運作失敗的複雜程式了,所以接下來正是來討論錯誤處理的時候!