集合类型

这一课你将能做到

1. 熟练操作 Vec、String、HashMap 三大集合，理解「所有权跟着集合走」
2. 区分 iter / iter_mut / into_iter 三种遍历，知道集合遍历时为什么不能顺手修改
3. 用迭代器适配器链（map/filter/collect）写出零开销的数据管道

为什么要学

Java 工程师每天离不开 ArrayList、HashMap、Stream——Rust 对应的是 Vec、HashMap 和迭代器。区别在于：Java 的 Stream 是运行时构建的惰性流水线，Rust 的迭代器链编译期直接展开成手写循环级别的机器码（零成本抽象的招牌案例）。

判题系统里到处是集合操作：提交队列（Vec）、判题结果缓存（HashMap）、拼接评测输出（String）。这一课的场景全部围绕它们展开。

先建立图像

Java                        Rust
ArrayList<T>          ↔     Vec<T>            堆上连续内存，随机访问 O(1)
HashMap<K,V>          ↔     HashMap<K,V>      哈希表（Rust 默认 SipHash，防 HashDoS）
String / StringBuilder ↔    String            UTF-8 堆上可增长
Stream<T>             ↔     Iterator trait    惰性管道，但编译期单态化

三个集合全部把数据存在堆上、变量持有所有权——所有权规则在这里全面生效：move 集合就是把整块堆数据易主，遍历借用要 &。

跟着做

步骤 1：Vec——最常用的动态数组

cargo new coll-demo
cd coll-demo

fn main() {
    let mut queue: Vec<String> = Vec::new();     // 或 vec!["s1".into(), "s2".into()]
    queue.push("submit-1".to_string());          // 尾部入队
    queue.push("submit-2".to_string());
    queue.push("submit-3".to_string());

    let first = queue.remove(0);                 // 取出并移除下标 0（所有权转移出来）
    println!("处理 {first}，队列剩余 {:?}", queue);

    let peek = &queue[0];                        // 借用访问：越界直接 panic
    let safe = queue.get(99);                    // Option 访问：越界返回 None
    println!("队首 {peek}，越界查询 {:?}", safe);
}

背下这组对照：v[i] 索引访问（越界 panic，对标 Java ArrayIndexOutOfBounds）、v.get(i) 安全访问（Option）、v.remove(i) 取走元素（所有权移出）。

步骤 2：三种遍历——所有权决定写法

fn main() {
    let mut times = vec![120u32, 990, 1500, 80];

    for t in &times {                  // iter()：不可变借用，集合还在
        println!("{t}");
    }
    for t in &mut times {              // iter_mut()：可变借用，能改元素
        *t = t.saturating_sub(100);
    }
    let owned: Vec<u32> = times.clone().into_iter().filter(|&t| t > 0).collect();
    println!("{:?} / {:?}", times, owned);
}

&times 借用读、&mut times 借用写、into_iter() 拿走集合所有权逐个交出元素。想在遍历中删元素？编译器直接拒绝（迭代器持有借用）——Java 的 ConcurrentModificationException 变成编译错误。

步骤 3：String——UTF-8 与所有权

fn main() {
    let mut log = String::from("判题开始");
    log.push_str(" | 用例1 通过");       // 追加：可变借用自身，无 StringBuilder 之分
    let full = format!("{log} | 总耗时 {} ms", 128);   // 拼接首选 format!，不夺走 log 所有权

    // 注意：String 是 UTF-8 字节序列，中文一个字符占 3 字节
    let chars: Vec<char> = "评测AB".chars().collect();       // 按字符遍历
    let bytes = "评测AB".len();                               // 按字节计数
    println!("{full}");
    println!("字符数 {}，字节数 {}", chars.len(), bytes);
    // "评测AB"[0] 不存在！String 不支持按下标取字符，避免切进 UTF-8 中间
}

&str 与 String 的配合在上一课已讲：参数收 &str，存储用 String。这里补一刀：字符串切片 &s[0..6] 按字节切，切在多字节字符中间会 panic——中文场景一律用 char_indices() 定位。

步骤 4：HashMap——判题结果缓存

use std::collections::HashMap;

fn main() {
    let mut scores: HashMap<String, u32> = HashMap::new();
    scores.insert("alice".to_string(), 90);           // 相同 key 覆盖旧值
    scores.insert("bob".to_string(), 75);

    let s = scores.get("alice");                      // Option<&u32>
    println!("alice: {:?}", s);

    // entry：不存在则插入默认值——词频统计的标准姿势
    let text = "rust fast rust safe rust";
    let mut freq: HashMap<&str, u32> = HashMap::new();
    for word in text.split_whitespace() {
        *freq.entry(word).or_insert(0) += 1;
    }

    let mut pairs: Vec<_> = freq.iter().collect();
    pairs.sort_by_key(|(_, n)| std::cmp::Reverse(**n));   // 按次数降序
    for (word, n) in &pairs {
        println!("{word} x{n}");
    }
}

entry().or_insert() 是 HashMap 最有价值的 API：一次哈希定位完成「查、缺省、改」三步，Java 要 getIfPresent + put 两轮哈希。BTreeMap（有序版）在需要按 key 排序遍历时替换使用。

步骤 5：迭代器链——Stream 的零成本版本

