Rust 使用 Hash Map 儲存鍵值對

ch08-03-hash-maps.md
commit 1fd890031311612e54965f7f800a8c8bd4464663

最后介紹的常用集合類型是 哈希 map（hash map）。HashMap<K, V> 類型儲存了一個鍵類型 K 對應(yīng)一個值類型 V 的映射。它通過一個 哈希函數(shù)（hashing function）來實現(xiàn)映射，決定如何將鍵和值放入內(nèi)存中。很多編程語言支持這種數(shù)據(jù)結(jié)構(gòu)，不過通常有不同的名字：哈希、map、對象、哈希表或者關(guān)聯(lián)數(shù)組，僅舉幾例。

哈希 map 可以用于需要任何類型作為鍵來尋找數(shù)據(jù)的情況，而不是像 vector 那樣通過索引。例如，在一個游戲中，你可以將每個團(tuán)隊的分?jǐn)?shù)記錄到哈希 map 中，其中鍵是隊伍的名字而值是每個隊伍的分?jǐn)?shù)。給出一個隊名，就能得到他們的得分。

本章我們會介紹哈希 map 的基本 API，不過還有更多吸引人的功能隱藏于標(biāo)準(zhǔn)庫在 HashMap<K, V> 上定義的函數(shù)中。一如既往請查看標(biāo)準(zhǔn)庫文檔來了解更多信息。

新建一個哈希 map

可以使用 new 創(chuàng)建一個空的 HashMap，并使用 insert 增加元素。在示例 8-20 中我們記錄兩支隊伍的分?jǐn)?shù)，分別是藍(lán)隊和黃隊。藍(lán)隊開始有 10 分而黃隊開始有 50 分：

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

示例 8-20：新建一個哈希 map 并插入一些鍵值對

注意必須首先 use 標(biāo)準(zhǔn)庫中集合部分的 HashMap。在這三個常用集合中，HashMap 是最不常用的，所以并沒有被 prelude 自動引用。標(biāo)準(zhǔn)庫中對 HashMap 的支持也相對較少，例如，并沒有內(nèi)建的構(gòu)建宏。

像 vector 一樣，哈希 map 將它們的數(shù)據(jù)儲存在堆上，這個 HashMap 的鍵類型是 String 而值類型是 i32。類似于 vector，哈希 map 是同質(zhì)的：所有的鍵必須是相同類型，值也必須都是相同類型。

另一個構(gòu)建哈希 map 的方法是在一個元組的 vector 上使用迭代器（iterator）和 collect 方法，其中每個元組包含一個鍵值對。我們會在第十三章的 “Processing a Series of Items with Iterators” 部分 介紹迭代器及其關(guān)聯(lián)方法。collect 方法可以將數(shù)據(jù)收集進(jìn)一系列的集合類型，包括 HashMap。例如，如果隊伍的名字和初始分?jǐn)?shù)分別在兩個 vector 中，可以使用 zip 方法來創(chuàng)建一個元組的迭代器，其中 “Blue” 與 10 是一對，依此類推。接著就可以使用 collect 方法將這個元組的迭代器轉(zhuǎn)換成一個 HashMap，如示例 8-21 所示：

    use std::collections::HashMap;

    let teams = vec![String::from("Blue"), String::from("Yellow")];
    let initial_scores = vec![10, 50];

    let mut scores: HashMap<_, _> =
        teams.into_iter().zip(initial_scores.into_iter()).collect();

示例 8-21：用隊伍列表和分?jǐn)?shù)列表創(chuàng)建哈希 map

這里 HashMap<_, _> 類型注解是必要的，因為可能 collect 為很多不同的數(shù)據(jù)結(jié)構(gòu)，而除非顯式指定否則 Rust 無從得知你需要的類型。但是對于鍵和值的類型參數(shù)來說，可以使用下劃線占位，而 Rust 能夠根據(jù) vector 中數(shù)據(jù)的類型推斷出 HashMap 所包含的類型。在示例 8-21 中，鍵（key）類型是 String，值（value）類型是 i32，與示例 8-20 的類型一樣。

