跳转至

常用集合:vector、String 与 hash map

这一章讲什么: 三种几乎每个程序都用的堆上数据结构——vector(一串同类型的值, 长度可变)、String(可增长的文本)、hash map(键找值)。 它们的共同点是:数据在堆上、编译期不知道多大、所有权规则和它们缠绕在一起。 本章的一半知识点是 API,另一半是三个"为什么"——为什么借用着 vector 元素时不能追加, 为什么字符串不能用下标,为什么默认哈希算法不是最快的。

1. 顶层全景:三个集合,三类问题

  Vec<T>      一列同类型的值,挨着放,可增长      → 问题:增长可能"搬家",旧引用变悬垂
  String      一列字节 + "按 UTF-8 解释"的保证    → 问题:"第 N 个字符"没有唯一答案
  HashMap<K,V> 键到值的映射                      → 问题:键的类型、所有权、重复键怎么办

  图说:左边是"存什么",右边是各自撞上所有权/编码规则的那个点。

2. vector:会搬家的列表

创建:空 vector Vec::new()(需要类型标注);带初始值用 vec! 宏,let v = vec![1, 2, 3]; 类型自动推断成 Vec<i32>1。追加:v.push(5)(v 得是可变的)。

读元素有两条路,故意让你选崩溃还是处理:

let v = vec![1, 2, 3, 4, 5];

let third: &i32 = &v[2];                    // ① 下标法:越界直接 panic
let third: Option<&i32> = v.get(2);         // ② get 法:越界返回 None

&v[100] 对五元素 vector 会 panic——当你认定"越界就是 bug、就该崩"时用 []; v.get(100) 返回 None——当越界是正常可能(比如用户输的数)时用 get,配 match 优雅处理2。

本章第一个"为什么":为什么拿着元素的引用时不能 push。

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

这看起来不可理喻——往末尾加一个元素,关第一个元素什么事?机制:vector 把元素在内存里挨着放;末尾追加时若原地空间不够,要申请一块新内存、把旧元素全部拷过去。此时 first 指向的旧内存已经释放——借用规则把程序挡在了"引用变悬垂"之前3。

遍历:for i in &v(不可变引用)或 for i in &mut v 后 *i += 50(可变引用,* 是解引用符)。循环体里不能增删元素——循环持有的引用禁止同时修改整个 vector4。

想在 vector 里存多种类型?用枚举。 电子表格一行有整数、浮点、文本:enum SpreadsheetCell { Int(i32), Float(f64), Text(String) },所有变体同属一个类型,正好喂给 Vec<SpreadsheetCell>;配合 match,编译器保证每种情况都被处理。前提:可能的类型集合编译期可知;运行时才知道的类型组合,答案是第 18 章的 trait 对象5。

离开作用域时,vector 和它的元素一起被 drop;借用检查器保证指向内容的引用只在 vector 活着时用6。

3. String:比"一串字符"复杂得多的东西

先分清两个名字。 Rust 核心语言只有一个字符串类型:字符串切片 str(通常以借用形式 &str 出现,字面量就是它)。标准库的 String 是"可增长、可变、拥有所有权、UTF-8 编码"的字符串类型,本质是"包了一层字节 vector 再加保证"。日常说"字符串"可能指两者,都是 UTF-87。

创建与更新:String::new();"lit".to_string() 或 String::from("lit")(一回事,风格任选)8。追加:push_str(&str)(参数是切片,不夺走所有权——追加完还能用原来的变量)、push('c')(单个字符)。拼接:

let s1 = String::from("Hello, ");
let s2 = String::from("world!");
let s3 = s1 + &s2;    // 注意:s1 被 move 了,之后不能用

+ 背后是一个 add(self, s: &str) -> String 方法:接收者是 self(没有 &,所以夺走 s1),参数是字符串切片(&String 能传进来靠 deref coercion 转成 &str,第 15 章)。所以它看起来复制了两个字符串,实际只复制了 s2 的内容追加到 s1 的缓冲上,比想象中省9。多个字符串拼接别用一连串 +,用 format!("{s1}-{s2}-{s3}")——不夺走任何参数的所有权,可读性完胜10。

