阿里、腾讯校招都爱问的 LRU 缓存，你能手写出来吗？（附详细代码及GitHub项目）
2026-05-13 18:25:49
LRU 缓存机制可以通过哈希表 + 双向链表实现，以下是 Java 代码实现：
import java.util.HashMap;import java.util.Map;class LRUCache { class Node { int key, value; Node prev, next; Node(int k, int v) { key = k; value = v; } } private int capacity; private Map<Integer, Node> map = new HashMap<>(); private Node head = new Node(0, 0), 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); remove(node); insert(node); return node.value; } public void put(int key, int value) { if (map.containsKey(key)) remove(map.get(key)); if (map.size() == capacity) remove(tail.prev); insert(new Node(key, value)); } private void insert(Node node) { map.put(node.key, node); node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; } private void remove(Node node) { map.remove(node.key); node.prev.next = node.next; node.next.prev = node.prev; }}核心实现思路数据结构选择
哈希表（HashMap）：存储键值对，实现 O(1) 时间复杂度的查找。
双向链表（Doubly Linked List）：维护数据访问顺序，最近访问的节点放在头部，最久未访问的节点靠近尾部。
关键操作
get(key)：
若键不存在，返回 -1。
若键存在，将对应节点移动到链表头部（表示最近使用），并返回值。
put(key, value)：
若键已存在，更新值并移动节点到头部。
若缓存已满，删除链表尾部的节点（最久未使用），再插入新节点到头部。
辅助方法
insert(node)：将节点插入链表头部，并更新哈希表。
remove(node)：从链表中删除节点，并从哈希表中移除对应键值对。
口头说明 LRU 机制
LRU（Least Recently Used）是一种缓存淘汰策略，优先淘汰最近最少使用的数据。
适用场景：内存受限时管理缓存数据，如数据库缓存、浏览器缓存等。
时间复杂度要求
需实现 O(1) 时间复杂度的 get 和 put 操作，因此选择哈希表 + 双向链表。
代码结构
先定义双向链表节点类 Node。
在 LRUCache 类中初始化哈希表和双向链表的头尾节点。
实现 get 和 put 方法，并调用辅助方法 insert 和 remove。
重点提示
先讲思路，再写代码，避免直接开敲导致逻辑混乱。
强调双向链表的维护逻辑（头部插入、尾部删除）。
如果需要更多校招面试题和系统设计题库，可以参考以下 GitHub 项目：
- 项目名称：Campus_recruitment_interview_questions
- 内容涵盖：
算法精选题目详解（如 LRU、LFU 等）。
高频知识点（Redis、操作系统、数据库等）。
腾讯/字节/阿里等大厂真实面经总结。
- 项目地址：[GitHub 链接]
- LRU 核心：哈希表 + 双向链表实现 O(1) 操作。
- 面试技巧：先讲思路，再写代码，重点突出数据结构选择的原因。
- 扩展学习：通过 GitHub 项目系统复习高频题和知识点。
希望这份解答能帮助你高效应对校招面试中的 LRU 问题！
热门标签