哈希 map 和所有權(quán)

對于像 i32 這樣的實現(xiàn)了 Copy trait 的類型，其值可以拷貝進(jìn)哈希 map。對于像 String 這樣擁有所有權(quán)的值，其值將被移動而哈希 map 會成為這些值的所有者，如示例 8-22 所示：

    use std::collections::HashMap;

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

    let mut map = HashMap::new();
    map.insert(field_name, field_value);
    // 這里 field_name 和 field_value 不再有效，
    // 嘗試使用它們看看會出現(xiàn)什么編譯錯誤！

示例 8-22：展示一旦鍵值對被插入后就為哈希 map 所擁有

當(dāng) insert 調(diào)用將 field_name 和 field_value 移動到哈希 map 中后，將不能使用這兩個綁定。

如果將值的引用插入哈希 map，這些值本身將不會被移動進(jìn)哈希 map。但是這些引用指向的值必須至少在哈希 map 有效時也是有效的。第十章 “生命周期與引用有效性” 部分將會更多的討論這個問題。

訪問哈希 map 中的值

可以通過 get 方法并提供對應(yīng)的鍵來從哈希 map 中獲取值，如示例 8-23 所示：

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    let team_name = String::from("Blue");
    let score = scores.get(&team_name);

示例 8-23：訪問哈希 map 中儲存的藍(lán)隊分?jǐn)?shù)

這里，score 是與藍(lán)隊分?jǐn)?shù)相關(guān)的值，應(yīng)為 Some(10)。因為 get 返回 Option<V>，所以結(jié)果被裝進(jìn) Some；如果某個鍵在哈希 map 中沒有對應(yīng)的值，get 會返回 None。這時就要用某種第六章提到的方法之一來處理 Option。

可以使用與 vector 類似的方式來遍歷哈希 map 中的每一個鍵值對，也就是 for 循環(huán)：

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

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

這會以任意順序打印出每一個鍵值對：

Yellow: 50
Blue: 10

更新哈希 map

盡管鍵值對的數(shù)量是可以增長的，不過任何時候，每個鍵只能關(guān)聯(lián)一個值。當(dāng)我們想要改變哈希 map 中的數(shù)據(jù)時，必須決定如何處理一個鍵已經(jīng)有值了的情況?？梢赃x擇完全無視舊值并用新值代替舊值?？梢赃x擇保留舊值而忽略新值，并只在鍵 沒有 對應(yīng)值時增加新值?；蛘呖梢越Y(jié)合新舊兩值。讓我們看看這分別該如何處理！

覆蓋一個值

如果我們插入了一個鍵值對，接著用相同的鍵插入一個不同的值，與這個鍵相關(guān)聯(lián)的舊值將被替換。即便示例 8-24 中的代碼調(diào)用了兩次 insert，哈希 map 也只會包含一個鍵值對，因為兩次都是對藍(lán)隊的鍵插入的值：

    use std::collections::HashMap;

    let mut scores = HashMap::new();

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

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

示例 8-24：替換以特定鍵儲存的值

這會打印出 {"Blue": 25}。原始的值 10 則被覆蓋了。

只在鍵沒有對應(yīng)值時插入

我們經(jīng)常會檢查某個特定的鍵是否有值，如果沒有就插入一個值。為此哈希 map 有一個特有的 API，叫做 entry，它獲取我們想要檢查的鍵作為參數(shù)。entry 函數(shù)的返回值是一個枚舉，Entry，它代表了可能存在也可能不存在的值。比如說我們想要檢查黃隊的鍵是否關(guān)聯(lián)了一個值。如果沒有，就插入值 50，對于藍(lán)隊也是如此。使用 entry API 的代碼看起來像示例 8-25 這樣：

    use std::collections::HashMap;

    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);

    scores.entry(String::from("Yellow")).or_insert(50);
    scores.entry(String::from("Blue")).or_insert(50);

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

示例 8-25：使用 entry 方法只在鍵沒有對應(yīng)一個值時插入

