第 6 节:选对容器——数据结构的学问

症状

"用 HashMap 还是 Vec?BTreeMap 还是 HashSet?"——容器选错,程序跑起来差一个数量级;选对,一行代码都不用改。

诊断

先认识容器家族的"性格"——每种容器的强项和代价都不同:

容器	强项	代价	场景
Vec<T>	按下标 O(1) 访问、顺序遍历快	中间插入/删除 O(n)	"列表"就该是 Vec
HashMap<K,V>	按键 O(1) 查找	哈希计算、顺序乱	"按名字找值"
BTreeMap<K,V>	按键查找 + 按键有序	比 HashMap 略慢(树)	"要排序遍历的键值"
HashSet<T>	去重、成员判断 O(1)	无序	"这个值出现过吗"
VecDeque<T>	两头 O(1) 插删	中间不行	队列、双端队列

最常见的"选错"是这三种:

1. "查名字"用了 Vec(线性扫描)

// 慢:每次查找遍历整个 Vec——1 万个名字,平均找 5000 次
let pet = pets.iter().find(|p| p.name == name);

// 快:HashMap 按名字建索引,O(1) 命中
let index: HashMap<&str, &Pet> = pets.iter().map(|p| (p.name.as_str(), p)).collect();
let pet = index.get(name);

2. "需要有序"用了 HashMap(顺序不可控)

// 尴尬:要按分数从低到高打印,HashMap 给不了顺序
let mut scores = HashMap::new();

// 正确:按序遍历时用 BTreeMap(或排序后用 Vec)
let mut scores = BTreeMap::new();
for (name, score) in &scores {
    println!("{}:{}", name, score);   // 按键名排序输出
}

3. "去重/判断存在"手写了 Vec 循环

// 慢:1 万个词,每个都扫一遍已有列表——O(n²)
let mut seen = Vec::new();
for word in words {
    if !seen.contains(&word) {
        seen.push(word);
    }
}

// 快:HashSet 天生去重,O(n)
let unique: HashSet<_> = words.iter().collect();

解药

选容器的三问:

1. 按什么找? 按下标/顺序 → Vec;按名字/键 → HashMap;还要有序 → BTreeMap
2. 要干嘛? 去重/存在判断 → HashSet;两头插删 → VecDeque;排序 → Vec + sort
3. 数据多大? 几十个元素,Vec 线性扫描反而快(常数小);上万才值得上哈希

经验法则:

• 小集合用 Vec:10 个元素的线性查找比 HashMap 快(哈希开销 > 遍历开销)
• 只增不改、按序访问 → Vec:排序一次,永远有序
• "查存在"永远 HashSet,别用 Vec::contains(除非很小)
• 双键索引:主结构用 Vec 存数据,再建几个 HashMap 当"索引"(数据库的玩法)

预防

• HashMap 的迭代顺序不稳定(第 7 章):需要稳定顺序就 BTreeMap 或排序
• HashSet 去重要元素实现 Hash + Eq:结构体要 #[derive(Hash, PartialEq, Eq)]
• 别"预优化":先用最直白的容器写对,数据量实测真的慢再换(总纲:先测,再优化)