数据结构选型：数组、链表、哈希表的性能博弈

说实话，我在嵌入式这行摸爬滚打了十几年，见过太多因为数据结构选型不当导致的性能灾难。有一次，一个同事用链表做实时数据采集的缓冲区，结果中断服务程序里频繁malloc/free，系统直接崩了。嗯，从那以后，我对数据结构的选择就格外谨慎。

今天咱们就聊聊数组、链表、哈希表这三兄弟。它们各有脾气，用对了是神器，用错了是坑。

一、数组：简单粗暴，但别滥用

数组是我个人最常用的数据结构。为什么？因为它连续存储，对缓存极度友好。

但数组也有软肋。插入和删除是O(n)的，而且大小固定。你想想看，如果你不知道数据量上限，要么浪费空间，要么面临扩容的尴尬。

// 数组遍历——缓存友好
int sum_array(int *arr, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];  // 顺序访问，预取器很开心
    }
    return sum;
}

二、链表：灵活但昂贵

链表的好处是插入删除快——O(1)就能搞定。但代价是什么？

首先，每个节点都有额外的指针开销。在32位系统上，一个int数据要额外带4字节的next指针；64位系统更夸张，8字节。你想想，存储效率直接打对折。

更致命的是，链表节点在内存里是散落的。遍历链表时，CPU得不停地从不同内存地址取数据，缓存行利用率极低。

// 链表遍历——缓存不友好
int sum_list(struct node *head) {
    int sum = 0;
    while (head) {
        sum += head->data;  // 每次访问都可能缓存缺失
        head = head->next;
    }
    return sum;
}

三、哈希表：查找利器，但别忽视开销

哈希表在查找场景下几乎是王者——平均O(1)的查找时间。但很多人忽略了它的代价。

哈希冲突处理、动态扩容、哈希函数计算……这些都有开销。而且哈希表的内存布局通常不连续，缓存友好性介于数组和链表之间。

// 简单的哈希表查找
int hash_lookup(struct hashtable *ht, int key) {
    int idx = key % ht->size;  // 哈希计算
    struct entry *e = ht->buckets[idx];
    while (e) {
        if (e->key == key) return e->value;
        e = e->next;  // 链地址法，可能跳转多次
    }
    return -1;
}

四、缓存行对齐：被忽视的性能杀手

说到性能，缓存行对齐是个绕不开的话题。现代CPU的缓存行通常是64字节。如果你的数据结构跨越了两个缓存行，访问它就需要两次内存读取。

我见过一个案例：一个结构体里有两个经常被不同线程访问的变量，恰好落在同一个缓存行里。结果两个线程互相"踢"对方的缓存行，性能下降了30%以上。这就是传说中的"伪共享"（False Sharing）。

// 缓存行对齐示例
struct alignas(64) cache_aligned_data {
    int counter_a;  // 线程A使用
    char padding[60];  // 填充到64字节
    int counter_b;  // 线程B使用
};

五、性能对比：一张表说清楚

操作	数组	链表	哈希表
随机访问	O(1) ★★★★★	O(n) ★	O(1)平均 ★★★★
插入/删除（已知位置）	O(n) ★★	O(1) ★★★★★	O(1)平均 ★★★★
缓存友好性	极高 ★★★★★	极低 ★	中等 ★★★
内存开销	极低 ★★★★★	高 ★★	较高 ★★★
适用场景	固定大小、频繁遍历	频繁插入删除、不关心顺序	快速查找、动态数据

六、知识体系图

下面这张图帮你理清数据结构选择的决策路径：

七、实战建议

说了这么多，到底该怎么选？我总结几条经验：

1. 默认用数组——除非你有明确的理由不用它。数组的缓存友好性是无与伦比的。
2. 链表用在正确的地方——比如需要频繁在中间插入删除，且数据量不大。但记得用内存池预分配节点，别用malloc。
3. 哈希表要选好哈希函数——我见过用取模做哈希的，结果数据分布不均匀，退化成链表。好的哈希函数能大幅减少冲突。
4. 缓存对齐不是玄学——在多线程场景下，用alignas(64)把热变量分开。虽然代码丑了点，但性能提升是实打实的。

---

公众号:蓝海资料掘金营，微信deep3321