后台高频算法

一致性哈希（Ring / Jump / Maglev）· 布隆过滤器 · HyperLogLog · LRU/LFU · 限流数学 · 树家族（B+/LSM/Merkle）——统一 C++ 实现

场景问题

想象你在饭店当传菜员：10 张桌子编号 0~9，客人的菜按"订单号 % 10"上桌，岁月静好。突然老板加开第 11 桌——灾难来了，几乎每桌的菜都要重算落到哪，全场跑堂原地爆炸。这就是取模分片扩容时的死法：hash % N 里 N 一变，几乎所有 key 换位置，缓存瞬间全失效、DB 被穿成筛子。下面这堆算法，一半是来治这个"多加一张桌就全乱"的病的。

实现方案

一致性哈希三种主流实现

扩缩容只迁 1/N 的直觉：环上加一个节点，只有"新节点逆时针到前一节点"这一小段的 key 改落到新节点，其余不动。

打个比方：把哈希环想成一个圆形钟表盘，每个节点是钉在盘面上的钉子，key 是掉进盘里顺时针滚的小球——球撞到的第一个钉子就归谁管。新钉一颗钉子进去，只有"从它逆时针到前一颗钉子"这段弧上的球改换门庭，别处的球压根没察觉老板换了人。类比失效边界：真实的环是 2³² 的哈希空间而非 12 小时刻度，而且每颗钉子还要"分身"成上百个虚拟节点撒满整圈，否则三五颗钉子会让球分布严重偏心（这也是虚拟节点存在的理由）。

Ring Hash 关键代码（C++）

#include <map>
#include <string>
#include <cstdint>

struct RingHash {
    std::map<uint32_t, std::string> ring;   // 有序：hash -> 物理节点
    int vnodes;
    RingHash(int v = 160) : vnodes(v) {}

    void addNode(const std::string& node) {
        for (int i = 0; i < vnodes; i++)
            ring[hash32(node + "#" + std::to_string(i))] = node;   // 每节点撒 V 个虚拟点
    }
    std::string get(const std::string& key) const {
        if (ring.empty()) return "";
        auto it = ring.lower_bound(hash32(key));   // 顺时针第一个 ≥ h 的虚拟节点
        if (it == ring.end()) it = ring.begin();   // 环回绕
        return it->second;
    }
    static uint32_t hash32(const std::string& s);  // xxhash/murmur，勿用 md5 截段（慢）
};

为何要虚拟节点：直接哈希物理 IP 分布严重不均；虚拟节点越多越均，代价是内存 + 变更时排序开销。

Jump Consistent Hash（Google 论文原版，C/C++ 通用）

int32_t jumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;                 // LCG
        j = (int64_t)((b + 1) * (double)(1LL << 31) / (double)((key >> 33) + 1));
    }
    return (int32_t)b;
}

核心思想：从 bucket 0 开始，每次以概率 (b+1)/(j+1) 决定"是否留在当前 bucket"。期望 O(log N)、内存 0、分布均匀。限制：bucket 必须 0~N-1 连续整数——只能尾部增删，不适合"无序删中间节点"。

Maglev：查找表 M 槽（素数 65537）；每后端按 P[i][j]=(offset[i]+j·skip[i]) mod M 生成偏好序列，轮流抢第一个空槽；查询 table[hash(key) mod M] 是 O(1)。扩缩容重填表，约 1/N 槽换主。

树的家族（面试高频）

为什么这么做

布隆过滤器（C++）

是什么：位数组 + K 个哈希函数；插入置 K 位，查询检查 K 位是否全 1。False Positive 存在（说"有"可能没有），False Negative 不存在（说"没有"一定没有）。假阳率 p ≈ (1 - e^(-kn/m))^k，最优 k = (m/n)·ln2；经验值每元素 ~10 bit → 假阳率 ~1%。

#include <vector>
#include <string>
#include <cstdint>

struct BloomFilter {
    std::vector<bool> bits;
    int k;                                          // 哈希函数个数
    BloomFilter(size_t m, int k) : bits(m, false), k(k) {}

    void add(const std::string& s) {
        uint64_t h1 = hashA(s), h2 = hashB(s);
        for (int i = 0; i < k; i++)
            bits[(h1 + (uint64_t)i * h2) % bits.size()] = true;   // 双哈希生成 k 个位
    }
    bool maybeContains(const std::string& s) const {
        uint64_t h1 = hashA(s), h2 = hashB(s);
        for (int i = 0; i < k; i++)
            if (!bits[(h1 + (uint64_t)i * h2) % bits.size()]) return false;  // 有 0 一定不存在
        return true;                                // 全 1 → 可能存在
    }
    static uint64_t hashA(const std::string&);      // 用不同 seed 的 murmur/xxhash
    static uint64_t hashB(const std::string&);
};

