经典算法专栏 #04：业务场景算法

真实世界的算法和面试题不一样——它们有明确的业务背景。本文以"业务场景 → 算法抽象 → 实现"的格式组织，覆盖限流、一致性哈希、Top-K、去重、分布式 ID、缓存淘汰等高频场景。

目录

限流算法

为什么需要限流

服务的处理能力有上限。面对以下三类场景，需要主动控制流量：

核心原则：宁可拒绝部分请求，也不让整个系统崩溃。

四种算法原理对比

计数器的临界问题：在窗口边界前后各发 100 个请求（共 200 个），两个窗口都认为自己未超限，但实际 1 秒内处理了 200 个请求，超出了限制。滑动窗口通过细粒度的时间格解决了这个问题。

令牌桶实现（Go 版本，可类比 Java）

type RateLimiter struct {
    rate   int64      // 每秒放入令牌数
    max    int64      // 令牌桶最大容量
    last   int64      // 上次请求时间（Unix 秒）
    amount int64      // 当前令牌数
    lock   sync.Mutex
}

func (rl *RateLimiter) Pass() bool {
    rl.lock.Lock()
    defer rl.lock.Unlock()

    now := time.Now().Unix()
    passed := now - rl.last                  // 距上次请求的秒数
    amount := rl.amount + passed*rl.rate     // 新增令牌
    if amount > rl.max {
        amount = rl.max                      // 不超过上限
    }
    if amount <= 0 {
        return false                         // 无令牌，拒绝
    }
    amount--
    rl.amount = amount
    rl.last = now
    return true
}

关键设计：不需要真的维护一个队列，通过时间差计算模拟令牌积累，约 50 行代码即可实现。令牌桶的"桶容量"决定了允许的最大突发量——桶满时一次性消费所有令牌，就是允许的最大突发。

滑动窗口实现（Java，基于 Redis ZSET）

// key: 用户/IP 标识，limit: 时间窗口内最大请求数，windowMs: 窗口大小（毫秒）
public boolean isAllowed(String key, int limit, long windowMs) {
    long now = System.currentTimeMillis();
    long windowStart = now - windowMs;

    try (Jedis jedis = pool.getResource()) {
        Pipeline pipe = jedis.pipelined();
        pipe.zremrangeByScore(key, 0, windowStart);  // 移除窗口外的请求
        pipe.zcard(key);                              // 统计窗口内请求数
        pipe.zadd(key, now, String.valueOf(now));     // 记录本次请求
        pipe.expire(key, (int)(windowMs / 1000) + 1);
        List<Object> results = pipe.syncAndReturnAll();

        long count = (Long) results.get(1);
        return count < limit;
    }
}

一致性哈希

为什么普通哈希不够用

分布式缓存集群扩缩容时，key % N 的方式会导致大量 key 重新映射（缓存雪崩）。

目标：节点增减时，只有少量 key 需要重新分配。

一致性哈希原理

1. 将整个哈希空间想象成一个 2³² 大小的环
2. 节点（bucket）通过哈希映射到环上某个位置
3. 请求（item）也映射到环上，顺时针找最近的节点
4. 为解决负载不均，引入虚拟节点：每个真实节点在环上放多个副本

真实节点 A → 虚拟节点 A-0, A-1, A-2, ... A-k

虚拟节点的作用：真实节点少时，哈希环上分布不均匀，某些节点承担的请求远多于其他节点。虚拟节点让每个真实节点在环上均匀分布，负载更均衡。

代码实现（Go，约 50 行）

import (
    "hash/crc32"
    "sort"
    "strconv"
)

type HashRing struct {
    nodes      map[uint32]string  // 哈希值 → 节点名
    replicates int                // 虚拟节点数量
    keys       []uint32           // 排序后的哈希值列表
}

func New(replicates int) *HashRing {
    return &HashRing{
        replicates: replicates,
        nodes:      make(map[uint32]string),
    }
}

// Add 向哈希环添加一个节点（及其虚拟节点）
func (h *HashRing) Add(node string) {
    for i := 0; i < h.replicates; i++ {
        hash := crc32.ChecksumIEEE([]byte(node + "-" + strconv.Itoa(i)))
        h.keys = append(h.keys, hash)
        h.nodes[hash] = node
    }
    // 保持有序，方便二分查找
    sort.Slice(h.keys, func(i, j int) bool { return h.keys[i] < h.keys[j] })
}

