第九章：数据结构与算法优化

说实话，很多C++程序员写了三五年代码，性能瓶颈往往不是语法不熟，而是数据结构选错了。我见过太多人用std::vector硬扛一切，结果缓存 miss 严重，程序跑得比蜗牛还慢。这一章，咱们就聊聊怎么选对数据结构，怎么让数据在内存里排兵布阵，以及两个实战利器——跳表和布隆过滤器。

9.1 选择合适的数据结构

选数据结构，说白了就是选「存取模式」。你想想看，如果你的代码里频繁做插入删除，却用了 vector，那每次插入都是 O(n) 的搬移，何必呢？

我个人习惯，先问自己三个问题：

• 数据量有多大？
• 读写比例是多少？
• 是否需要有序遍历？

举个例子。我在项目中做过一个实时日志系统，每秒写入几万条，但查询很少。一开始用了 std::map，结果 CPU 飙到 80%。后来换成 std::deque + 哈希索引，CPU 直接降到 15%。

9.2 缓存友好型设计

嗯，这里要注意。现代 CPU 和内存之间有个巨大的速度鸿沟。CPU 每秒能执行几十亿条指令，但内存访问一次要几十纳秒。这中间的差距，全靠缓存来填。

缓存友好，说白了就是让数据尽量在连续内存里待着。你想想看，CPU 加载一个 int 时，会把相邻的几十个字节一起拉进缓存。如果你能利用好这个特性，性能翻倍不是梦。

我曾经优化过一个矩阵乘法，原始版本是逐行遍历，缓存命中率很高。但有个同事写成了逐列遍历，结果每次都要从内存重新加载，慢了 8 倍。嗯，这就是缓存不友好的典型例子。

// 缓存友好：按行遍历
for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
        sum += matrix[i][j];
    }
}

// 缓存不友好：按列遍历
for (int j = 0; j < M; ++j) {
    for (int i = 0; i < N; ++i) {
        sum += matrix[i][j];
    }
}

9.3 跳表（Skip List）

跳表这东西，我第一次接触是在 LevelDB 的源码里。当时觉得这玩意儿挺神奇——用概率代替平衡，实现简单，性能还不赖。

说白了，跳表就是在有序链表上加了多层索引。底层是完整的有序链表，上层是「快速通道」。查找时从顶层开始，快速跳过大量元素。

我在项目中用跳表做过一个内存 KV 缓存。当时需要支持范围查询，红黑树写起来太麻烦，跳表三天就搞定了。而且并发读写时，只需要锁住局部节点，性能比全局锁好很多。

// 跳表节点定义（简化版）
struct SkipNode {
    int key;
    std::string value;
    std::vector<SkipNode*> forward; // 不同层级的指针
    SkipNode(int k, const std::string& v, int level)
        : key(k), value(v), forward(level + 1, nullptr) {}
};

// 查找操作
bool search(int key) {
    SkipNode* cur = head;
    for (int i = level; i >= 0; --i) {
        while (cur->forward[i] && cur->forward[i]->key < key) {
            cur = cur->forward[i];
        }
    }
    cur = cur->forward[0];
    return cur && cur->key == key;
}

9.4 布隆过滤器（Bloom Filter）

布隆过滤器，说白了就是一个「大概率正确」的集合。它告诉你「这个元素一定不在」或者「可能在」。用在缓存穿透、爬虫去重、垃圾邮件过滤等场景，效果拔群。

我记得有一次做推荐系统，每天要过滤几十亿次重复请求。如果用哈希表存所有已处理 ID，内存根本扛不住。后来用了布隆过滤器，每个元素只占几个 bit，内存直接降到原来的 1/100。

布隆过滤器的原理很简单：

• 一个 bit 数组（比如 1 亿个 bit）
• k 个哈希函数
• 插入时，把 k 个哈希位置都设为 1
• 查询时，检查 k 个位置是否全为 1

// 布隆过滤器核心实现
class BloomFilter {
    std::vector<bool> bits;
    int hashCount;
    
    size_t hash(const std::string& s, int seed) const {
        // 使用不同的 seed 模拟多个哈希函数
        std::hash<std::string> hasher;
        return hasher(s + std::to_string(seed)) % bits.size();
    }
    
public:
    BloomFilter(size_t size, int k) : bits(size, false), hashCount(k) {}
    
    void insert(const std::string& key) {
        for (int i = 0; i < hashCount; ++i) {
            bits[hash(key, i)] = true;
        }
    }
    
    bool mightContain(const std::string& key) const {
        for (int i = 0; i < hashCount; ++i) {
            if (!bits[hash(key, i)]) return false;
        }
        return true; // 可能误判
    }
};

9.5 知识体系总览

下面这张图，把本章的核心逻辑串起来了。你可以看到，数据结构选型、缓存优化、跳表和布隆过滤器，其实都围绕一个核心——「用空间换时间，用概率换效率」。

好了，这一章的内容就到这里。数据结构选型是基本功，缓存友好是进阶技巧，跳表和布隆过滤器是实战利器。你想想看，如果能把这几样东西用好，你的 C++ 程序性能至少能提升一个数量级。