变种：Counting Bloom（位改计数器支持删除）、Cuckoo Filter（支持删除 + 更好局部性）、RedisBloom（BF.ADD/BF.EXISTS）。用途：缓存穿透（DB 都没有的 key 直接拒）、URL 去重、RocksDB SST 层判断"这层有没有 key"。

HyperLogLog

基数估算（多少不同元素）极小内存——12 KB 算 10 亿量级 UV，误差 <1%。原理：hash 分块，取每块前导 0 个数的最大值（"抛硬币连中 k 个正面 → n≈2^k"）。Redis PFADD/PFCOUNT 即此。

LRU / LFU / ARC

• LRU：unordered_map + 双向链表——O(1) 访问 + 移到头，淘汰尾部（见 数据结构）。
• LFU：按访问次数淘汰；冷启动慢（新元素次数少易被淘汰）；实现用"频次桶 + 每桶双向链表"。
• Redis LFU 用 8-bit 计数器 + 概率衰减，避免旧热点长期霸榜。

限流算法数学

• 令牌桶：tokens = min(cap, tokens + rate·Δt)，请求扣 N，tokens<N 拒 → 允许突发
• 漏桶：桶容量 + 恒定漏出速率 → 强制平滑
• 滑动窗口计数器：1 秒切 10 格，查询近 1 秒求和 → 内存 O(格数)（详见 令牌桶与漏桶）

为什么别的选择不行

• Ring Hash 虚拟节点太少 → 分布倾斜（100 起步，200 更稳）；用 md5 太慢 → 换 xxhash/murmur。
• Jump Hash 只能追加：删中间节点不行；解法是"打墓碑"（保留桶但不响应）。
• Maglev 表大小不是素数 → 分布不均。
• Bloom 用 md5 截段做多哈希 → 相关性强、假阳偏高：应用不同 seed 的独立哈希（或双哈希法 h1 + i·h2）。

沉淀结论

面试快速反应表

• 一致性哈希 → Ring / Jump / Maglev 三选一 + 虚拟节点 + 迁移 1/N
• 缓存穿透 → 布隆过滤器 + 空值缓存
• 有序集合 / 排行榜 → 跳表（Redis ZSet）或线段树
• 区间查询 → 线段树 / BIT
• 前缀匹配 → Trie / Radix Trie
• 数据校验 / 反熵 → Merkle 树
• 写多读少落盘 → LSM Tree；磁盘索引 → B+ 树；UV 估算 → HyperLogLog

面试高频题清单

• Q：Redis Cluster 怎么分片？ A：16384 个 slot（CRC16(key) mod 16384），节点认领 slot 区间；本质是"槽 + 一致性映射"，扩缩容按 slot 迁移。
• Q：一致性哈希 vs 取模分片？ A：取模 hash%N 在 N 变化时几乎全部 key 重映射；一致性哈希只迁 1/N，且虚拟节点保证均衡。
• Q：布隆过滤器怎么定 m 和 k？ A：给定 n 和目标假阳率 p，m = -n·ln p /(ln2)²，k = (m/n)·ln2；经验 ~10 bit/元素 ≈ 1%。
• Q：LSM 为什么写快、读可能慢？ A：写只追加 memtable/WAL（顺序 IO）；读要查 memtable + 多层 SSTable，靠布隆过滤器 + 分层 compaction 降读放大。

记忆口诀

• 一致性哈希：Ring 撒虚拟节点 / Jump 零内存但只能尾部增删 / Maglev 查表 O(1) / 三者都只迁 1/N
• 布隆过滤器：K 哈希置位 / 有 0 一定没有 / 全 1 可能有 / ~10 bit ≈ 1% 假阳 / 防缓存穿透
• 存储引擎树：写多落盘想 LSM / 磁盘索引想 B+ / 有序范围想跳表 / 校验反熵想 Merkle
• 概率数据结构：HyperLogLog 数基数 / 12 KB 算十亿 UV / 误差 <1%

内容来源

综合整理：Google Maglev / Jump Consistent Hash 论文、Redis / RocksDB 公开资料、《数据结构与算法分析》。代码为教学示意，生产请用成熟库（哈希用 xxhash/murmur）。

分工：本篇聚焦后台/分布式高频算法（一致性哈希各变体、布隆过滤器、LSM 等落地取舍）。树家族/堆/跳表等数据结构基础详见 数据结构，本篇不重复展开其基本定义。

自测：合上资料能说清楚吗？

1. 为什么一致性哈希扩缩容只迁移 1/N 的 key？取模分片相比之下差在哪？

2. 对比 Ring Hash、Jump Consistent Hash、Maglev 三者的取舍。

3. 布隆过滤器为什么能防缓存穿透？它会漏判吗？

4. LSM Tree 为什么写快、读可能慢？靠什么优化读？

5. HyperLogLog 用 12 KB 估算十亿量级基数的原理是什么？