// Get 根据 key 找到负责的节点
func (h *HashRing) Get(key string) string {
    hash := crc32.ChecksumIEEE([]byte(key))
    // 二分查找第一个 >= hash 的位置（顺时针最近节点）
    idx := sort.Search(len(h.keys), func(i int) bool {
        return h.keys[i] >= hash
    })
    if idx == len(h.keys) {
        idx = 0  // 环形，超过最大值则回到起点
    }
    return h.nodes[h.keys[idx]]
}

效果：节点数量变化时，平均只有 1/N 的 key 需要重新分配（N 为节点数）。

Top-K 与排名

业务场景

• 热搜榜 Top-10
• 商品销量 Top-100
• 用户积分排名

三种方案对比

小顶堆求 Top-K（Java）

// 从 n 个数中找最大的 k 个数
// 为什么用小顶堆而不是大顶堆？
// 大顶堆需要全部入堆再弹出 k 次，O(n + klogn)
// 小顶堆维护 k 个最大值：堆顶是这 k 个数中最小的，遇到更大的就替换
public int[] topK(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int num : nums) {
        if (minHeap.size() < k) {
            minHeap.offer(num);
        } else if (num > minHeap.peek()) {
            minHeap.poll();       // 踢出最小值
            minHeap.offer(num);   // 放入更大的值
        }
    }
    return minHeap.stream().mapToInt(i -> i).toArray();
}
// 时间 O(nlogk)，空间 O(k)
// 优势：不需要全部数据加载到内存，适合流式处理

Redis ZSet 实现实时排行榜

// 更新用户分数
jedis.zadd("leaderboard", score, userId);

// 获取 Top-K（降序）
Set<Tuple> top10 = jedis.zrevrangeWithScores("leaderboard", 0, 9);

// 获取某用户排名（0-indexed，从高到低）
Long rank = jedis.zrevrank("leaderboard", userId);

// 获取某用户分数
Double userScore = jedis.zscore("leaderboard", userId);

为什么 Redis ZSet 适合排行榜：底层用跳表（skiplist）实现，插入/删除/查询排名都是 O(logn)，支持范围查询。跳表相比红黑树的优势是实现简单、并发性更好（可以用 CAS 做无锁并发）。

去重算法

业务场景

• 海量 URL 去重（爬虫）
• 缓存穿透防护
• 用户访问计数（UV）

布隆过滤器

原理：用 k 个哈希函数将元素映射到 Bitmap 的 k 个位置，置为 1。

• 判断不存在：k 个位置中有任何一位为 0 → 一定不存在
• 判断可能存在：k 个位置全为 1 → 可能存在（有误判率）

为什么有误判但没有漏判？ 插入时置 1 是永久的，所以已插入的元素查询时 k 个位一定全为 1，不会漏判。但不同元素可能共享某些位，导致误判（把未插入的元素判断为已插入）。

误判率公式：

误判率 ≈ (1 - e^(-kn/m))^k

其中：m = Bitmap 位数，n = 已插入元素数，k = 哈希函数个数
经验值：100 万数据，5 次 Hash，700 万位 Bitmap（<1MB），误判率 < 5%

使用 Guava 布隆过滤器（Java）：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

// 创建：预期 100 万元素，误判率 1%
BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(Charset.forName("UTF-8")),
    1_000_000,   // 预期元素数量
    0.01         // 误判率
);

// 添加元素
filter.put("user:12345");

// 查询（注意：返回 true 不代表一定存在）
boolean mightExist = filter.mightContain("user:12345");

缓存穿透防护流程：

请求 key
  → 布隆过滤器判断
      → 不存在：直接返回 null（拦截穿透）
      → 可能存在：查 Redis
          → 命中：返回
          → 未命中：查数据库
              → 有数据：写入 Redis，返回
              → 无数据：返回 null（5% 误判穿透可接受）

局限性：

1. 有误判率（可接受）
2. 不支持删除：某位的 1 可能被多个元素共享，删除一个元素会影响其他元素的判断。解决方案：Counting Bloom Filter（每位改为计数器）

HyperLogLog（基数估计）

场景：统计网站 UV（独立访客数），允许约 0.81% 的误差。

为什么不用 HashSet？ HashSet 存储每个 userId，内存随数据量线性增长，百万用户需要数十 MB。HyperLogLog 只需固定的 12KB，误差仅 0.81%，是工程上的极佳权衡。

