---
title: 集合类型
url: https://doc.liz6.com/rust/10-standard-library-depth/02-collection-types
locale: zh
area: rust
tags:
- rust
- 标准库深度
date: 2026-06-30
modified: 2026-06-30
description: Vec 是堆上的连续数组(随机访问 O(1)、尾部插入摊销 O(1)),HashMap 用 SwissTable 实现(缓存友好的开放寻址),BTreeMap 按键排序(Vec 的缓存局部性 vs BTreeMap 的有序遍历——两者不能兼得)。VecDeque 是环形缓冲区,两头推入都 O(1)。选型看访问模式:连…
---

# 集合类型

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

## Vec<T>: 动态数组

```rust
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

```rust
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 指针）。

## 选择指南

| 需求 | 推荐 |
|------|------|
| 顺序存储 + 随机访问 | Vec |
| FIFO | VecDeque |
| Double-ended queue | VecDeque |
| Key-value, unordered | HashMap (默认) / FxHashMap (高性能) |
| Key-value, ordered, range scan | BTreeMap |
| 小集合 (< 20 items) 无 heap | smallvec / tinyvec |
| 固定大小, 编译期已知 | `[T; N]` |

## 参考

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

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