Rust 程式設計:Map 和集合

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

Map

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

Map

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

註:一般中文書籍對於 map 傾向不翻譯,保持原始名稱,本教程依循此慣例。

使用 Map

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

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

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

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

走訪 Map

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

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

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

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

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

集合

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

使用集合

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

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

集合的二元操作

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

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

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

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

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

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