8. Rust 集合

• 8.1 Vector
• 8.2 Vector 的枚举
• 8.3 String
• 8.4 String 的访问
  • 字符串切片
  • 遍历字符串
• 8.5 HashMap
  • 创建 HashMap
  • HashMap 和所有权
  • 访问 HashMap 中的值
  • 更新 HashMap
  • Hash 函数
• 8.6 总结

8.1 Vector

使用 Vector 可存储多个值。

• 由标准库提供
• 可存储多个值
• 只能存储相同类型的值
• 值在内存中连续存放

使用 Vec<T> 声明 Vector，使用 Vec::new() 创建空 Vector。

fn main() {
    let v: Vec<i32> = Vec::new();
}

使用 vec! 宏可以从列表创建 Vector。

fn main() {
    let v = vec![1, 2, 3];
}

可以使用引用来访问 Vector 中的元素。

fn main() {
    let v = vec![1, 2, 3];
    let third: &i32 = &v[2];
    println!("The third element is {}", third);
}

可以使用 get() 方法来访问 Vector 中的元素。

fn main() {
    let v = vec![1, 2, 3];
    match v.get(2) {
        Some(third) => println!("The third element is {}", third),
        None => println!("There is no third element."),
    }
}

Vector 也遵循所有权和借用规则，不能在同一个作用域内同时存在可变和不可变引用。

fn main() {
    let mut v = vec![1, 2, 3, 4, 5];
    let first = &v[0];
    v.push(6); // error: cannot borrow `v` as mutable because it is also borrowed as immutable
    println!("The first element is: {}", first);
}

使用 for 循环遍历 Vector。

fn main() {
    let v = vec![100, 32, 57];
    for i in &v {
        println!("{}", i);
    }
}

使用可变引用修改 Vector 中的元素。

fn main() {
    let mut v = vec![100, 32, 57];
    for i in &mut v {
        *i += 50;
    }
}

8.2 Vector 的枚举

可以使用枚举来存储不同类型的值。

enum SpreadsheetCell {
    Int(i32),
    Float(f64),
    Text(String),
}

fn main() {
    let row = vec![
        SpreadsheetCell::Int(3),
        SpreadsheetCell::Text(String::from("blue")),
        SpreadsheetCell::Float(10.12),
    ];
}

8.3 String

Rust 开发者经常会被字符串所困扰：

• Rust 倾向于暴露可能的错误
• 字符串数据结构复杂
• 字符串使用 UTF-8 编码

字符串实际上是 Byte 的集合，提供了一些方法，并能将 Byte 集合转换为文本。

Rust 语言核心层面没有字符串类型，而是使用标准库提供的 String 类型。Rust 核心语言层面只有一种字符串类型，即字符串切片 str（或 &str）。

String 类型是标准库提供的，是一种可获得所有权的、可增长、可修改、堆分配的 UTF-8 编码的字符串类型。

• 许多 Vec<T> 的操作也适用于 String
• 可以使用 String::new() 创建空字符串
• 可以使用 to_string() 方法将字符串切片转换为 String
• 可以使用 String::from() 方法将字符串切片转换为 String

fn main() {
    let mut s = String::new();
    let data = "initial contents";
    let s = data.to_string();
    let s = String::from("initial contents");
}

使用 push_str() 方法追加字符串切片。

fn main() {
    let mut s = String::from("foo");
    s.push_str("bar");
}

使用 push() 方法追加字符。

fn main() {
    let mut s = String::from("lo");
    s.push('l');
}

使用运算符 + 可以拼接字符串，类似于 fn add(self, s: &str) -> String 方法。

fn main() {
    let s1 = String::from("Hello, ");
    let s2 = String::from("world!");
    let s3 = s1 + &s2;
}

• 标准库中的 add() 方法使用了泛型
• 只能将 &str 添加到 String 上
• Rust 使用了解引用强制转换（deref coercion）

Rust 会将 &String 转换为 &str，所以 &s2 会被转换为 &s2[..]。

使用 format! 宏拼接字符串，不会获取所有权。

fn main() {
    let s1 = String::from("tic");
    let s2 = String::from("tac");
    let s3 = String::from("toe");
    let s = format!("{}-{}-{}", s1, s2, s3);
}

8.4 String 的访问

Rust 不支持使用索引访问 String 中的字符，因为字符串使用 UTF-8 编码，一个字符可能占用多个字节。

fn main() {
    let s1 = String::from("hello");
    // let h = s1[0]; // error: the type `String` cannot be indexed by `{integer}`
}

Rust 字符串的内部表示是 Vec<u8>，一个 UTF-8 编码的字节序列。对于 ASCII 字符，每个字符占用 1 个字节，但对于其他字符，可能占用 2 个或更多字节。

例如，对于字符串 "Здравствуйте"（俄语的"你好"），它占用 24 个字节，而不是 12 个字符。

从 Rust 的角度看，字符串有三种表示方式：

• 字节（Bytes）：实际存储的字节序列
• 标量值（Scalar Values）：Unicode 标量值，即 char 类型
• 字形簇（Grapheme Clusters）：最接近人类理解的字符概念

例如，印地语单词 "नमस्ते" 的三种表示方式：

