装东西的容器：集合

原理

Vec<T> 在栈上保存三元组（ptr, len, cap, 共 24 字节），堆上存实际数据。扩容策略为 2x 增长（push 时若 len==cap 则 realloc 到 2*cap）。重新分配时通过 ptr::copy_nonoverlapping 迁移旧数据，类似 C 的 realloc。

String 实质是 Vec<u8>，保证了内容为有效 UTF-8 字节序列。len() 返回字节数，非字符数（一个中文字符占 3 字节）。s[i] 不可用于索引，因为 UTF-8 非定长编码，单字节索引可能切到字符中间 → 编译期拒绝。

HashMap<K,V> 使用 Swiss table（hashbrown crate）实现，提供 O(1) 平均查找。Hash 碰撞通过开放式寻址（open addressing）+ SIMD 探测解决。无序性意味着遍历顺序随插入和 resize 改变。

三者使用堆存储，所以非 Copy。遍历时 for x in vec 消耗所有权，for x in &vec 仅借用。

C: 动态数组

语法

Vec

let mut v: Vec<i32> = Vec::new();
v.push(1);
v.push(2);
 
let v2 = vec![1, 2, 3, 4, 5];   // vec! 宏
 
v[2];           // 索引访问（越界 panic）
v.get(2);       // 返回 Option<&i32>
 
for n in &v { }             // 不可变遍历
for n in &mut v { *n += 1; } // 可变遍历
for (i, n) in v.iter().enumerate() { }
 
v.pop();        // 移除末尾，返回 Option<T>
v.insert(0, 9); // 指定位置插入
v.remove(0);    // 指定位置移除
v.len();
v.is_empty();

方法	效果	复杂度
`push`	末尾插入	O(1) 均摊
`pop`	末尾删除	O(1)
`insert`	指定位置插入	O(n)
`remove`	指定位置删除	O(n)

String

let mut s = String::from("你好");
s.push_str("世界");
s.push('!');
let s = s + "结尾";     // s 被移动
 
let a = String::from("A");
let b = String::from("B");
let c = format!("{} {}", a, b);  // 不移动所有权
 
s.len();        // UTF-8 字节数（中文*3）
&s[0..6];       // 切片（注意 UTF-8 边界）
 
// s[0];        // 错误：String 不支持直接整数索引
s.chars().nth(0); // 按 char 遍历

HashMap

use std::collections::HashMap;
 
let mut map = HashMap::new();
map.insert("a", 1);
map.insert("b", 2);
 
let val = map.get("a");            // Option<&V>
let val = map["a"];                // 不存在时 panic
 
for (k, v) in &map { }             // 无序
 
// 仅不存在时插入
map.entry("c").or_insert(3);       // 返回 &mut V
 
// 统计词频
let count = map.entry(word).or_insert(0);
*count += 1;

集合对比

	Vec	String	HashMap<K,V>
存储	同类型序列	UTF-8 文本	键→值映射
访问	索引 O(1)	按字节切片	键查找 O(1) 平均
顺序	插入顺序	插入顺序	无序
存储	堆	堆	堆

实践

力扣问题

力扣: 力扣质数筛选题 — Vec 操作

let mut primes: Vec<i32> = Vec::new();
for n in numbers {
    if is_prime(n) { primes.push(n); }
}

力扣: 力扣哈希映射题 — HashMap 映射

AI 自检

Vec 扩容为何是 2x 而非 1x？从 amortized O(1) 角度解释。
HashMap 的 entry API 如何避免重复哈希查找？

RootStack

探索

09-装东西的容器：集合