// Redis HyperLogLog 统计 UV
jedis.pfadd("uv:20240101", userId);    // 记录访问
long uv = jedis.pfcount("uv:20240101"); // 估算独立访客数

// 合并多天数据
jedis.pfmerge("uv:week", "uv:20240101", "uv:20240102");

三种方案对比：

缓存淘汰

LRU（最近最少使用）

核心思想：利用时间局部性，优先淘汰最久未访问的数据。

数据结构：哈希表 + 双向链表（LinkedHashMap）

• 哈希表：O(1) 查找节点
• 双向链表：O(1) 移动节点（需要双向才能 O(1) 删除任意节点）

为什么用双向链表而非单向链表？ 删除任意节点需要知道前驱节点，单向链表需要 O(n) 遍历，双向链表可以通过 node.prev 直接 O(1) 操作。

Java O(1) 实现：

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);  // 虚拟头节点（最近使用端）
    private final Node tail = new Node(0, 0);  // 虚拟尾节点（最久未用端）

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToHead(node);    // 访问后移到头部（最近使用）
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            moveToHead(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node removed = removeTail();  // 淘汰最久未用的
                map.remove(removed.key);
            }
        }
    }

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }

    static class Node {
        int key, val;
        Node prev, next;
        Node(int key, int val) { this.key = key; this.val = val; }
    }
}
// get/put 均为 O(1)

LFU（最不经常使用）

核心思想：淘汰访问频次最低的数据；频次相同时淘汰最久未访问的。

数据结构：

• keyMap：key → (value, freq)
• freqMap：freq → LinkedHashSet（保持插入顺序，方便淘汰）
• minFreq：当前最小频次

为什么用 LinkedHashSet？ 同频次的 key 需要按插入顺序淘汰（即最久未访问的），LinkedHashSet 保持插入顺序且支持 O(1) 删除，恰好满足需求。

class LFUCache {
    private final int capacity;
    private int minFreq = 0;
    private final Map<Integer, int[]> keyMap = new HashMap<>(); // key -> [val, freq]
    private final Map<Integer, LinkedHashSet<Integer>> freqMap = new HashMap<>();

    public LFUCache(int capacity) { this.capacity = capacity; }

    public int get(int key) {
        if (!keyMap.containsKey(key)) return -1;
        increaseFreq(key);
        return keyMap.get(key)[0];
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;
        if (keyMap.containsKey(key)) {
            keyMap.get(key)[0] = value;
            increaseFreq(key);
        } else {
            if (keyMap.size() >= capacity) evict();
            keyMap.put(key, new int[]{value, 1});
            freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
            minFreq = 1;
        }
    }

    private void increaseFreq(int key) {
        int freq = keyMap.get(key)[1];
        keyMap.get(key)[1]++;
        freqMap.get(freq).remove(key);
        if (freqMap.get(freq).isEmpty()) {
            freqMap.remove(freq);
            if (minFreq == freq) minFreq++;
        }
        freqMap.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }

    private void evict() {
        LinkedHashSet<Integer> minSet = freqMap.get(minFreq);
        int evictKey = minSet.iterator().next();  // 最久未用的（LinkedHashSet 保持插入顺序）
        minSet.remove(evictKey);
        if (minSet.isEmpty()) freqMap.remove(minFreq);
        keyMap.remove(evictKey);
    }
}
// get/put 均为 O(1)

LRU vs LFU 对比

分布式 ID

业务需求

• 全局唯一：多节点并发生成不重复
• 粗略有序：按时间递增，便于数据库索引
• 高性能：本地生成，无网络调用

主流方案对比

雪花算法（Snowflake）

64 位结构：

为什么这样划分位数？

• 41 bit 时间戳：2⁴¹ 毫秒 ≈ 69 年，足够大多数业务生命周期
• 10 bit 机器 ID：1024 台机器，可以拆分为 5 bit 数据中心 + 5 bit 机器
• 12 bit 序列号：同一毫秒内 4096 个 ID，单机 400 万/秒，远超大多数业务需求

Java 实现（含时钟回拨处理）：

public class Snowflake {
    private static final long EPOCH = 1420070400000L;  // 自定义起始时间（2015-01-01）
    private static final int NODE_BITS = 10;
    private static final int SEQ_BITS = 12;
    private static final long MAX_NODE = (1L << NODE_BITS) - 1;    // 1023
    private static final long MAX_SEQ  = (1L << SEQ_BITS) - 1;     // 4095