Entry 的 or_insert 方法在鍵對應(yīng)的值存在時就返回這個值的可變引用，如果不存在則將參數(shù)作為新值插入并返回新值的可變引用。這比編寫自己的邏輯要簡明的多，另外也與借用檢查器結(jié)合得更好。

運行示例 8-25 的代碼會打印出 {"Yellow": 50, "Blue": 10}。第一個 entry 調(diào)用會插入黃隊的鍵和值 50，因為黃隊并沒有一個值。第二個 entry 調(diào)用不會改變哈希 map 因為藍(lán)隊已經(jīng)有了值 10。

根據(jù)舊值更新一個值

另一個常見的哈希 map 的應(yīng)用場景是找到一個鍵對應(yīng)的值并根據(jù)舊的值更新它。例如，示例 8-26 中的代碼計數(shù)一些文本中每一個單詞分別出現(xiàn)了多少次。我們使用哈希 map 以單詞作為鍵并遞增其值來記錄我們遇到過幾次這個單詞。如果是第一次看到某個單詞，就插入值 0。

    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-26：通過哈希 map 儲存單詞和計數(shù)來統(tǒng)計出現(xiàn)次數(shù)

這會打印出 {"world": 2, "hello": 1, "wonderful": 1}。split_whitespace 方法會迭代 text 的值由空格分隔的子 slice。or_insert 方法返回這個鍵的值的一個可變引用（&mut V）。這里我們將這個可變引用儲存在 count 變量中，所以為了賦值必須首先使用星號（*）解引用 count。這個可變引用在 for 循環(huán)的結(jié)尾離開作用域，這樣所有這些改變都是安全的并符合借用規(guī)則。

哈希函數(shù)

HashMap 默認(rèn)使用一種叫做 SipHash 的哈希函數(shù)，它可以抵御涉及哈希表（hash table）¹ 的拒絕服務(wù)（Denial of Service, DoS）攻擊。然而這并不是可用的最快的算法，不過為了更高的安全性值得付出一些性能的代價。如果性能監(jiān)測顯示此哈希函數(shù)非常慢，以致于你無法接受，你可以指定一個不同的 hasher 來切換為其它函數(shù)。hasher 是一個實現(xiàn)了 BuildHasher trait 的類型。第十章會討論 trait 和如何實現(xiàn)它們。你并不需要從頭開始實現(xiàn)你自己的 hasher；crates.io 有其他人分享的實現(xiàn)了許多常用哈希算法的 hasher 的庫。

¹ https://en.wikipedia.org/wiki/SipHash

總結(jié)

vector、字符串和哈希 map 會在你的程序需要儲存、訪問和修改數(shù)據(jù)時幫助你。這里有一些你應(yīng)該能夠解決的練習(xí)問題：

• 給定一系列數(shù)字，使用 vector 并返回這個列表的中位數(shù)（排列數(shù)組后位于中間的值）和眾數(shù)（mode，出現(xiàn)次數(shù)最多的值；這里哈希 map 會很有幫助）。
• 將字符串轉(zhuǎn)換為 Pig Latin，也就是每一個單詞的第一個輔音字母被移動到單詞的結(jié)尾并增加 “ay”，所以 “first” 會變成 “irst-fay”。元音字母開頭的單詞則在結(jié)尾增加 “hay”（“apple” 會變成 “apple-hay”）。牢記 UTF-8 編碼！
• 使用哈希 map 和 vector，創(chuàng)建一個文本接口來允許用戶向公司的部門中增加員工的名字。例如，“Add Sally to Engineering” 或 “Add Amir to Sales”。接著讓用戶獲取一個部門的所有員工的列表，或者公司每個部門的所有員工按照字典序排列的列表。

標(biāo)準(zhǔn)庫 API 文檔中描述的這些類型的方法將有助于你進(jìn)行這些練習(xí)！

我們已經(jīng)開始接觸可能會有失敗操作的復(fù)雜程序了，這也意味著接下來是一個了解錯誤處理的絕佳時機(jī)！