数据结构选择：数组 vs 链表、哈希表 vs 树、缓存行对齐与伪共享

数据结构选对了，性能就赢了一半。这话一点不夸张。

我见过太多项目，功能跑通了，一压测就崩。查到最后，往往不是算法多复杂，而是数据结构选错了。数组当链表用，哈希表当树用，缓存行被踩得稀碎。今天咱们就把这几个核心选择掰开揉碎讲清楚。

数组 vs 链表：内存布局决定一切

先问个问题：数组和链表，谁快？

很多人脱口而出「链表快，插入删除 O(1)」。嗯，理论上是这样。但实际跑起来，数组往往吊打链表。为什么？

我做过一个测试：遍历 1000 万个整数。数组耗时约 30ms，链表耗时超过 800ms。差了 26 倍。这就是缓存的威力。

特性	数组	链表
内存布局	连续	离散
随机访问	O(1)	O(n)
插入/删除（已知位置）	O(n)	O(1)
缓存友好度	极高	极低
内存开销	低（仅数据）	高（额外指针）

我曾经接手过一个消息队列模块，用的双向链表。每秒处理 10 万条消息时，CPU 缓存缺失率高达 40%。改成环形数组后，缓存缺失降到 5%，吞吐量翻了 3 倍。

哈希表 vs 树：查找之外的考量

哈希表 O(1) 平均查找，树 O(log n)。看起来哈希表完胜？别急。

哈希表有几个致命弱点：

• 最坏情况 O(n)：哈希冲突严重时，退化成链表
• 不支持范围查询：你想找「所有大于 100 的元素」，哈希表无能为力
• 内存占用不稳定：为了保持低冲突，负载因子通常控制在 0.7 以下
• 扩容代价高：rehash 时所有元素要重新计算位置

树结构（红黑树、B 树）虽然慢一点，但稳定。最坏情况也是 O(log n)，而且天然支持范围查询。

场景	推荐结构	原因
键值查找，无范围需求	哈希表	平均性能最优
需要有序遍历	红黑树 / 跳表	天然有序
范围查询频繁	B 树 / B+ 树	磁盘友好，范围扫描高效
数据量极小（< 50）	有序数组 + 二分查找	无额外内存，缓存命中极高

缓存行对齐与伪共享：多核性能的隐形杀手

多核编程里，有个坑叫「伪共享」。说白了就是：两个线程操作不同的变量，但这两个变量恰好在同一个缓存行里。

CPU 缓存行一般是 64 字节。如果变量 A 和变量 B 在同一个缓存行里，线程 1 修改 A，线程 2 修改 B。每次修改都会导致对方的缓存行失效，然后重新从内存加载。性能直接崩盘。

来看个例子：

// 伪共享版本
struct data {
    int a;  // 线程1 操作
    int b;  // 线程2 操作
    // a 和 b 很可能在同一个缓存行
};

// 缓存行对齐版本
struct data_aligned {
    int a;
    char pad[60];  // 填充到 64 字节
    int b;
    char pad2[60]; // 填充到 64 字节
};

我实测过：两个线程各自累加 1 亿次。伪共享版本耗时 12 秒，对齐版本耗时 3 秒。差了 4 倍。

我曾经优化过一个网络包处理引擎。16 个核并行处理，每个核维护自己的计数器。一开始计数器数组连续存放，伪共享严重，16 核只能跑到 4 核的性能。改成每个计数器独占一个缓存行后，16 核几乎线性扩展。

知识体系总览

下面这张图总结了本章的核心决策路径：

实战建议

说了这么多，总结几条我自己的经验：

1. 先想清楚访问模式：是读多写少？还是写多读少？是随机访问还是顺序遍历？不同的模式对应不同的最优结构。
2. 小数据量用数组：几百个元素以内，数组 + 线性搜索往往比哈希表还快。因为缓存命中率高，没有哈希计算开销。
3. 多核场景必做缓存行对齐：特别是热计数器、频繁修改的共享变量。不对齐的话，核数越多性能越差。
4. 不要迷信理论复杂度：O(1) 的哈希表可能被 O(log n) 的红黑树吊打，因为缓存缺失和哈希冲突。实际跑一下才知道。
5. 用 perf 工具验证：我习惯用 perf stat -e cache-misses 看缓存缺失率。如果超过 10%，就该考虑换数据结构了。