fn main() {
    let times = vec![120u32, 990, 1500, 80, 2000];

    let fast: Vec<u32> = times.iter().copied().filter(|&t| t < 1000).collect();
    let total: u32 = times.iter().sum();
    let best = times.iter().min();
    let labels: Vec<String> = times.iter().map(|t| format!("{t}ms")).collect();

    println!("快速通过 {fast:?}");
    println!("总耗时 {total} ms，最快 {:?}", best);
    println!("标签 {labels:?}");
}

链式调用：map 变形、filter 过滤、sum/min/max 聚合、collect 收集。惰性且无中间集合——编译器把整条链展开为一个循环，对标 Java Stream 但省掉全部流水线对象。

讲清楚要点

1. Vec 是 Rust 的默认集合：连续内存、缓存友好、随机访问 O(1)；尾部 push/pop 均摊 O(1)。对标 ArrayList 但无扩容的隐式装箱。
2. HashMap 遍历顺序不稳定：默认 SipHash 随机种子防 HashDoS 攻击，两次运行顺序都不同。需要顺序用 BTreeMap，需要自定义哈希用 with_hasher。
3. String 的三个铁律：UTF-8 编码、按下标 O(1) 拿到的不是字符是字节、不支持 [i] 取字符。字符操作走 chars()。
4. 迭代器是惰性的：不调用 collect / sum / for 这类消费者，适配器一行代码都不执行。
5. collect 的类型由变量标注决定：collect::<Vec<_>>()、collect::<HashMap<_, _>>()——同一迭代器能收集成任何实现了 FromIterator 的容器。

你可能会懵的地方

• Vec 越界为什么直接 panic 而不像 Java 抛异常让我 catch？ Rust 认为越界是程序 bug，不该被捕获后继续跑；安全访问用 get 拿 Option 自行处理。设计哲学：bug 快速失败，业务失败走类型。

• HashMap 默认哈希慢吗？ SipHash 抗碰撞攻击但比 xxhash 慢。key 是整数且吞吐敏感时换 std::collections::hash_map::DefaultHasher 之外的 hasher（如 fxhash）。默认选择是安全优先，可替换是性能自由。

• &Vec<T> 参数和 &[T] 参数哪个好？ &[T]（切片）更好：它同时接受 Vec、数组、切片，且少一层间接。原则和字符串一样——参数收宽类型（&str/&[T]），存储用拥有类型（String/Vec）。

• 迭代器链和 for 循环性能谁高？ 通常一样甚至链更快：适配器在编译期内联融合，没有边界检查的重复与中间分配。这是「零成本抽象」最经典的实证。

• remove(0) 慢吗？ O(n)（后面全部前移）。做队列用 VecDeque（双端 O(1)），做栈用 Vec 的 pop——先想访问模式再选容器。

错法对照

错法	问题	正解
v[5] 访问不确定的下标	越界 panic	v.get(5) 处理 Option
遍历时 v.remove(i)	error[E0502] 借用冲突	retain/drain 批量删，或先收集再删
s[0] 取字符串首字符	String 不支持下标	s.chars().next()
HashMap 取值直接当值用	get 返回 Option	if let Some(v) = map.get(k)
中文字符串按字节 &s[..3] 硬切	切进 UTF-8 中间 panic	用 char_indices() 或按 chars() 处理

卡点急救

1. error[E0502] cannot borrow ... as mutable because it is also borrowed as immutable：遍历中修改集合的典型报错。改用 retain（条件删除）、iter_mut（原地改值），或 split 收集索引后处理。
2. type annotations needed（collect 后类型推不出）：给接收变量加标注：let v: Vec<u32> = ...collect(); 或 turbofish collect::<Vec<u32>>()。
3. panic: called Option::unwrap() on a None：定位到 unwrap 处，换成 unwrap_or/?/if let；热路径先想清楚 None 是「正常分支」还是「bug」。

面试常问

• Rust HashMap 和 Java HashMap 的实现差异？ Rust 默认 SipHash（抗 HashDoS，随机种子、顺序不稳定），开放寻址；Java HashMap 链地址法 + 树化。Rust 可一键换 hasher（fxhash/ahash）做吞吐优化，默认策略是安全优先。

• 为什么说 Rust 迭代器是零成本抽象？ 适配器全部编译期单态化并内联融合成单个循环，无装箱、无接口虚调用、无中间集合；基准上与手写循环一致甚至更优（省去重复边界检查），对比 Java Stream 的流水线对象与 lambda 元数据开销。

• Vec、VecDeque、BTreeMap 怎么选？ 随机访问+尾部增删选 Vec；两端进出（任务队列）选 VecDeque；需要按 key 有序遍历/范围查询选 BTreeMap。先定访问模式，再定容器。

自测三问

1. &times、&mut times、times（into_iter）三种 for 遍历各发生什么？
2. entry(word).or_insert(0) 一行做了 Java 里的哪几步？
3. 为什么函数参数建议收 &[T] 而不是 &Vec<T>？

小结一句话

Vec/String/HashMap 加迭代器链覆盖 90% 数据处理需求；所有权让「边遍历边改」成为编译错误，零成本抽象让链式写法不再是性能妥协。

延伸

• The Rust Book ch08：常见集合
• 下一课：并发与 async——线程、通道、Mutex 与 tokio，判题并发的两套武器。