【Java 面试题】手写 LRU（Least Recently Used）缓存 Java 源代码

下面给你可直接在面试中手写的 LRU（Least Recently Used）缓存 Java 源代码，支持 O(1) put/get，基于HashMap + 双向链表。
代码简洁、无多余封装、适合白板面试。

✔手写 LRUCache（Java 完整代码）

importjava.util.HashMap;importjava.util.Map;publicclassLRUCache{classNode{intkey,value;Nodeprev,next;publicNode(intk,intv){key=k;value=v;}}privatefinalintcapacity;privatefinalMap<Integer,Node>map;privatefinalNodehead,tail;// 哨兵节点publicLRUCache(intcapacity){this.capacity=capacity;map=newHashMap<>();head=newNode(-1,-1);tail=newNode(-1,-1);head.next=tail;tail.prev=head;}publicintget(intkey){if(!map.containsKey(key))return-1;Nodenode=map.get(key);remove(node);insertToHead(node);returnnode.value;}publicvoidput(intkey,intvalue){if(map.containsKey(key)){Nodenode=map.get(key);node.value=value;remove(node);insertToHead(node);}else{if(map.size()==capacity){Nodelast=tail.prev;remove(last);map.remove(last.key);}NodenewNode=newNode(key,value);insertToHead(newNode);map.put(key,newNode);}}privatevoidremove(Nodenode){node.prev.next=node.next;node.next.prev=node.prev;}privatevoidinsertToHead(Nodenode){node.next=head.next;head.next.prev=node;node.prev=head;head.next=node;}}

🔍关键点说明（适合面试说）

📌 时间复杂度

🔥 你可以在面试中这么总结

LRU 需要 O(1) 的删除和插入操作，所以必须使用 HashMap + 双向链表。Map 用于快速查找节点位置；链表用于维护访问时间顺序，最新放在头部，超过容量时从尾部移除最旧的节点。

如需扩展版本（支持泛型、线程安全、LinkedHashMap 一行实现），回复：继续升级版本🚀

你需要手写LRU（最近最少使用）缓存的Java完整源代码，我会优先提供面试高频考察的底层实现版本（HashMap + 双向链表）（这是手写LRU的核心考点），同时补充基于LinkedHashMap的简易版，方便你对比理解。

一、核心原理说明

LRU的核心规则是：当缓存容量达到上限时，移除最近最少使用的元素；get/put操作会将元素标记为「最近使用」。

• 用HashMap实现O(1)时间复杂度的节点查找；
• 用双向链表维护元素的访问顺序（头节点=最近使用，尾节点=最久未使用）；
• 核心操作：get（查+移到头部）、put（增/更+移到头部，超容则删尾节点）。

二、底层实现版（HashMap + 双向链表）

这是面试手写的标准版本，无依赖JDK高级封装，能体现底层逻辑理解：

importjava.util.HashMap;importjava.util.Map;/** * 手写LRU缓存：基于HashMap + 双向链表实现 * 核心：O(1)查找（HashMap） + O(1)增删（双向链表） */publicclassLRUCache{// 双向链表节点类（存储key+value，以及前后指针）staticclassDNode{intkey;intvalue;DNodeprev;DNodenext;publicDNode(){}publicDNode(intkey,intvalue){this.key=key;this.value=value;}}// 缓存容量privateintcapacity;// 实际存储的元素数量privateintsize;// HashMap：快速定位节点（key=缓存key，value=链表节点）privateMap<Integer,DNode>cacheMap;// 双向链表的伪头/伪尾（避免空指针判断，简化操作）privateDNodehead;privateDNodetail;// 构造方法：初始化容量、HashMap、双向链表头尾publicLRUCache(intcapacity){this.capacity=capacity;this.size=0;this.cacheMap=newHashMap<>();// 初始化伪头、伪尾，且相互指向head=newDNode();tail=newDNode();head.next=tail;tail.prev=head;}/** * 获取缓存值：O(1) * @param key 缓存key * @return 存在则返回value，否则返回-1 */publicintget(intkey){DNodenode=cacheMap.get(key);if(node==null){return-1;}// 访问后，将节点移到「最近使用」的头部moveToHead(node);returnnode.value;}/** * 存入缓存：O(1) * @param key 缓存key * @param value 缓存value */publicvoidput(intkey,intvalue){DNodenode=cacheMap.get(key);if(node==null){// 1. 新节点：创建+加入HashMap+加入链表头部DNodenewNode=newDNode(key,value);cacheMap.put(key,newNode);addToHead(newNode);size++;// 2. 超容量：移除「最久未使用」的尾节点（同时删除HashMap中的记录）if(size>capacity){DNodetailNode=removeTail();cacheMap.remove(tailNode.key);size--;}}else{// 已有节点：更新value + 移到头部（标记为最近使用）node.value=value;moveToHead(node);}}// ===== 双向链表辅助方法 =====/** * 将节点添加到链表头部（伪头之后） */privatevoidaddToHead(DNodenode){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}/** * 移除指定节点 */privatevoidremoveNode(DNodenode){node.prev.next=node.next;node.next.prev=node.prev;}/** * 将节点移到头部（先移除，再添加到头部） */privatevoidmoveToHead(DNodenode){removeNode(node);addToHead(node);}/** * 移除最久未使用的尾节点（伪尾之前的节点） */privateDNoderemoveTail(){DNoderealTail=tail.prev;removeNode(realTail);returnrealTail;}// 测试用例publicstaticvoidmain(String[]args){LRUCachelruCache=newLRUCache(2);lruCache.put(1,1);// 缓存：{1=1}lruCache.put(2,2);// 缓存：{1=1, 2=2}System.out.println(lruCache.get(1));// 输出1，缓存：{2=2, 1=1}（1移到头部）lruCache.put(3,3);// 容量超2，移除最久未使用的2，缓存：{1=1, 3=3}System.out.println(lruCache.get(2));// 输出-1（已被移除）lruCache.put(4,4);// 容量超2，移除最久未使用的1，缓存：{3=3, 4=4}System.out.println(lruCache.get(1));// 输出-1（已被移除）System.out.println(lruCache.get(3));// 输出3，缓存：{4=4, 3=3}System.out.println(lruCache.get(4));// 输出4，缓存：{3=3, 4=4}}}

三、关键代码解释

1. 双向链表节点（DNode）：

   • 存储key（移除尾节点时，需要通过key删除HashMap中的记录）、value；
   • prev/next：前后指针，实现O(1)时间的节点增删。

2. 伪头/伪尾（head/tail）：

   • 避免处理「头节点为空」「尾节点为空」的边界情况，简化代码逻辑。

3. 核心方法：

   • get：查不到返回-1；查到则移到头部（标记为最近使用）；
   • put：
     • 新节点：创建→加HashMap→加链表头部→超容则删尾节点（同步删HashMap）；
     • 已有节点：更新value→移到头部；
   • 辅助方法：addToHead（加头部）、removeNode（删节点）、moveToHead（移头部）、removeTail（删尾节点）。

四、简易版（基于LinkedHashMap）

JDK的LinkedHashMap天然支持按访问顺序排序，只需重写removeEldestEntry即可实现LRU，适合工程开发（但面试手写不推荐，体现不出底层能力）：

importjava.util.LinkedHashMap;importjava.util.Map;publicclassLRUCacheSimpleextendsLinkedHashMap<Integer,Integer>{privateintcapacity;publicLRUCacheSimple(intcapacity){// 初始化：初始容量=capacity，负载因子=0.75，按访问顺序排序（第三个参数=true）super(capacity,0.75f,true);this.capacity=capacity;}publicintget(intkey){// 父类get方法会自动将节点移到「最近使用」位置returnsuper.getOrDefault(key,-1);}publicvoidput(intkey,intvalue){super.put(key,value);}/** * 重写该方法：当元素数量超过容量时，移除最久未使用的元素 */@OverrideprotectedbooleanremoveEldestEntry(Map.Entry<Integer,Integer>eldest){returnsize()>capacity;}// 测试用例和底层版一致publicstaticvoidmain(String[]args){LRUCacheSimplelru=newLRUCacheSimple(2);lru.put(1,1);lru.put(2,2);System.out.println(lru.get(1));// 1lru.put(3,3);System.out.println(lru.get(2));// -1lru.put(4,4);System.out.println(lru.get(1));// -1System.out.println(lru.get(3));// 3System.out.println(lru.get(4));// 4}}

总结

1. 面试手写LRU优先选HashMap + 双向链表实现，核心是「O(1)查找 + O(1)增删」；
2. 双向链表需维护「伪头/伪尾」简化边界处理，节点必须存key（删尾节点时同步删HashMap）；
3. get/put操作都要将节点移到头部，超容时删除尾节点（最久未使用）。

下一步迭代建议

需要我为你分析这个LRU实现的时间/空间复杂度，以及面试中可能被追问的「线程安全优化方案」吗？

下面是一个「简单版」的 LRU 缓存实现，只用到基础数据结构：

• 一个HashMap<K, Node<K,V>>（O(1) 查找 key 对应节点）
• 一个自定义的双向链表（O(1) 把节点移动到头部 / 删除尾部）

这里的 LRU 语义：

• get(key)：如果存在，返回值，并把节点移动到链表头部（最近使用）。
• put(key, value)：
  • 如果 key 已存在：更新值，并移动到头部
  • 如果 key 不存在：新建节点插入头部；如果容量已满，删除尾部节点（最久未使用）

importjava.util.HashMap;importjava.util.Map;/** * 简单版 LRU Cache 手写实现（不依赖 LinkedHashMap） * 特点： * - get/put 均为 O(1) * - 使用 HashMap + 双向链表 */publicclassLRUCache<K,V>{// 双向链表节点privatestaticclassNode<K,V>{Kkey;Vvalue;Node<K,V>prev;Node<K,V>next;Node(){}Node(Kkey,Vvalue){this.key=key;this.value=value;}}privatefinalintcapacity;privatefinalMap<K,Node<K,V>>map;// 虚拟头尾节点，方便处理边界privatefinalNode<K,V>head;privatefinalNode<K,V>tail;publicLRUCache(intcapacity){if(capacity<=0){thrownewIllegalArgumentException("capacity must be > 0");}this.capacity=capacity;this.map=newHashMap<>();this.head=newNode<>();this.tail=newNode<>();head.next=tail;tail.prev=head;}/** * 获取缓存中的值，如果不存在返回 null。 * 同时将访问的节点移动到链表头部（最近使用） */publicVget(Kkey){Node<K,V>node=map.get(key);if(node==null){returnnull;}moveToHead(node);returnnode.value;}/** * 放入 key-value。 * 如果 key 已存在：更新 value，并移动到头部； * 如果 key 不存在：新建节点，插入头部，如果超出容量，删除尾部节点。 */publicvoidput(Kkey,Vvalue){Node<K,V>node=map.get(key);if(node!=null){// 已存在，更新值并移动到头部node.value=value;moveToHead(node);}else{// 新节点Node<K,V>newNode=newNode<>(key,value);map.put(key,newNode);addToHead(newNode);// 超出容量，移除尾部节点if(map.size()>capacity){Node<K,V>tailNode=removeTail();if(tailNode!=null){map.remove(tailNode.key);}}}}// 将节点移动到双向链表头部privatevoidmoveToHead(Node<K,V>node){removeNode(node);addToHead(node);}// 在链表头部插入节点（head 之后）privatevoidaddToHead(Node<K,V>node){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}// 从链表中移除节点privatevoidremoveNode(Node<K,V>node){Node<K,V>prev=node.prev;Node<K,V>next=node.next;prev.next=next;next.prev=prev;}// 移除尾部真实数据节点（tail 前一个），并返回之privateNode<K,V>removeTail(){Node<K,V>node=tail.prev;if(node==head){returnnull;}removeNode(node);returnnode;}// 简单测试publicstaticvoidmain(String[]args){LRUCache<Integer,String>cache=newLRUCache<>(2);cache.put(1,"one");cache.put(2,"two");System.out.println(cache.get(1));// one，1 变为最近使用cache.put(3,"three");// 淘汰 key=2System.out.println(cache.get(2));// nullcache.put(4,"four");// 淘汰 key=1System.out.println(cache.get(1));// nullSystem.out.println(cache.get(3));// threeSystem.out.println(cache.get(4));// four}}

如果你需要：

• 线程安全版本
• 基于LinkedHashMap的简化实现
• 或者带过期时间/统计信息的 LRU

可以告诉我具体需求，我再给对应代码。

根据真实的面经和笔经，我为你整理了一份同花顺后端/大数据工程师岗位的高频面试考题与核心回答思路，以便你更有针对性地准备。

下面将面试考核分为三个主要部分：技术一面、技术二面和笔试。

🎯 技术一面 - 基础与算法

这一轮主要考察你的技术基本功、项目经验和编码能力。

💡 技术二面 - 深度与设计

这一轮问题更深，考察你的理解深度和系统设计能力。

📝 笔试 - 广度与思维

同花顺的笔试通常题量较大，题型多样。

✨ 针对性面试策略

除了准备好具体答案，掌握策略同样关键：

1. 展示金融业务思维：在回答系统设计或大数据优化问题时，尝试联系金融场景（如实时行情、交易风控、用户画像），这是同花顺非常看重的。
2. 体现深度和广度：二面的问题（如HashMap扩容、AQS）需要理解底层原理。主动提及相关机制（如synchronized锁升级、volatile内存屏障），能体现你的深度。
3. 坦诚沟通，积极思考：遇到完全不懂的问题，可以说“这个领域我了解不深，但根据我的理解，我认为…”，并给出一个解决问题的思路，这比生硬回答更好。

希望这份详细的考题与思路清单能帮助你高效备考。

如果你想针对上述某个高频考点（比如“数据倾斜优化”或“订单超时设计”）进行更深入的模拟问答练习，我可以继续为你详细展开。