数组真的比链表快吗？我用1000万条数据实测了一遍，结论和教材说的不太一样

一、起因：删掉一层指针，P99 从 380ms 掉到 42ms

去年底我接手了一个日志聚合的小服务，逻辑不复杂：从 Kafka 拉日志，按 traceId 分组攒批，攒够一批再往下游写。当时数据结构用的是 map[string][]*LogEntry，value 是指针切片，想着后续要按时间排序、还要做插入删除，用指针省点拷贝。

压测到 8k QPS 的时候 P99 从 40ms 一路爬到 380ms，GC 一跑整个曲线就抖。我第一反应是 GC 问题，把 GOGC 从 100 调到 400，有用，但只降到 300ms 左右。后来拿 pprof 抓了 30 秒 CPU profile，发现热点根本不在 map 上，排在前面的是 runtime.memmove 和一堆我根本看不懂的地址，看着像是内存访问本身在拖后腿。

最后我做的事说出来你可能觉得没啥技术含量：把 []*LogEntry 换成 []LogEntry，同时把 LogEntry 从 96 字节压到 48 字节（主要是把一个 string 字段换成了固定长度的 [16]byte）。算法一行没改，数据结构名字都没换，P99 掉到 42ms。

这事让我重新去想一个被讲烂了的问题：数组和链表，到底谁快。

二、教材没骗你，但它少说了一半

所有讲数据结构的书都会告诉你：数组随机访问 O(1)，中间插入删除 O(n)；链表插入删除 O(1)，访问 O(n)。结论是频繁插入的场景选链表。这个推导没错，但它的前提是一个「所有内存地址访问代价相同」的理想模型，学术界管这个叫 RAM 模型（Random Access Machine）。

真实 CPU 不是这么工作的。一条 x86 的内存访问打到主存上大概要 80~100ns，而命中 L1 cache 只要 4 个周期、3GHz 下差不多 1.3ns，中间差了六七十倍。更关键的是，CPU 从来不是一个字节一个字节地读内存的，它按 cache line 搬，一条 line 64 字节。所以你读一个 int64（8 字节）的时候，硬件顺手把后面 7 个也塞进 cache 了。

这就是数组的隐藏红利：你顺序遍历一个 int64 数组，第一次 miss 之后，后面 7 次访问全是 L1 命中，实际平均每个元素的成本只有十几个 ns。而链表呢，每个节点的地址是 malloc 随机给的，next 指针指向哪，CPU 的硬件预取器（prefetcher）完全猜不到。每走一步都是一次潜在的主存访问，100ns 打底。

所以理论上 O(n) 和 O(n)，实际差了几十倍。大 O 记法把常数项和内存层级全给抹掉了，抹掉的那部分恰好是工程上最要命的部分。

三、1000 万条数据的实测对比

为了把感觉变成数字，我写了个小基准测试。机器是 M2 Pro 的 MacBook，Go 1.22，数据量 1000 万，元素是 int64。测试内容很简单，就是从头到尾遍历一遍求和，数组和链表各跑 5 次取中位数：

差了 28 倍。注意这个差距还是在「顺序访问」链表的情况下测出来的——链表节点的分配顺序恰好和遍历顺序一致，内存布局相对友好。如果把节点打乱插入，链表那个数字还要再翻一倍。

再补一个我踩过的坑：Go 里 []User（结构体切片）和 []*User（指针切片）差别也很大。我拿一个 48 字节的 struct 测，1000 万条顺序遍历，值切片 12ms，指针切片 96ms——8 倍。原因很简单，值切片一次 cache line 能塞 1.33 个元素，指针切片一次只能拿一个指针，还得再跳一次去解引用。

顺带说下 Go 的 map。Go 1.24（2025 年 2 月发布）把 map 的底层实现从原来的 bucket 数组（每个 bucket 8 个 kv，满了挂溢出桶）换成了 Swiss Table，就是 C++ absl 那套开放寻址 + 分组 SIMD 探测。同样是找 key，老的 bucket 链在负载高的时候会退化成多次指针跳转。如果你还在用 Go 1.21 之前的版本，map 在 1000 万量级上的 GC 压力是真的会让人怀疑人生。

四、那链表还有没有活路

有，但场景比你想的窄。

第一是节点大小极不均匀、无法预分配的时候。比如解析 JSON 得到的树，节点数量你不知道，用数组反而要反复扩容拷贝。第二是需要在已知位置做 O(1) 插入删除，而这个位置是通过外部引用直接拿到的——LRU 缓存就是标准案例，Go 的 container/list 配合 map 能做到读写都是 O(1)，这种结构用数组反而要写个双向链表模拟。第三是无锁并发队列，比如 Disruptor 的 ring buffer 是数组，但 Michael-Scott 队列就是链表，因为 CAS 操作在链表节点上更自然。

但我自己的经验是：绝大部分业务代码里的「链表需求」都是伪需求。你以为要频繁中间插入，实际上你是在尾部追加（用 slice 就够）；你以为要 O(1) 删除，实际上你在用 map 做索引，链表只是顺手记了个顺序。这种场景下把结构换成数组 + 索引表，性能往往直接起飞。

有个细节值得单独提：判断一个结构体多大，别靠数字段，用 unsafe.Sizeof 打印出来看。我见过有人以为自己写的是 32 字节的结构体，实际因为内存对齐 padding 成了 96 字节，cache line 白白浪费一半。字段顺序调一下（大的放前面，小的凑一起）经常能省 20%~30% 的内存。

五、几条能直接抄走的建议

1. 热点路径上的集合，优先用值切片 []T 而不是指针切片 []*T，除非 T 超过 128 字节或者需要多态。
2. 结构体字段按大小从大到小排，能减少 padding。我那个 96 字节压到 48 字节就有一半是这么省下来的。
3. 高频访问的结构考虑 SoA（结构体数组转数组结构体）。比如粒子系统里 x[]、y[]、vx[]、vy[] 分开存，只遍历 x 的时候其他字段不占用 cache line，实测能快 3~5 倍。
4. 别迷信大 O。写完之后跑一遍，用 perf stat 看 cache-misses 和 LLC-load-misses，这两个数字比 profile 里的函数耗时更能说明问题。
5. Java 那边也类似，HashMap 的链表长度到 8 且 table 容量 ≥ 64 才转红黑树（负载因子 0.75），这个阈值不是随便定的，就是因为链表短的时候遍历开销还不如树化的成本。

最后说句可能有点得罪人的话：很多面试题里「数组和链表的区别」的标准答案，是在一个现实中不存在的机器上推导出来的。背它没问题，但别真拿它指导写代码。我是被线上 P99 教过一次才明白的。