3.1 本章第二个"为什么":String 为什么不能 s[0]

let h = s1[0]; 编译错:str cannot be indexed by {integer}。为什么?书里给了一个会让你记一辈子的例子:

String::from("Hola") 的 len 是 4(4 个字母各 1 字节);String::from("Здравствуйте") 你以为是 12,实际 len 是 24——UTF-8 里这个字符串的每个字符占 2 字节11。

于是 &hello[0] 能返回什么?若按字节返回 208(З 的第一个字节),那不是任何有效字符;若按字符返回 З,那下标访问就没法保证 O(1)——Rust 无法保证"索引 = 常数时间"这个约定,因为从开头走到第 N 个字符必须先逐个字节解码。与其返回一个你意想不到的值、埋一颗迟爆的雷,Rust 选择不让这段代码编译12。

三种"字符"观:同一段印地语 "नमस्ते"——按字节看是 18 个 u8;按 Unicode 标量值看是 6 个 char(其中两个是单独的附加符号,单独无意义);按字素簇(grapheme cluster,最接近人说的"字母")看是 4 个。Rust 让你显式选解释方式:s.chars() 迭代 char、s.bytes() 迭代字节;字素簇标准库不提供,要去 crates.io13。

真要用范围下标,可以用切片语法,但切的是字节且必须在字符边界上:&"Здравствуйте"[0..4] 得到 "Зд";[0..1] 会 panic("not a char boundary")14。

书给这一节的定性很诚实:字符串是复杂的,不同语言只是把这复杂度藏得深浅不同;Rust 选择把 UTF-8 的正确处理变成默认行为, upfront 多费神,换后期不踩非 ASCII 的雷15。

4. hash map:键找值

HashMap<K, V> 用哈希函数决定键值对在内存里的位置。 别的语言叫它 hash / dictionary / map / associative array。它在三个集合里使用频率最低,不在 prelude 里,要用 use std::collections::HashMap; 显式引进,也没有 vec! 那样的构造宏16。

基本操作:新建 HashMap::new()、插入 map.insert(k, v)(同键重复插入 = 覆盖旧值)、读取 map.get(&k)(返回 Option<&V>——查不到是 None 而不是 panic,这和 vector 的 get 一脉相承)。惯用读法:scores.get(&team_name).copied().unwrap_or(0)——copied 把 Option<&i32> 变 Option<i32>,unwrap_or 给查不到时的默认值17。

所有权:Copy 类型(i32)的值拷进 map;String 这类 owned 值被 move 进去,insert 之后原变量失效。想存引用也行,但被引用物至少得和 map 一样长寿(生命周期,第 10 章)18。

重复键的三种策略(改数据前必须先决定)19:

策略 API 行为
覆盖旧的 直接再 insert 旧值被丢弃
只在不存在时插入 map.entry(k).or_insert(v) 已存在则原样保留
基于旧值更新 let c = map.entry(k).or_insert(0); *c += 1; 拿到 &mut V,解引用后改

entry 返回一个叫 Entry 的枚举,表示"这个键可能有值也可能没有";or_insert 在它上面:有值返回值的 &mut V,没有就插入参数再返回其 &mut V。主线例子是词频统计:

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;
}
// {"world": 2, "hello": 1, "wonderful": 1}(顺序任意)

每轮循环 count 是对该键值的 &mut V;循环结束引用离开作用域,借用规则放行20。

本章第三个"为什么":默认哈希是 SipHash——不是最快的,但能抵抗针对哈希表的 DoS 攻击;安全换性能的账默认是划算的。profiling 发现它是瓶颈时,可以换实现 BuildHasher trait 的 hasher,crates.io 上有现成的21。

5. 作者的判断与证据

  • "[] 越界 panic vs get 返回 None,是给你选择"——设计主张,两种行为并存的理由是场景不同2。
  • "String 不提供下标是为了防误解 + 保 O(1) 约定"——双重理由,都是机制论证12。
  • "SipHash 的取舍值得"——价值判断,理由给了(防 DoS),也给了退出 hatch(换 hasher)21。

