[Rust] 程式設計教學:映射 (Map) 和集合 (Set)

【分享本文】
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

    前言

    不論是陣列或是向量,都是以數字做為其索引的容器,映射 (map) 則可以用其他的資料型別做為索引值,進行快速查詢。集合 (set) 實作數學上集合論 (set theory) 的概念,和映射的概念有一些關連。

    映射 (Map)

    映射 (map) 是以一對 鍵 (key) : 值 (value) 為單位的容器,透過特定的鍵可以找到相對應的值。以鍵找尋值的過程,透過雜湊函數 (hash function) 來轉換,如以下示意圖:

    Map

    在資料結構的書籍中,這種容器稱為雜湊表 (hash table),在其他的程式語言中可能稱為雜湊 (hash)、字典 (dictionary)、關連性陣列 (associative array) 等。

    使用映射 (Map)

    Rust 內建語法不直接支援映射,而是透過其標準函式庫進行物件呼叫。如下例:

    // Call HashMap class in Rust standard library
    use std::collections::HashMap;
     
    fn main() {
        // Create an empty map
        let mut hash = HashMap::new();  // HashMap<&str, &str>
     
        // Insert (key, value) pairs into the map
        hash.insert("one", "eins");
        hash.insert("two", "zwei");
        hash.insert("three", "drei");
     
        // Get value by key
        assert_eq!(hash.get("one"), Some(&"eins"));
     
        // Get None when (key, value) doesn't exist
        assert_eq!(hash.get("four"), None);
    }
    

    Rust 的映射透過鍵取值時,得到的是 Option<& value> 而非直接得到值,我們在先前有提過,這牽涉到 Rust 處理錯誤的方式,由於在映射中取值時,有可能取到不存在的值,Rust 以 Option 這個特殊容器包裝值,若可以得到值,就回傳一個包在 Option 內的值的參考,若無法得到值,則回傳 None。如果要得到值,可參考以下範例:

    use std::collections::HashMap;
     
    fn main() {
        let mut hash = HashMap::new();
     
        hash.insert("one", "eins");
        hash.insert("two", "zwei");
        hash.insert("three", "drei");
     
        let data = match hash.get("one") {
            None => "",
            Some(v) => *v
        };
        assert_eq!(data, "eins");
    }
    

    要注意的是,在本例的 match 中,若映射回傳空值,不能直接回傳 None 而要回傳空字串,這是因為 Rust 要求回傳的型別需一致。若很確定該鍵值對的確存在,可參考以下方式取值:

    use std::collections::HashMap;
     
    fn main() {
        let mut hash = HashMap::new();
     
        hash.insert("one", "eins");
        hash.insert("two", "zwei");
        hash.insert("three", "drei");
     
        let data = *(hash.get("one").unwrap());
        assert_eq!(data, "eins");
    }
    

    在本例中,我們直接將該 Option 容器解開取得參考後,再解參考得到值。

    走訪映射 (Map)

    若要走訪映射,可以依映射的鍵來走訪,範例如下:

    use std::collections::HashMap;
     
    fn main() {
        let mut hash = HashMap::new();
     
        hash.insert("one", "eins");
        hash.insert("two", "zwei");
        hash.insert("three", "drei");
     
        // Iterate the hash by key
        for k in hash.keys() {
            println!("{} => {}", k, *hash.get(k).unwrap());
        }
    }
    

    要注意的是,HashMap 不保證鍵的順序,讀者可試著多執行幾次本程式,即可發現此現象。典型的雜湊表不保證鍵的順序,除非某個函式庫有註明其雜湊表的實作有儲存鍵的順序,讀者應該視雜湊表的鍵為無序的。

    或是依其鍵/值對來走訪,範例如下:

    use std::collections::HashMap;
     
    fn main() {
        let mut hash = HashMap::new();
     
        hash.insert("one", "eins");
        hash.insert("two", "zwei");
        hash.insert("three", "drei");
     
        // Iterate the hash by (key, value) pair
        for (k, v) in hash.iter() {
            println!("{} => {}", k, *v);
        }
    }
    

    若有需要,也可依其值來走訪,範例如下:

    use std::collections::HashMap;
     
    fn main() {
        let mut hash = HashMap::new();
     
        hash.insert("one", "eins");
        hash.insert("two", "zwei");
        hash.insert("three", "drei");
     
        // Iterate the hash by value
        for v in hash.values() {
            println!("{}", *v);
        }
    }
    

    要注意的是,雜湊表只能由鍵推得值,無法倒過來由值推得鍵。雜湊表的鍵是唯一的,但值可以重覆,使用時必需要注意這個觀念。

    集合 (Set)

    集合 (set) 是一個數學上的概念,表示一群不重覆的無序物件,對於集合的相關概念,可見集合論 (set theory) 的教材。由於集合的概念在程式設計中相當實用,有許多高階語言都實作集合這種容器。集合可以用雜湊表實作,以雜湊表來說,集合可視為值為空值的雜湊表。Rust 的 HashSet 內部的確是以 HashMap 來做為儲存資料的容器。

    使用集合

    這裡用一個簡單的範例展示如何使用集合:

    // Call HashSet from library
    use std::collections::HashSet;
     
    fn main() {
        // Create an empty set
        let mut set = HashSet::new();
     
        // Insert item into the set
        set.insert("C++");
        set.insert("Java");
        set.insert("Python");
        set.insert("Rust");
        set.insert("Go");
     
        // Check the property of the set
        assert_eq!(set.len(), 5);
        assert_eq!(set.contains("Rust"), true);
        assert_eq!(set.contains("Lisp"), false);
     
        // Remove item from the set
        set.remove("Python");
     
        // Check the property of the set
        assert_eq!(set.len(), 4);
        assert_eq!(set.contains("Rust"), true);
        assert_eq!(set.contains("Python"), false);
    }
    

    雖然 HashSet 內部使用 HashMap,但簡化了介面,使用者不需要直接操作 HashMap。

    集合的二元操作

    集合可以實現一些集合論的二元操作,像是聯集 (unino)、交集 (intersection)、差集 (difference) 等。以下用實例展示這些操作:

    // Call HashSet from library
    use std::collections::HashSet;
     
    fn main() {
        // Get two sets from two arrays
        let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
        let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect();
     
        // Get the union of the two sets
        let union: HashSet<_> = a.union(&b).cloned().collect();
        assert_eq!(union, [1, 2, 3, 4].iter().cloned().collect());
     
        // Get the intersection of the two sets
        let intersection: HashSet<_> = a.intersection(&b).cloned().collect();
        assert_eq!(intersection, [2, 3].iter().cloned().collect());
     
        // Get the difference of a from b
        let diff: HashSet<_> = a.difference(&b).cloned().collect();
        assert_eq!(diff, [1].iter().cloned().collect());
    }
    

    要注意的是,在這裡,我們傳入的是集合的參考而非集合本身,一方面是為了節省傳遞資料的時間,另一方面牽涉到 Rust 的所有權 (ownership),我們將於後續章節中介紹這些概念。

    (案例選讀) 位數不重覆的數字

    在本節中,我們處理以下的問題:選出位數不重覆的數字。例如:435 的三個數字都不重覆,就是一個符合條件的數字;而 919 則因為有重覆的 9 不符合本題目的條件。我們將某個數字拆開,每個位數各個放入集合中,若集合的長度大於等於數字的位數,則代表該數字的位數沒有重覆,符合我們的條件。

    我們將這個程式的步驟以虛擬碼表示:

    Let N a number with j digits
    Let S a set
     
    Let d(x) the digit of N at point x
    for i from 1 to j {
        Insert d(i) into S
    }
     
    Let len(x) the length of x
    if len(S) >= len(N) {
        N fits our criteria
    }
    

    這裡提供程式碼範例,僅供參考:

    use std::io;
    use std::io::Write;
    use std::process;
    use std::collections::HashSet;
     
    fn main() {
        // Prompt for user input
        print!("Input a number: ");
        let _ = io::stdout().flush();
     
        // Receive user input
        let mut input = String::new();
        io::stdin()
            .read_line(&mut input)
            .expect("failed to read from stdin");
     
        // Parse the number
        let n = match input.trim().parse::<u32>() {
            Ok(i) => i,
            Err(_) => {
                println!("Invalid integer");
     
                // Exit the program with abnormal status code
                process::exit(1);
            }
        };
     
        let x: i32 = 10;
        for i in 1..(x.pow(n)) {
            /* Convert number to an iterator of char.
               Then, insert char to set. */
            let num_string = i.to_string();
            let mut chars = num_string.chars();
            let mut set = HashSet::new();
            let mut c = chars.next();
            while c != None {
                set.insert(c);
                c = chars.next();
            }
     
            // Get the digit number of i
            let mut digit = 0;
            let mut j = i;
            while j > 0 {
                j = j / 10;
                digit += 1;
            }
     
            // Check whether i fits our criteria
            if set.len() as i32 >= digit {
                // Show i in console
                print!("{} ", i);
            }
        }
     
        // Print tailing newline
        println!("");
    }
    
    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
    【追蹤新文章】
    Facebook Twitter Plurk
    標籤: MAP, RUST, SET