标题：选对数据结构，Rust 程序才能快起来：从原理到实践的性能思考

性能优化，从来不是“多开几条线程”或“换个编译参数”这么简单。在 Rust 里，性能的根基往往藏在对数据结构选择的细节之中。Rust 的标准库提供了丰富的数据结构：Vec、VecDeque、LinkedList、HashMap、BTreeMap、HashSet……它们都能完成任务，但不同选择背后的性能特征、内存模型和适用场景却差别极大。本文将深入探讨在 Rust 中如何基于底层特性做出正确的数据结构选择，并通过实测代码展示差异。

---

一、为什么数据结构选择影响性能

Rust 没有垃圾回收机制，每一次内存分配、移动、遍历，都会真实地反映在执行时间和内存布局上。
例如：

• Vec<T> 是连续内存结构，插入快、随机访问快，但中间插入或删除代价高。
• LinkedList<T> 每个节点独立分配，插入删除快，但缓存局部性差、遍历慢。
• HashMap<K, V> 哈希访问平均 O(1)，但哈希计算、碰撞处理和再散列会带来额外开销。
• BTreeMap<K, V> 访问复杂度 O(log n)，但在范围查询（range query）场景中优势明显。

这些结构的底层行为（尤其是内存布局和缓存利用率）直接决定了 Rust 程序的运行效率。

---

二、一个例子：Vec vs LinkedList 的性能差异

假设我们要存储 1,000,000 个整数，然后遍历求和。我们先分别用 Vec 和 LinkedList 实现：

use std::collections::LinkedList;
use std::time::Instant;

fn main() {
    let mut v = Vec::new();
    for i in 0..1_000_000 {
        v.push(i);
    }

    let mut list = LinkedList::new();
    for i in 0..1_000_000 {
        list.push_back(i);
    }

    let now = Instant::now();
    let sum_v: u64 = v.iter().map(|&x| x as u64).sum();
    println!("Vec sum: {} ({} µs)", sum_v, now.elapsed().as_micros());

    let now = Instant::now();
    let sum_l: u64 = list.iter().map(|&x| x as u64).sum();
    println!("List sum: {} ({} µs)", sum_l, now.elapsed().as_micros());
}

在多数机器上，Vec 版本的执行时间仅为 LinkedList 的 1/5 甚至 1/10。这是因为 Vec 内部的数据存储在连续的内存中，CPU 可以利用缓存预取（cache prefetching） 一次性加载多个元素。而 LinkedList 的节点散布在堆上，CPU 每次遍历都可能触发缓存未命中。

因此，Rust 的性能瓶颈往往不是算法本身，而是内存访问模式。

---

三、HashMap vs BTreeMap：哈希还是树结构？

在 Rust 的标准库中，HashMap<K, V> 和 BTreeMap<K, V> 是两种常用的键值存储结构。
选择哪一个，取决于访问模式：

• 若关注随机访问速度，HashMap 通常更优。
• 若需要有序遍历或范围查询，BTreeMap 更高效。

use std::collections::{HashMap, BTreeMap};
use std::time::Instant;

fn main() {
    let mut h = HashMap::new();
    let mut b = BTreeMap::new();
    for i in 0..100_000 {
        h.insert(i, i);
        b.insert(i, i);
    }

    let now = Instant::now();
    for _ in 0..1000 {
        let _ = h.get(&5000);
    }
    println!("HashMap get: {} µs", now.elapsed().as_micros());

    let now = Instant::now();
    for _ in 0..1000 {
        let _ = b.get(&5000);
    }
    println!("BTreeMap get: {} µs", now.elapsed().as_micros());
}

结果显示 HashMap 查询更快，但如果我们改为 for (k, v) in b.range(1000..2000) 进行区间访问，BTreeMap 的性能反而更优。
这说明 Rust 提供的不同数据结构不是“通用替代品”，而是针对不同访问模式做了权衡。

---

四、容量规划与内存分配策略

即便选择了合适的数据结构，如果忽视容量规划，也会引发频繁的重新分配（reallocation）。

例如在 Vec 或 HashMap 中动态插入时，如果容量不够，Rust 会申请新内存并迁移数据，这一过程极其昂贵。
因此：

• 使用 Vec::with_capacity(n) 预分配足够空间。
• 对 HashMap 使用 with_capacity() 避免多次 rehash。
• 对 String 使用 with_capacity() 避免多次堆扩容。

这类优化不会改变算法复杂度，却能显著减少堆分配次数，提升整体性能稳定性。

---

五、零拷贝与数据借用

Rust 的借用系统让我们可以在不牺牲安全的前提下避免不必要的内存拷贝。
举个例子，假设我们在 HashMap 中存储大量字符串键，使用 String 会导致分配与复制，而用 &str 则可直接借用原始数据：

let input = "apple banana orange";
let mut map = std::collections::HashMap::new();
for word in input.split_whitespace() {
    map.insert(word, word.len());
}

这段代码零分配完成插入。对性能敏感的 Rust 程序来说，这种借用思维比任何“算法优化”都更具性价比。

---

六、总结与思考

Rust 的高性能不仅源于零成本抽象和所有权模型，更体现在开发者能精确控制内存与数据结构行为。
在实际项目中，数据结构选择应遵循以下思路：

1. 优先使用 Vec —— 连续内存带来最佳性能；
2. 按访问模式选择 Map 类型 —— HashMap 随机快，BTreeMap 有序强；
3. 提前分配容量 —— 避免隐式 realloc；
4. 利用借用与切片 —— 减少拷贝与分配；
5. 关注缓存局部性 —— 内存布局往往决定性能上限。

Rust 不会替你“自动优化”，但它给了你完全的控制权。只有理解每一种数据结构在内存层面的表现，才能写出既安全又飞快的 Rust 代码。

---

结语：
Rust 的性能不是“神奇”的，而是“诚实”的——每个分配、每个结构的选择，都会被如实反映在运行时行为中。选对数据结构，就是写出高性能 Rust 程序的第一步。