链表 vs 数组：为什么高性能系统偏爱连续内存？

从网络测量的视角看数据结构选择：cache locality 为什么比算法优雅更重要。

问题本质

链表和数组在性能上有什么区别？为什么很多高性能系统都不用链表？

这是一个经典但常被误解的问题。作为从事网络测量领域的工程师，我对性能的理解比较直接——在真实系统里，访存对性能的影响远远大于计算。

评估算法的两个核心指标

我们从代码角度评估一个测量算法，核心指标基本就两个：

1. 哈希计算次数 —— 对应 CPU 的计算开销
2. 访存次数 —— 对应内存系统的压力

当 cache、TLB、内存带宽都成为瓶颈之后，你会发现：一次 cache miss 的代价，可能抵得上成百上千次 CPU 运算。

链表的核心问题：随机访存

链表最大的问题在于指针跳转带来的随机访存。

想象一下这个场景： - 链表节点分散在内存各处 - 遍历链表时，CPU 需要不断跳转地址 - 每次跳转都可能导致 cache miss - 预取机制完全失效

一次链表遍历，基本等价于不断制造 cache miss。在现代 CPU 架构下，这意味着大量的流水线停顿和内存等待。

数组的优势：data locality

相比之下，数组、紧凑结构、甚至”看起来更复杂”的结构，只要内存布局连续，性能往往会好得多：

• 空间局部性：连续内存访问，CPU 预取机制高效工作
• 缓存友好：一个 cache line 能加载多个元素
• 向量化友好：SIMD 指令可以批量处理

工程实践：牺牲优雅换取性能

在我们的网络测量系统里，链式哈希表这种结构是完全用不了的。

我们宁愿牺牲一些算法层面的”优雅”，也要把访问次数压到最低、把 data locality 做到极致。因此所有的测量结构基本上都是：

• 二维数组结构
• 内存连续且固定
• 预分配避免动态分配

总结

链表在算法教材里很优雅，但在高性能系统中往往是性能杀手。当你需要在毫秒级甚至微秒级完成处理时，内存布局的连续性比数据结构的理论复杂度重要得多。

这不是说链表一无是处——在需要频繁插入删除、且对性能不敏感的场景，链表依然有用。但对于追求极致性能的系统，数组和紧凑结构才是正确的选择。