判断(我们的,不是书里的): 这一章的三个"为什么"其实是同一个原则的三次应用: 当"直觉上该行"的代码背后藏着无法兑现的假设时,Rust 选择拒编,并把替代路径摆出来。 push 撞搬家、下标撞 UTF-8、哈希撞安全——没有一个问题是"加个聪明实现"能糊过去的, 全是"语义本身有歧义/有代价",拒编是诚实的答案。 如果错,会错在: 诚实有学费——新手会在 vector 借用和字符串下标这两处反复撞墙, 书里也承认"新 Rustacean 常在字符串上卡住"7;若语言选择了"先让你跑、错了再炸", 入门曲线更平,但那一类 bug 就归了用户。

6. 边界与局限

  • vector 的容量/增长策略只有一句"可能搬家",实现细节指给 Rustonomicon。
  • String 的方法库(contains、replace 等)只点了名,让读者查文档。
  • 字素簇明确说"标准库不提供"。
  • 三个集合的练习(中位数/众数、Pig Latin、部门花名册)是本章的隐性作业,拆解不复述。

7. 可带走的

  1. vec! 带初始值;Vec::new() 空表要标注类型;push 要 mut。
  2. &v[i] 越界 panic(认定是 bug 时用);v.get(i) 越界 None(可能正常发生时用)。
  3. 持有元素引用时不能 push——扩容搬家会使旧引用悬垂。
  4. for i in &v / for i in &mut v + *i;循环里不能增删。
  5. 同 vector 存多类型:枚举;类型集合运行时才知道:trait 对象(第 18 章)。
  6. &str 是切片,String 是拥有的、可增长的;push_str 不夺走参数。
  7. s1 + &s2 会 move s1;多段拼接用 format!。
  8. String 无下标:UTF-8 下"第 N 个"不唯一且难保 O(1);要字符用 .chars(),要字节用 .bytes(),范围切片必须在字符边界上。
  9. HashMap 不在 prelude;insert 会 move String 键值;get 返回 Option。
  10. entry(k).or_insert(v) 一行搞定"没有才插";词频统计是它的教科书用法。
  11. 默认哈希 SipHash:抗 DoS,慢可换。

8. 原文地图

