【在主画面加入捷径】
       
【选择语系】
繁中 简中

Rust 程序设计教学:Map 和集合 (Set)

【赞助商连结】

    不论是数组或是向量,都是以数字做为其索引的容器,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 不符合本题目的条件。我们将某个数字拆开,每个位数各个放入集合中,若集合的长度大于等于数字的位数,则代表该数字的位数没有重覆,符合我们的条件。

    我们将这个程序的步骤以伪代码表示:

    这里提供程序代码范例,仅供参考:

    TAGS: MAP, RUST, SET