Rust 使用 Hash Map 儲(chǔ)存鍵值對(duì)

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

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

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

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

新建一個(gè)哈希 map

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

    use std::collections::HashMap;

    let mut scores = HashMap::new();

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

示例 8-20：新建一個(gè)哈希 map 并插入一些鍵值對(duì)

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

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

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

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

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

對(duì)于像 i32 這樣的實(shí)現(xiàn)了 Copy trait 的類型，其值可以拷貝進(jìn)哈希 map。對(duì)于像 String 這樣擁有所有權(quán)的值，其值將被移動(dòng)而哈希 map 會(huì)成為這些值的所有者，如示例 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 不再有效，
    // 嘗試使用它們看看會(huì)出現(xiàn)什么編譯錯(cuò)誤！

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

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

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

訪問(wèn)哈希 map 中的值

可以通過(guò) get 方法并提供對(duì)應(yīng)的鍵來(lái)從哈希 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：訪問(wèn)哈希 map 中儲(chǔ)存的藍(lán)隊(duì)分?jǐn)?shù)

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

可以使用與 vector 類似的方式來(lái)遍歷哈希 map 中的每一個(gè)鍵值對(duì)，也就是 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);
    }

這會(huì)以任意順序打印出每一個(gè)鍵值對(duì)：

Yellow: 50
Blue: 10

更新哈希 map

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

覆蓋一個(gè)值

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

    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：替換以特定鍵儲(chǔ)存的值

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

只在鍵沒(méi)有對(duì)應(yīng)值時(shí)插入

我們經(jīng)常會(huì)檢查某個(gè)特定的鍵是否有值，如果沒(méi)有就插入一個(gè)值。為此哈希 map 有一個(gè)特有的 API，叫做 entry，它獲取我們想要檢查的鍵作為參數(shù)。entry 函數(shù)的返回值是一個(gè)枚舉，Entry，它代表了可能存在也可能不存在的值。比如說(shuō)我們想要檢查黃隊(duì)的鍵是否關(guān)聯(lián)了一個(gè)值。如果沒(méi)有，就插入值 50，對(duì)于藍(lán)隊(duì)也是如此。使用 entry API 的代碼看起來(lái)像示例 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 方法只在鍵沒(méi)有對(duì)應(yīng)一個(gè)值時(shí)插入

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

運(yùn)行示例 8-25 的代碼會(huì)打印出 {"Yellow": 50, "Blue": 10}。第一個(gè) entry 調(diào)用會(huì)插入黃隊(duì)的鍵和值 50，因?yàn)辄S隊(duì)并沒(méi)有一個(gè)值。第二個(gè) entry 調(diào)用不會(huì)改變哈希 map 因?yàn)樗{(lán)隊(duì)已經(jīng)有了值 10。

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

另一個(gè)常見(jiàn)的哈希 map 的應(yīng)用場(chǎng)景是找到一個(gè)鍵對(duì)應(yīng)的值并根據(jù)舊的值更新它。例如，示例 8-26 中的代碼計(jì)數(shù)一些文本中每一個(gè)單詞分別出現(xiàn)了多少次。我們使用哈希 map 以單詞作為鍵并遞增其值來(lái)記錄我們遇到過(guò)幾次這個(gè)單詞。如果是第一次看到某個(gè)單詞，就插入值 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：通過(guò)哈希 map 儲(chǔ)存單詞和計(jì)數(shù)來(lái)統(tǒng)計(jì)出現(xiàn)次數(shù)

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

哈希函數(shù)

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

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

總結(jié)

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

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

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

我們已經(jīng)開(kāi)始接觸可能會(huì)有失敗操作的復(fù)雜程序了，這也意味著接下來(lái)是一個(gè)了解錯(cuò)誤處理的絕佳時(shí)機(jī)！