    private final long nodeId;
    private long lastTimestamp = -1L;
    private long sequence = 0L;

    public Snowflake(long nodeId) {
        if (nodeId < 0 || nodeId > MAX_NODE)
            throw new IllegalArgumentException("nodeId must be in [0, " + MAX_NODE + "]");
        this.nodeId = nodeId;
    }

    public synchronized long nextId() {
        long now = currentMs();

        // 时钟回拨处理：等待时钟追上
        if (now < lastTimestamp) {
            long offset = lastTimestamp - now;
            if (offset <= 5) {
                // 回拨不超过 5ms，等待追上
                try { Thread.sleep(offset); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
                now = currentMs();
            }
            if (now < lastTimestamp) {
                throw new RuntimeException("Clock moved backwards. Refusing to generate id.");
            }
        }

        if (now == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQ;
            if (sequence == 0) {
                now = waitNextMs(now);  // 序列号耗尽，等到下一毫秒
            }
        } else {
            sequence = 0;
        }
        lastTimestamp = now;

        return ((now - EPOCH) << (NODE_BITS + SEQ_BITS))
             | (nodeId << SEQ_BITS)
             | sequence;
    }

    private long currentMs() { return System.currentTimeMillis(); }

    private long waitNextMs(long current) {
        long ts = currentMs();
        while (ts <= current) ts = currentMs();
        return ts;
    }
}

时钟回拨的根本原因：NTP 时间同步可能导致系统时间向前调整。

处理策略：

推荐算法基础（补充）

协同过滤

基于用户的协同过滤：找到与目标用户行为相似的用户，推荐他们喜欢但目标用户未看过的内容。

相似度计算：

// 余弦相似度：cos(θ) = A·B / (|A| × |B|)
// 衡量两个向量的方向相似度，不受向量长度影响（适合用户评分数量不同的场景）
public double cosineSimilarity(Map<String, Double> userA, Map<String, Double> userB) {
    double dotProduct = 0, normA = 0, normB = 0;
    for (String key : userA.keySet()) {
        if (userB.containsKey(key)) {
            dotProduct += userA.get(key) * userB.get(key);
        }
        normA += userA.get(key) * userA.get(key);
    }
    for (double v : userB.values()) normB += v * v;
    return normA == 0 || normB == 0 ? 0 : dotProduct / (Math.sqrt(normA) * Math.sqrt(normB));
}

// Jaccard 相似度（适合集合）：|A∩B| / |A∪B|
// 衡量两个集合的重叠程度，适合"是否购买/是否点赞"这类二值数据
public double jaccardSimilarity(Set<String> setA, Set<String> setB) {
    Set<String> intersection = new HashSet<>(setA);
    intersection.retainAll(setB);
    Set<String> union = new HashSet<>(setA);
    union.addAll(setB);
    return union.isEmpty() ? 0 : (double) intersection.size() / union.size();
}

搜索排序（TF-IDF）

TF-IDF：衡量词语对文档的重要程度。

TF(t, d)   = 词 t 在文档 d 中出现的次数 / 文档 d 的总词数
IDF(t, D)  = log(文档总数 / 包含词 t 的文档数 + 1)
TF-IDF(t, d, D) = TF(t, d) × IDF(t, D)

直觉：TF 衡量词在文档中的频率（词越常见越重要），IDF 衡量词在整个语料库中的稀缺性（越稀有越有区分度）。"的"、"是"这类词 TF 高但 IDF 极低，最终权重接近 0。

BM25（TF-IDF 的改进版，Elasticsearch 默认使用）：

BM25(t, d) = IDF(t) × (TF(t,d) × (k₁+1)) / (TF(t,d) + k₁ × (1-b+b×|d|/avgdl))

其中：k₁ ≈ 1.2~2.0（词频饱和参数），b ≈ 0.75（文档长度归一化参数）

BM25 的改进：对高频词的贡献做了"饱和"处理，避免某个词出现 100 次比出现 10 次的文档得分高 10 倍。同时通过文档长度归一化，避免长文档因词频绝对值高而获得不公平的优势。

算法选型速查

参考资料

• 极客时间《业务开发算法 50 讲》— 微扰君
• Redis 官方文档 — LRU/LFU 缓存策略
• Twitter Snowflake 开源实现
• Google Guava BloomFilter 源码