Rust 散列表 HashMap

vector 通过整型下标来存储值，而 HashMap（散列表）通过键（key）来存储值。HashMap 的键可以是布尔型、整型、字符串，或任意实现了 Eq 和 Hash trait 的其他类型。在下一节将进一步介绍。

和 vector 类似，HashMap 也是可增长的，但 HashMap 在占据了多余空间时还可以缩小自己。可以使用 HashMap::with_capacity(unit) 创建具有一定初始容量的 HashMap，也可以使用 HashMap::new() 来获得一个带有默认初始容量的 HashMap（这是推荐方式）。

use std::collections::HashMap;

fn call(number: &str) -> &str {
    match number {
        "798-1364" => "We're sorry, the call cannot be completed as dialed.
            Please hang up and try again.",
        "645-7689" => "Hello, this is Mr. Awesome's Pizza. My name is Fred.
            What can I get for you today?",
        _ => "Hi! Who is this again?"
    }
}

fn main() {
    let mut contacts = HashMap::new();

    contacts.insert("Daniel", "798-1364");
    contacts.insert("Ashley", "645-7689");
    contacts.insert("Katie", "435-8291");
    contacts.insert("Robert", "956-1745");

    // 接受一个引用并返回 Option<&V>
    match contacts.get(&"Daniel") {
        Some(&number) => println!("Calling Daniel: {}", call(number)),
        _ => println!("Don't have Daniel's number."),
    }

    // 如果被插入的值为新内容，那么 `HashMap::insert()` 返回 `None`，
    // 否则返回 `Some(value)`
    contacts.insert("Daniel", "164-6743");

    match contacts.get(&"Ashley") {
        Some(&number) => println!("Calling Ashley: {}", call(number)),
        _ => println!("Don't have Ashley's number."),
    }

    contacts.remove(&("Ashley"));

    // `HashMap::iter()` 返回一个迭代器，该迭代器以任意顺序举出
    // (&'a key, &'a value) 对。
    for (contact, &number) in contacts.iter() {
        println!("Calling {}: {}", contact, call(number));
    }
}

更改或自定义关键字类型

任何实现了 Eq 和 Hash trait 的类型都可以充当 HashMap 的键。这包括：

bool （当然这个用处不大，因为只有两个可能的键）
int，unit，以及其他整数类型
String 和 &str（友情提示：如果使用 String 作为键来创建 HashMap，则可以将 &str 作为散列表的 .get() 方法的参数，以获取值）

注意到 f32 和 f64 没有实现 Hash，这很大程度上是由于若使用浮点数作为散列表的键，浮点精度误差会很容易导致错误。

对于所有的集合类（collection class），如果它们包含的类型都分别实现了 Eq 和 Hash，那么这些集合类也就实现了 Eq 和 Hash。例如，若 T 实现了 Hash，则 Vec 也实现了 Hash。

对自定义类型可以轻松地实现 Eq 和 Hash，只需加上一行代码：#[derive(PartialEq, Eq, Hash)]。

编译器将会完成余下的工作。如果你想控制更多的细节，你可以手动实现 Eq 和/或 Hash。本指南不包含实现 Hash 的细节内容。

为了试验 HashMap 中的 struct，让我们试着做一个非常简易的用户登录系统：

use std::collections::HashMap;

// Eq 要求你对此类型推导 PartiaEq。
#[derive(PartialEq, Eq, Hash)]
struct Account<'a>{
    username: &'a str,
    password: &'a str,
}

struct AccountInfo<'a>{
    name: &'a str,
    email: &'a str,
}

type Accounts<'a> = HashMap<Account<'a>, AccountInfo<'a>>;

fn try_logon<'a>(accounts: &Accounts<'a>,
        username: &'a str, password: &'a str){
    println!("Username: {}", username);
    println!("Password: {}", password);
    println!("Attempting logon...");

    let logon = Account {
        username: username,
        password: password,
    };

    match accounts.get(&logon) {
        Some(account_info) => {
            println!("Successful logon!");
            println!("Name: {}", account_info.name);
            println!("Email: {}", account_info.email);
        },
        _ => println!("Login failed!"),
    }
}

fn main(){
    let mut accounts: Accounts = HashMap::new();

    let account = Account {
        username: "j.everyman",
        password: "password123",
    };

    let account_info = AccountInfo {
        name: "John Everyman",
        email: "j.everyman@email.com",
    };

    accounts.insert(account, account_info);

    try_logon(&accounts, "j.everyman", "psasword123");

    try_logon(&accounts, "j.everyman", "password123");
}

散列集 HashSet

请把 HashSet 当成这样一个 HashMap：我们只关心其中的键而非值（HashSet 实际上只是对 HashMap<T, ()> 的封装）。

你可能会问：“这有什么意义呢？我完全可以将键存储到一个 Vec 中呀。”

HashSet 的独特之处在于，它保证了不会出现重复的元素。这是任何 set 集合类型（set collection）遵循的规定。HashSet 只是它的一个实现。（参见：BTreeSet）

如果插入的值已经存在于 HashSet 中（也就是，新值等于已存在的值，并且拥有相同的散列值），那么新值将会替换旧的值。

如果你不想要一样东西出现多于一次，或者你要判断一样东西是不是已经存在，这种做法就很有用了。

不过集合（set）可以做更多的事。

集合（set）拥有 4 种基本操作（下面的调用全部都返回一个迭代器）：

union（并集）：获得两个集合中的所有元素（不含重复值）。
difference（差集）：获取属于第一个集合而不属于第二集合的所有元素。
intersection（交集）：获取同时属于两个集合的所有元素。
symmetric_difference（对称差）：获取所有只属于其中一个集合，而不同时属于两个集合的所有元素。

在下面的例子中尝试使用这些操作。

use std::collections::HashSet;

fn main() {
    let mut a: HashSet<i32> = vec!(1i32, 2, 3).into_iter().collect();
    let mut b: HashSet<i32> = vec!(2i32, 3, 4).into_iter().collect();

    assert!(a.insert(4));
    assert!(a.contains(&4));

    // 如果值已经存在，那么 `HashSet::insert()` 返回 false。
    assert!(b.insert(4), "Value 4 is already in set B!");
    // 改正 ^ 将此行注释掉。

    b.insert(5);

    // 若一个集合（collection）的元素类型实现了 `Debug`，那么该集合也就实现了 `Debug`。
    // 这通常将元素打印成这样的格式 `[elem1, elem2, ...]
    println!("A: {:?}", a);
    println!("B: {:?}", b);

    // 乱序打印 [1, 2, 3, 4, 5]。
    println!("Union: {:?}", a.union(&b).collect::<Vec<&i32>>());

    // 这将会打印出 [1]
    println!("Difference: {:?}", a.difference(&b).collect::<Vec<&i32>>());

    // 乱序打印 [2, 3, 4]。
    println!("Intersection: {:?}", a.intersection(&b).collect::<Vec<&i32>>());

    // 打印 [1, 5]
    println!("Symmetric Difference: {:?}",
             a.symmetric_difference(&b).collect::<Vec<&i32>>());
}

豆子笔记

Rust 散列表 HashMap

更改或自定义关键字类型

散列集 HashSet