主题 原书章 原文位置
vector 创建与 push Chapter 8: Common Collections text/15-ch08-chapter-8-common-collections.txt:34(搜「Vec::new」) · text/15-ch08-chapter-8-common-collections.txt:63(搜「Updating a Vector」)
两种读法与越界行为 同上 text/15-ch08-chapter-8-common-collections.txt:120(搜「cause the program to」) · text/15-ch08-chapter-8-common-collections.txt:125(搜「returns None」)
push 撞借用(E0502) 同上 text/15-ch08-chapter-8-common-collections.txt:155(搜「cannot borrow」) · text/15-ch08-chapter-8-common-collections.txt:171(搜「allocating new memory」)
枚举存多类型 同上 text/15-ch08-chapter-8-common-collections.txt:215(搜「Using an Enum」)
String 与 &str 同上 text/15-ch08-chapter-8-common-collections.txt:292(搜「only one string」)
+ 与 add 签名 同上 text/15-ch08-chapter-8-common-collections.txt:407(搜「moved here」) · text/15-ch08-chapter-8-common-collections.txt:416(搜「fn add」)
format! 同上 text/15-ch08-chapter-8-common-collections.txt:457(搜「format!」)
Hola/Здравствуйте 例子 同上 text/15-ch08-chapter-8-common-collections.txt:499(搜「Здравствуйте」)
三种字符观 同上 text/15-ch08-chapter-8-common-collections.txt:524(搜「Grapheme Clusters」)
字符串切片边界 同上 text/15-ch08-chapter-8-common-collections.txt:565(搜「first 4 bytes」)
HashMap 基础 同上 text/15-ch08-chapter-8-common-collections.txt:625(搜「hash map」)
entry/or_insert 同上 text/15-ch08-chapter-8-common-collections.txt:779(搜「or_insert」)
词频统计 同上 text/15-ch08-chapter-8-common-collections.txt:811(搜「split_whitespace」)
SipHash 同上 text/15-ch08-chapter-8-common-collections.txt:833(搜「SipHash」)

  1. 出处:「Chapter 8: Common Collections」第 56 段(text/15-ch08-chapter-8-common-collections.txt:56,搜「vec!」)。 ↩

  2. 出处:「Chapter 8: Common Collections」第 120 段(text/15-ch08-chapter-8-common-collections.txt:120,搜「cause the program to」)与第 125 段(text/15-ch08-chapter-8-common-collections.txt:125,搜「returns None」)。 ↩↩

  3. 出处:「Chapter 8: Common Collections」第 171 段(text/15-ch08-chapter-8-common-collections.txt:171,搜「allocating new memory」)。 ↩

  4. 出处:「Chapter 8: Common Collections」第 209 段(text/15-ch08-chapter-8-common-collections.txt:209,搜「borrow checker」)。 ↩

  5. 出处:「Chapter 8: Common Collections」第 215 段(text/15-ch08-chapter-8-common-collections.txt:215,搜「Using an Enum」)与第 250 段(text/15-ch08-chapter-8-common-collections.txt:250,搜「don’t know the exhaustive set」)。 ↩

  6. 出处:「Chapter 8: Common Collections」第 270 段(text/15-ch08-chapter-8-common-collections.txt:270,搜「all of its contents are also dropped」)。 ↩

  7. 出处:「Chapter 8: Common Collections」第 292 段(text/15-ch08-chapter-8-common-collections.txt:292,搜「only one string」)与第 278 段(text/15-ch08-chapter-8-common-collections.txt:278,搜「get stuck on strings」)。 ↩↩

  8. 出处:「Chapter 8: Common Collections」第 324 段(text/15-ch08-chapter-8-common-collections.txt:324,搜「to_string」)。 ↩

  9. 出处:「Chapter 8: Common Collections」第 416 段(text/15-ch08-chapter-8-common-collections.txt:416,搜「fn add」)与第 433 段(text/15-ch08-chapter-8-common-collections.txt:433,搜「takes ownership of self」)。 ↩

  10. 出处:「Chapter 8: Common Collections」第 457 段(text/15-ch08-chapter-8-common-collections.txt:457,搜「format!」)。 ↩

  11. 出处:「Chapter 8: Common Collections」第 499 段(text/15-ch08-chapter-8-common-collections.txt:499,搜「Здравствуйте」)。 ↩

  12. 出处:「Chapter 8: Common Collections」第 521 段(text/15-ch08-chapter-8-common-collections.txt:521,搜「this code at all」)与第 549 段(text/15-ch08-chapter-8-common-collections.txt:549,搜「constant time」)。 ↩↩

  13. 出处:「Chapter 8: Common Collections」第 524 段(text/15-ch08-chapter-8-common-collections.txt:524,搜「Grapheme Clusters」)。 ↩

  14. 出处:「Chapter 8: Common Collections」第 565 段(text/15-ch08-chapter-8-common-collections.txt:565,搜「first 4 bytes」)。 ↩

  15. 出处:「Chapter 8: Common Collections」第 611 段(text/15-ch08-chapter-8-common-collections.txt:611,搜「correct handling of String data」)。 ↩

  16. 出处:「Chapter 8: Common Collections」第 657 段(text/15-ch08-chapter-8-common-collections.txt:657,搜「often used」)。 ↩

  17. 出处:「Chapter 8: Common Collections」第 683 段(text/15-ch08-chapter-8-common-collections.txt:683,搜「unwrap_or」)。 ↩

  18. 出处:「Chapter 8: Common Collections」第 706 段(text/15-ch08-chapter-8-common-collections.txt:706,搜「moved」)。 ↩

  19. 出处:「Chapter 8: Common Collections」第 735 段(text/15-ch08-chapter-8-common-collections.txt:735,搜「how to handle」)。 ↩

  20. 出处:「Chapter 8: Common Collections」第 811 段(text/15-ch08-chapter-8-common-collections.txt:811,搜「split_whitespace」)。 ↩

  21. 出处:「Chapter 8: Common Collections」第 833 段(text/15-ch08-chapter-8-common-collections.txt:833,搜「SipHash」)。 ↩↩