主题 15设计模式与工程手写题

15.1手写题到底在考什么

面试官给你一张纸写 LRU，他心里有四条评分线，写完能跑只占第一条：

15.2LRU：三行 vs 六十行

先看现成的。构造 LinkedHashMap 时把 accessOrder 设成 true， 再重写一个方法：

LinkedHashMap<Integer, String> cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > 3;      // 超过容量就淘汰最久未用的
    }
};

实测行为（容量 3）：

put 1,2,3 之后: [1, 2, 3]
get(1) 之后:    [2, 3, 1]  <-- 1 移到末尾
put(4,d) 之后:  [3, 1, 4]  <-- 2 被淘汰

关键在于第二行：get(1) 之后，1 从队首跑到了队尾。 这就是 accessOrder = true 的作用——访问也算一次「使用」。 很多人手写时会漏掉这一点，只把 put 当作使用。

那为什么还要手写？因为面试官想看你知道它内部是怎么做到的。 核心是三个方法：afterNodeAccess（访问后移到队尾）、 afterNodeInsertion（插入后判断要不要淘汰）、afterNodeRemoval（删除时维护链表）。

手写版就是自己实现这三件事：

class LRU<K, V> {
    class Node { K k; V v; Node prev, next; }
    Map<K, Node> map = new HashMap<>();
    Node head, tail;              // 哨兵：head 最旧、tail.next 最新

    V get(K k) {
        Node n = map.get(k);
        if (n == null) return null;
        moveToHead(n);            // ★ 访问也要刷新（最容易漏的一行）
        return n.v;
    }

    void put(K k, V v) {
        Node n = map.get(k);
        if (n != null) { n.v = v; moveToHead(n); return; }
        if (map.size() == cap) {
            Node last = tail.prev;    // 淘汰最久未用的
            map.remove(last.k);
            unlink(last);
        }
        n = new Node(k, v);
        map.put(k, n);
        addHead(n);
    }
}

性能上两者几乎一样（100 万次 get + put，容量 1 万）：

LinkedHashMap:     45 ms
手写双向链表 :     54 ms
手写版是 0.83 倍速

手写版反而慢 20%。因为 LinkedHashMap 的三个钩子方法在 JIT 之后会被内联， 而我的版本多了一层 map.get + 方法调用。这不是重点—— 重点是「JDK 已经优化过的轮子，自己造不会更快」，这句话面试时说出来很加分。

15.3四种限流器，边界处见真章

限流是工程手写题里最容易写错的：四种实现里三种在日常流量下表现完全一样， 只有跨窗口边界时才露馅。为了结果可复现，这一节用虚拟时间 （把 now 当参数传进去，不读真实时钟）。

① 同样的瞬时洪峰，四个都合格

=== case1 四种限流器，限制 100/秒 ===
场景 A：t=0 这一刻打 500 个请求
  固定窗口     通过 100 / 500
  滑动窗口     通过 100 / 500
  令牌桶      通过 100 / 500
  漏桶       通过 100 / 500

这一组没有区分度。面试里如果只测这一组，会以为自己写对了。

② 跨窗口边界：固定窗口放过了 2 倍

=== case2 跨窗口边界：t=999 打 100，t=1001 再打 100 ===
  固定窗口     第一批 100 / 100，第二批 100 / 100，共 200
  滑动窗口     第一批 100 / 100，第二批   0 / 100，共 100
  令牌桶      第一批 100 / 100，第二批   0 / 100，共 100
  漏桶       第一批 100 / 100，第二批   1 / 100，共 101

固定窗口在 2 毫秒内放过了 200 个请求，是限制值的 2 倍。原因只有一句话：

t=999  -> 属于第 0 秒窗口，计数 0/100 -> 全部放行
t=1000 -> 窗口重置，计数归零
t=1001 -> 属于第 1 秒窗口，计数 0/100 -> 又全部放行

真实流量里，攻击者只要卡着秒的边界打，就能让固定窗口的限流形同虚设。 这就是为什么生产上不推荐固定窗口。

③ 稳态流量：四个又都一样

=== case3 稳态：每 10ms 一个请求，持续 2 秒（共 200 个）===
  固定窗口     通过 200 / 200
  滑动窗口     通过 200 / 200
  令牌桶      通过 200 / 200
  漏桶       通过 200 / 200

三个场景连起来看，才是完整结论：限流器的差别只在「突发」和「边界」， 平稳流量下没有区别。所以测限流器，一定要造突发。

15.4单例：为什么现在推荐枚举

单例的写法演进本身就是一部「如何防住反射和反序列化」的历史：

枚举那两列「是」不是巧合：Constructor.newInstance 里有一句硬检查——

if ((clazz.getModifiers() & Modifier.ENUM) != 0)
    throw new IllegalArgumentException("Cannot reflectively create enum objects");

反序列化则是因为枚举的 readObject 被特殊处理成「按名字查找已有实例」。 所以《Effective Java》说「单元素的枚举类型是实现单例的最佳方法」—— 它能挡住反射和反序列化这两个漏洞，而其他写法都挡不住。

15.5手写题的通用四步

不管题目是 LRU、限流、还是生产者消费者，套路都一样：

15.6速记卡与自查

动手清单与自查表