3. 数据结构选择：数组 vs 链表、哈希表 vs 平衡树、缓存友好性对性能的影响
数据结构选型这事儿，我做了十几年优化，发现很多性能问题其实不是算法多复杂，而是数据结构选错了。说白了，选对了数据结构，性能问题就解决了一半。今天咱们就聊聊几个经典的选择题：数组还是链表？哈希表还是平衡树？以及那个容易被忽略的——缓存友好性。
3.1 数组 vs 链表：内存布局决定一切
先问个问题：你写代码时，什么时候用数组，什么时候用链表？
很多人会说：「数组适合随机访问，链表适合频繁插入删除。」这话没错，但不够深入。我个人的经验是——缓存友好性才是真正的分水岭。
3.1.1 数组：连续内存的王者
数组的元素在内存中是连续存放的。这意味着什么？
- CPU缓存命中率高：当你访问
arr[0]时，CPU 会把相邻的arr[1]、arr[2]也加载到缓存行中。后续访问几乎就是零延迟。 - 预取器友好：现代 CPU 有硬件预取器，能识别连续访问模式，提前把数据拉到缓存。
- 内存开销低：没有额外的指针存储，每个元素只存数据本身。
核心结论：如果你的数据是「批量处理」或「顺序遍历」，数组几乎总是比链表快，哪怕插入删除操作多一些。
3.1.2 链表：指针跳跃的代价
链表每个节点都包含数据和指向下一个节点的指针。节点在内存中可能分散在各处。
我曾经优化过一个消息队列系统，原本用链表实现，吞吐量一直上不去。一分析发现：缓存缺失率高达 70%。每次访问下一个节点，CPU 都要去主存里捞数据，延迟是缓存的几十倍。
避坑指南：我曾经接手过一个项目，用链表存储高频交易订单簿。每次遍历都要跳跃几十个缓存行，延迟直接爆表。后来改成数组+空闲索引池，性能提升了 5 倍。
3.1.3 什么时候该用链表？
说实话，现代 C++ 里链表的使用场景越来越窄。我个人觉得只有两种情况值得考虑：
- 需要常数时间的中间插入/删除，且数据量很大，数组的移动成本无法接受。
- 节点本身很大，移动成本高，且插入删除频繁。
但即便在这两种情况下，我也建议先试试 std::vector + 延迟删除标记，或者 std::deque。你想想看，vector 的尾部插入是摊还常数时间，而且缓存友好性吊打链表。
3.2 哈希表 vs 平衡树：查找与有序的博弈
哈希表和平衡树，这是另一个经典选择题。我见过不少团队在这上面栽跟头。
3.2.1 哈希表：快，但有代价
哈希表的平均查找时间是 O(1)，这听起来很完美。但实际使用中，有几个坑：
- 哈希冲突：当冲突严重时，查找退化为 O(n)。我遇到过用
std::unordered_map存字符串键，默认哈希函数导致大量冲突，性能直接崩了。 - 内存碎片：开放寻址法的哈希表需要预分配大量内存，链地址法则会产生指针跳跃。
- 不支持范围查询：你想找「所有 key 在 [100, 200] 之间的元素」？哈希表做不到。
我的习惯：如果键是整数且范围可控，我会用 std::vector 做直接索引，比哈希表快一个数量级。比如 ID 范围 0~10000，直接开个 10001 大小的数组，访问就是 O(1) 且零哈希开销。
3.2.2 平衡树：有序的代价
平衡树（如红黑树、AVL树）的查找是 O(log n)，比哈希表慢，但提供了有序性。
我记得有一次做实时排行榜系统，需要频繁查询「第 10 名到第 20 名的数据」。用哈希表根本没法做，只能用 std::set 或 std::map。平衡树虽然慢一点，但能直接支持范围遍历。
| 特性 | 哈希表 | 平衡树 |
|---|---|---|
| 平均查找时间 | O(1) | O(log n) |
| 最坏查找时间 | O(n) | O(log n) |
| 有序遍历 | 不支持 | 支持 |
| 范围查询 | 不支持 | 支持 |
| 内存开销 | 中等（预分配） | 较高（每个节点多指针） |
| 缓存友好性 | 差（跳跃访问） | 差（树形结构） |
3.2.3 我的选择策略
说白了，就一句话：需要有序就用平衡树，不需要就用哈希表。但这里有个细节：
- 如果数据量很小（比如 < 100 个元素），
std::vector+ 线性查找可能比哈希表还快。因为哈希计算的开销比线性比较还大。 - 如果键是整数且分布均匀，试试
std::unordered_map的开放寻址变体（如absl::flat_hash_map），性能比标准库好很多。
3.3 缓存友好性：被忽视的性能杀手
嗯，这里我要重点说说缓存友好性。很多开发者只关注算法复杂度，却忽略了内存访问模式对性能的影响。
为什么会这样？因为 CPU 缓存是透明的，你看不到它。但它的影响巨大——一次缓存缺失的代价是缓存命中的 100 倍以上。
3.3.1 什么是缓存友好？
简单说，就是你的数据访问模式要符合 CPU 缓存的运作方式：
- 空间局部性：访问一个数据后，大概率会访问它附近的数据。
- 时间局部性：访问一个数据后，短时间内可能再次访问它。
数组天然满足空间局部性，链表则完全相反。
3.3.2 实战案例：矩阵遍历
来看个经典例子。假设有一个 10000x10000 的矩阵，按行遍历和按列遍历，性能差多少？
// 按行遍历（缓存友好）
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
sum += matrix[i][j];
}
}
// 按列遍历（缓存不友好）
for (int j = 0; j < N; ++j) {
for (int i = 0; i < N; ++i) {
sum += matrix[i][j];
}
}我在项目中实测过，按行遍历比按列遍历快 10 倍以上。原因很简单：按行遍历时，每次访问 matrix[i][j]，相邻的 matrix[i][j+1] 已经在缓存里了。按列遍历则每次都要跳到很远的内存地址，缓存完全失效。
核心原则：写代码时，脑子里要有一张「内存布局图」。想想你的数据在内存里是怎么排列的，然后让访问顺序跟它一致。
3.3.3 结构体布局优化
另一个常见问题是结构体成员的排列顺序。我见过有人把热点数据和非热点数据混在一起，导致缓存行被污染。
// 缓存不友好：热点数据分散
struct BadLayout {
int hot_data1;
char padding[60]; // 非热点
int hot_data2;
};
// 缓存友好：热点数据集中
struct GoodLayout {
int hot_data1;
int hot_data2;
char padding[60]; // 非热点放后面
};你想想看，访问 hot_data1 时，CPU 会把整个缓存行（通常 64 字节）加载进来。如果 hot_data2 也在同一缓存行里，下次访问就是零成本。否则就要重新加载。
3.4 知识体系总览
下面这张图总结了本章的核心逻辑，帮你快速理清思路：
3.5 总结与建议
说了这么多，最后给几条实用建议：
- 默认用
std::vector：除非你有非常明确的理由，否则别碰链表。vector 的缓存友好性在绝大多数场景下完胜。 - 哈希表优先，但注意哈希函数：不需要有序时，用
std::unordered_map或更好的absl::flat_hash_map。但一定要测试哈希冲突率。 - 脑子里时刻想着缓存：写循环时，想想数据在内存里怎么排列。按顺序访问，别跳来跳去。
- 小数据量用线性结构：少于 100 个元素时，
std::vector的线性查找可能比哈希表还快。
我的个人习惯：每次写完一段性能敏感的代码，我都会用 perf 工具看看缓存缺失率。如果 L1 缓存缺失率超过 10%，我就会重新审视数据结构的选择。这个习惯帮我避免了很多性能灾难。
数据结构选型没有银弹，但理解了缓存友好性这个底层原理，你就能做出更明智的决策。记住：数据怎么放，决定了代码跑多快。