框架手写复盘完,最后补数据结构的手写清单——这四件是 Java 面试「手写题」的高频四强:LRU 缓存、跳表、B+ 树、排序三件套。它们不是刷题的孤岛,每一个背后都拴着一个生产组件:LRU 拴着 Redis 与 15.2 的 MyBatis 缓存、跳表拴着 zset、B+ 树拴着 MySQL 索引(9.2)、排序拴着一切。手写时带着「它在哪上班」的问题写,写完对回原理章,一鱼两吃。
class LRUCache {
private int capacity;
private Map<Integer, Node> map = new HashMap<>();
private Node head, tail; // 虚拟头尾哨兵
class Node { int k, v; Node prev, next; }
public int get(int key) {
Node n = map.get(key);
if (n == null) return -1;
unlink(n); addFirst(n); // 命中即移到队头
return n.v;
}
public void put(int key, int value) {
Node n = map.get(key);
if (n != null) { n.v = value; unlink(n); addFirst(n); return; }
if (map.size() == capacity) { Node last = tail.prev; unlink(last); map.remove(last.k); } // 淘汰队尾
Node node = new Node(key, value); addFirst(node); map.put(key, node);
}
}
设计的关键是两个哨兵节点(虚拟头尾):所有 unlink/addFirst 都不碰 null 判断,代码减一半、边界 bug 减九成。复杂度账:HashMap 定位 O(1),链表移动 O(1),合起来 get/put 双 O(1)——单独用哪个都不行(链表查找 O(n)、Map 无序),组合的本质是「Map 管定位、链表管时序」的分工。写完对回生产:JDK 的 LinkedHashMap 把这套双向链表内建进 Map(accessOrder=true 即 LRU,重写 removeEldestEntry 三行实现),Redis 的近似 LRU 是另一个方向的取舍(随机采样省内存,10.1 讲过),MyBatis 一级缓存按 SqlSession 淘汰——同一思想的三种工程化。
单线程版跑通后值得加一道思考题:get 和 put 都是复合操作(查 Map+动链表两步),并发下链表指针会被两个线程拧断——Collections.synchronizedMap 只锁单个方法,救不了复合操作。最直接的手写解法是整个类一把 synchronized 锁,正确但吞吐随线程数跳水(链表操作全串行);进阶解法是分片:把一个 LRU 拆成十六个小 LRU,按 key 的 hash 路由,各片各锁——同一时刻最多十六个线程并行读写,淘汰粒度从全局变成片内(总容量除以片数),近似全局 LRU 而非严格 LRU,这是性能与语义的显式交换。写完分片版再回看 Caffeine:它用 CAS 加细粒度锁把读写窗口做到接近无锁——面试从「手写 LRU」追问到「并发下怎么办」,分片这一层答出来就超过八成候选人。
有序链表查找 O(n) 的痛点,跳表的解法是给部分节点加「高速层」:底层全量链表,上层每层抽一半节点,查找从最高层往右走到头再下一层——平均 O(log n)。手写核心是 findPrev(key) 从顶层一路「右移+下降」收集每层的前驱,插入时抛硬币定层高(每层 50% 概率晋升,最高封顶),删除按 findPrev 逐层摘链。最简版两层加随机层高约六十行。为什么 Redis zset 选跳表不选红黑树(10.1 的老问题,手写后答得更硬):跳表范围查询天然友好(找到起点沿底层链表扫)、实现与调试简单(指针单向、无旋转)、内存可调(层高概率可调稀疏)——红黑树的平衡靠旋转维护,跳表靠概率期望平衡,工程上「简单且够用」赢。
手写 B+ 树抓住三条不变量:非叶节点只存路由键(不存数据,一页 16K 能塞上千键——树矮三层的根因,9.2 的账在这里兑现);数据全在叶子节点且叶子串成有序链表(范围查询沿链表顺序扫,不必回溯树);分裂自底向上(叶子满了对半分裂,中间键上浮给父节点做新路由;根分裂则树高加一)。手写最小版:insert 时递归下行到叶子,叶子满了 split,返回上浮键给父层处理——分裂的回传是递归设计的精髓,也是写崩的重灾区(上浮键忘从叶子删除、父节点插入位置错位)。删除侧面试只要求说清「借键与合并」的策略,不必死磕代码。写完再看 9.2:为什么 MySQL 选 B+ 不选 B 树(非叶不存数据→更矮;叶子链表→范围查询)、为什么不用跳表(磁盘按页读,多叉一页一节点吞吐最优)——答案全在自己刚写的代码里。
面试手写排序不考全抄八种,考三件套及其变奏。快排:partition 双指针(挖坑法或交换法),平均 O(n log n) 最坏 O(n²)(已有序数组加固定取首元素),随机 pivot 或三数取中规避;递归深度 O(log n)。归并:分治递归加辅助数组合并,稳定 O(n log n),空间 O(n)——外排序与链表排序的主力(数组的逆序对、链表排序都爱用它)。堆排:建堆 O(n)(自底向上下沉而非逐个插入),取出 O(log n),原地 O(1) 空间——Top-K 问题的正主:一亿个数找最大前十,维护十容量小顶堆,扫一遍 O(n log k),这是 10.5 延迟任务与热点统计场景的通用解。三件套对比一句话答题:快排最快但最坏退化、归并稳定但要空间、堆排原地但缓存不友好(跳跃访问)——JDK 的 Arrays.sort 双轴快排加小数组插入排序,就是这个权衡表的工程答案。
四件手写数据结构是「原理章的实践补丁」:LRU 补缓存章、跳表补 Redis 章、B+ 树补索引章、堆排补 Top-K 场景——每件都建议「手写一遍、再对回对应章节的生产实现」,左手的代码与右手的中间件互相印证,两边都忘不掉。