跳到主要内容

常用集合

问题​

Rust 标准库提供了哪些常用集合？它们的特点和使用场景是什么？

答案​

Rust 标准库提供的集合类型都在堆上分配内存，大小可在运行时增长。

Vec — 动态数组​

Vec<T> 是最常用的集合，在堆上分配连续内存：

fn main() {
    // 创建
    let mut v: Vec<i32> = Vec::new();
    let v2 = vec![1, 2, 3];                 // vec! 宏
    let v3 = Vec::with_capacity(100);       // 预分配容量
    let v4: Vec<i32> = (0..10).collect();   // 从迭代器收集

    // 增删
    v.push(1);
    v.push(2);
    v.push(3);
    let last = v.pop();           // Some(3)
    v.insert(0, 0);              // 在索引 0 插入
    v.remove(0);                  // 移除索引 0

    // 访问
    let first = v[0];            // 索引访问（越界 panic）
    let first = v.get(0);        // Option<&i32>（越界返回 None）
    let slice = &v[1..3];        // 切片

    // 遍历
    for item in &v { /* 不可变引用遍历 */ }
    for item in &mut v { *item *= 2; }  // 可变引用遍历
    for item in v { /* 消耗 v，获取所有权 */ }
}
Vec 的内存布局

Vec<T> 由三个字段组成：{ ptr: *mut T, len: usize, cap: usize }

栈上: [ptr | len: 3 | cap: 8]
         ↓
堆上: [1 | 2 | 3 | _ | _ | _ | _ | _]
                     ~~~~~~~ 未使用容量

扩容策略：当 len == cap 时，容量翻倍（实际是乘以约 2 的系数），分配新内存并搬移数据。所以预分配（with_capacity）可以避免频繁重分配。

HashMap — 哈希表​

use std::collections::HashMap;

fn main() {
    // 创建
    let mut scores: HashMap<String, i32> = HashMap::new();
    let scores2: HashMap<_, _> = vec![("Alice", 90), ("Bob", 85)].into_iter().collect();

    // 插入
    scores.insert(String::from("Alice"), 90);
    scores.insert(String::from("Bob"), 85);

    // 访问
    let score = scores.get("Alice");          // Option<&i32>
    let score = scores["Alice"];               // 直接索引（不存在则 panic）

    // Entry API（不存在才插入）
    scores.entry(String::from("Charlie")).or_insert(0);
    // 存在则修改
    scores.entry(String::from("Alice")).and_modify(|s| *s += 10);
    // 不存在则用函数计算默认值
    scores.entry(String::from("Dave")).or_insert_with(|| expensive_default());

    // 遍历
    for (name, score) in &scores {
        println!("{}: {}", name, score);
    }

    // 删除
    scores.remove("Bob");
}
Entry API

Entry API 是 Rust HashMap 的精华——一次查找完成"检查 + 插入/修改"，避免重复哈希计算：

// 经典场景：计数
let mut word_count = HashMap::new();
for word in text.split_whitespace() {
    let count = word_count.entry(word).or_insert(0);
    *count += 1;
}

HashSet — 哈希集合​

HashSet<T> 本质是 HashMap<T, ()>，只存储键：

use std::collections::HashSet;

fn main() {
    let mut set = HashSet::new();
    set.insert(1);
    set.insert(2);
    set.insert(3);
    set.insert(2); // 重复，不会插入

    // 查询
    assert!(set.contains(&2));
    assert_eq!(set.len(), 3);

    // 集合运算
    let a: HashSet<_> = [1, 2, 3].into();
    let b: HashSet<_> = [2, 3, 4].into();

    let union: HashSet<_> = a.union(&b).collect();         // {1, 2, 3, 4}
    let intersection: HashSet<_> = a.intersection(&b).collect(); // {2, 3}
    let difference: HashSet<_> = a.difference(&b).collect(); // {1}
    let symmetric: HashSet<_> = a.symmetric_difference(&b).collect(); // {1, 4}
}

BTreeMap / BTreeSet — 有序集合​