• 字节：[224, 164, 168, 224, 164, 174, 224, 164, 184, 224, 165, 141, 224, 164, 164, 224, 165, 135]
• 标量值：['न', 'म', 'स', '्', 'त', 'े']
• 字形簇：["न", "म", "स्", "ते"]

Rust 不允许使用索引访问字符串的另一个原因是索引操作应该是 $O(1)$ 的时间复杂度，但 UTF-8 编码的字符串无法保证这一点。

字符串切片

可以使用切片来访问字符串的一部分，但需要小心，因为切片必须在字符边界上。

fn main() {
    let hello = "Здравствуйте";
    let s = &hello[0..4]; // "Зд"
}

如果尝试在字符边界中间创建切片，程序会在运行时 panic。

fn main() {
    let hello = "Здравствуйте";
    let s = &hello[0..1]; // panic: byte index 1 is not a char boundary
}

遍历字符串

可以使用 .chars() 方法遍历字符串的字符。

fn main() {
    for c in "नमस्ते".chars() {
        println!("{}", c);
    }
}

输出：

न
म
स
्
त
े

可以使用 .bytes() 方法遍历字符串的字节。

fn main() {
    for b in "नमस्ते".bytes() {
        println!("{}", b);
    }
}

输出：

224
164
// ...省略其他字节

从标准库中获取字形簇比较复杂，可以使用第三方库如 unicode-segmentation。

8.5 HashMap

HashMap<K, V> 存储键值对，通过 Hash 函数决定如何存储。

• 键值对存储在堆上
• 同构的：所有的键必须是相同类型，所有的值也必须是相同类型

创建 HashMap

使用 HashMap::new() 创建空的 HashMap。

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();
    
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
}

另一种创建 HashMap 的方法是使用 collect() 方法。在元组的 Vector 上使用 collect() 方法可以创建 HashMap。

use std::collections::HashMap;

fn main() {
    let teams = vec![String::from("Blue"), String::from("Yellow")];
    let initial_scores = vec![10, 50];
    
    let scores: HashMap<_, _> = teams.iter().zip(initial_scores.iter()).collect();
}

zip() 方法可以创建一个元组的迭代器，collect() 方法可以将迭代器转换为 HashMap。这里使用类型注解 HashMap<_, _> 是因为 collect() 可以返回多种类型的集合，所以需要指定类型。但键和值的具体类型可以由 Rust 推断。

HashMap 和所有权

对于实现了 Copy trait 的类型（如 i32），值会被复制到 HashMap 中。对于拥有所有权的值（如 String），值会被移动，HashMap 会成为这些值的所有者。

use std::collections::HashMap;

fn main() {
    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 从这一刻开始失效
    // println!("{}", field_name); // error: value borrowed here after move
}

如果将值的引用插入 HashMap，值本身不会被移动到 HashMap 中。但这些引用指向的值必须在 HashMap 有效期间保持有效。

访问 HashMap 中的值

使用 get() 方法访问 HashMap 中的值。

use std::collections::HashMap;

fn main() {
    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);
    
    match score {
        Some(s) => println!("score: {}", s),
        None => println!("team not exist"),
    }
}

get() 方法返回 Option<&V>，如果键不存在则返回 None。

可以使用 for 循环遍历 HashMap。

use std::collections::HashMap;

fn main() {
    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);
    }
}

更新 HashMap

覆盖值

如果插入相同的键，新值会覆盖旧值。

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();
    
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Blue"), 25);
    
    println!("{:?}", scores); // {"Blue": 25}
}

只在键不存在时插入

使用 entry() 方法检查键是否存在。entry() 方法返回一个 Entry 枚举，代表可能存在也可能不存在的值。

use std::collections::HashMap;

fn main() {
    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); // {"Blue": 10, "Yellow": 50}
}

or_insert() 方法在键对应的值存在时就返回这个值的可变引用，如果不存在则将参数作为新值插入并返回新值的可变引用。

基于旧值更新值

use std::collections::HashMap;

fn main() {
    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); // {"hello": 1, "world": 2, "wonderful": 1}
}

or_insert() 方法返回值的可变引用 &mut V，我们需要使用 * 解引用才能修改值。

Hash 函数

默认情况下，HashMap 使用一种称为 SipHash 的哈希函数，它可以提供防御 HashDoS 攻击的能力。这不是最快的哈希算法，但为了安全性值得付出性能代价。

如果需要更快的哈希函数，可以指定不同的 hasher。Hasher 是实现了 BuildHasher trait 的类型。可以在 crates.io 上查找社区提供的 hasher。

8.6 总结

Vector、String 和 HashMap 是 Rust 标准库中最常用的集合类型。它们可以帮助我们存储、访问和修改数据。

• Vector 用于存储一系列相同类型的值
• String 是 UTF-8 编码的字符序列
• HashMap 用于存储键值对

标准库还提供了其他有用的集合类型，如 VecDeque、LinkedList、BTreeMap、BTreeSet、HashSet 等。更多信息可以查看标准库文档。

掌握这些集合类型的使用方法对于编写 Rust 程序非常重要。在实际开发中，根据具体需求选择合适的集合类型可以提高程序的性能和可读性。