集合类型

Vec 是堆上的连续数组(随机访问 O(1)、尾部插入摊销 O(1)),HashMap 用 SwissTable 实现(缓存友好的开放寻址),BTreeMap 按键排序(Vec 的缓存局部性 vs BTreeMap 的有序遍历——两者不能兼得)。VecDeque 是环形缓冲区,两头推入都 O(1)。选型看访问模式:连续遍历 Vec,按键查询 HashMap,范围查询 BTreeMap。

Vec: 动态数组

let mut v = Vec::with_capacity(100);  // 预分配 — 避免 push 时的 realloc
v.push(42);

内部（栈上 24 bytes on 64-bit）: [ptr: 8B | len: 8B | cap: 8B]，ptr 指向堆上的 [T; cap] 数组。

增长策略：当 len == cap 时，新 capacity = max(old × 2, len + 1)。这是摊还 O(1) push 的经典策略。注意：realloc 可能将数据复制到新地址——所有指向旧 Vec 元素的引用会在 realloc 后变成悬垂。这就是为什么 borrow checker 禁止在持有一个元素的引用时 push。

HashMap: 默认 SipHash，可选 FxHash

use std::collections::HashMap;
let mut map = HashMap::new();
map.insert("key", 42);

std 的 HashMap 默认用 SipHash 1-3。为什么不是更快的 hash？SipHash 的设计目标是抗 HashDoS——攻击者构造大量产生相同 hash 的 key，使 HashMap 退化为 O(n) 查找，放大 CPU 资源消耗。SipHash 的 key 是随机的（每次进程启动生成），攻击者无法预知 hash 结果。

代价：SipHash 比 FxHash 慢 10-30%。如果你的输入可控（不对外部暴露 key），可以用 rustc_hash::FxHashMap（rustc 自己用的哈希表）——它是基于整数算术的快速 hash，但不抗 HashDoS。

BTreeMap: 有序集合

B-tree 结构：key 有序存储，每个节点有 B 个 key。查找/插入 O(log N)。相比 HashMap 的优势：

• Range scan: map.range("a".."z") 是 O(log N + K)，HashMap 做不到（unordered）
• 可预测性能⁠: 没有最坏情况的 O(N) 退化（HashMap 在碰撞时可能退化）
• 内存局部性⁠: B-tree 的节点是连续的（cache-friendly）

适用：需要有序遍历、按 key 范围查询。

VecDeque: 两端操作的优化

内部是 ring buffer——push_front 和 push_back 都是 O(1) amortized。适应 FIFO 队列和双端队列。与 Vec 的区别：Vec::remove(0) 是 O(n)（需要 memmove 所有元素），VecDeque::pop_front 是 O(1)（只移动 ring buffer 指针）。

选择指南

参考

• Rust Book: Chapter 8
• hashbrown: Rust HashMap 实现 (现在是 std)
• smallvec: docs.rs/smallvec

Keywords: Vec, HashMap, BTreeMap, VecDeque, SipHash, FxHash, ring buffer, reallocation