基于 B-Tree 实现，元素按键排序：

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert(3, "three");
    map.insert(1, "one");
    map.insert(2, "two");

    // 遍历是有序的（按键排序）
    for (k, v) in &map {
        println!("{}: {}", k, v); // 1: one, 2: two, 3: three
    }

    // 范围查询
    for (k, v) in map.range(1..3) {
        println!("{}: {}", k, v); // 1: one, 2: two
    }
}

集合对比​

集合底层查找插入有序键要求
Vec<T>连续数组O(n)O(n)O(1)O(1) 末尾插入序无
HashMap<K,V>哈希表O(1)O(1) 均摊O(1)O(1) 均摊无序Eq + Hash
HashSet<T>哈希表O(1)O(1) 均摊O(1)O(1) 均摊无序Eq + Hash
BTreeMap<K,V>B-TreeO(log⁡n)O(\log n)O(log⁡n)O(\log n)键排序Ord
BTreeSet<T>B-TreeO(log⁡n)O(\log n)O(log⁡n)O(\log n)有序Ord
VecDeque<T>环形缓冲O(n)O(n)O(1)O(1) 两端插入序无
LinkedList<T>双向链表O(n)O(n)O(1)O(1) 两端插入序无
BinaryHeap<T>二叉堆O(1)O(1) 最大值O(log⁡n)O(\log n)部分有序Ord

常见面试问题​

Q1: Vec 的扩容机制是什么？对性能有什么影响？​

答案：

Vec 在 push 时如果 len == cap，会分配新内存（约 2 倍当前容量），将所有元素复制到新位置，释放旧内存。

性能影响：

  • 均摊 O(1)：虽然扩容是 O(n)，但扩容次数随 n 对数增长，均摊每次 push 仍是 O(1)
  • 预分配：如果已知大小，用 Vec::with_capacity(n) 一次分配足够空间
  • 引用失效：扩容后所有指向旧内存的引用都失效——这就是为什么借用检查器不允许在持有 &v[0] 时 v.push()

Q2: HashMap 和 BTreeMap 怎么选？​

答案：

场景选择原因
不需要排序，频繁查找HashMapO(1) 查找
需要按键排序遍历BTreeMap自动排序
需要范围查询BTreeMap支持 range()
键不能 HashBTreeMap只要求 Ord
确定性遍历顺序BTreeMapHashMap 遍历顺序不确定

Q3: 如何用 HashMap 做单词计数？​

答案：

use std::collections::HashMap;

fn word_count(text: &str) -> HashMap<&str, usize> {
    let mut counts = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    counts
}

entry().or_insert() 是 HashMap 的经典模式——一次哈希查找完成"不存在则插入默认值"的操作。

Q4: Vec 和 slice &[T] 是什么关系？​

答案：

  • Vec<T>：拥有数据所有权的动态数组（ptr + len + cap）
  • &[T]：切片引用，不拥有数据（ptr + len）

关系类似 String 和 &str：Vec 可以 Deref 为 &[T]。函数参数推荐接受 &[T] 而非 &Vec<T>，更通用。

fn sum(numbers: &[i32]) -> i32 {     // ✅ 接受 &[T]
    numbers.iter().sum()
}

let v = vec![1, 2, 3];
let arr = [4, 5, 6];
sum(&v);    // ✅ &Vec → &[T]
sum(&arr);  // ✅ &[T; N] → &[T]

Q5: 如何在 Vec 中存储不同类型的数据？​

答案：

// 方式 1：枚举（编译期类型安全)
enum Value {
    Int(i32),
    Float(f64),
    Text(String),
}
let values: Vec<Value> = vec![Value::Int(1), Value::Float(2.0)];

// 方式 2：Trait Object（动态分发）
let items: Vec<Box<dyn std::fmt::Display>> = vec![
    Box::new(42),
    Box::new("hello"),
    Box::new(3.14),
];

枚举方式性能更好（无间接寻址），Trait Object 更灵活（开放扩展）。

相关链接​