Java算法lru和带ttl的lru
可以，这个题如果改成外部测试类main函数LRUCache类打印测试结果我先给你整理成一个，尽量保持你原来的写法和思路不变。
·
可以，这个题如果改成 面试一片空白模式，一般要补上：
-
import java.util.*; -
外部测试类
-
main函数 -
LRUCache类 -
打印测试结果
我先给你整理成一个 标准可运行的面试版本，尽量保持你原来的写法和思路不变。
import java.util.*;
public class InterviewSolution {
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // 1
cache.put(3, 3); // 淘汰 key=2
System.out.println(cache.get(2)); // -1
cache.put(4, 4); // 淘汰 key=1
System.out.println(cache.get(1)); // -1
System.out.println(cache.get(3)); // 3
System.out.println(cache.get(4)); // 4
}
static class LRUCache {
private final int capacity;
private final Node dummy = new Node(0, 0); // 哨兵节点
private final Map<Integer, Node> keyToNode = new HashMap<>();
private static class Node {
int key;
int value;
Node prev;
Node next;
public Node(int k, int v) {
key = k;
value = v;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
dummy.prev = dummy;
dummy.next = dummy;
}
public int get(int key) {
Node node = getNode(key); // getNode 会把对应节点移到链表头部
return node != null ? node.value : -1;
}
public void put(int key, int value) {
Node node = getNode(key); // getNode 会把对应节点移到链表头部
if (node != null) {
node.value = value;
return;
}
node = new Node(key, value);
keyToNode.put(key, node);
pushFront(node);
if (keyToNode.size() > capacity) {
Node backNode = dummy.prev;
keyToNode.remove(backNode.key);
remove(backNode);
}
}
// 获取 key 对应的节点，同时把该节点移到链表头部
private Node getNode(int key) {
if (!keyToNode.containsKey(key)) {
return null;
}
Node node = keyToNode.get(key);
remove(node);
pushFront(node);
return node;
}
// 删除一个节点
private void remove(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}
// 头插一个节点
private void pushFront(Node x) {
x.prev = dummy;
x.next = dummy.next;
x.prev.next = x;
x.next.prev = x;
}
}
}
这种写法在面试里是很标准的
结构就是：
public class InterviewSolution {
public static void main(String[] args) {
// 写测试
}
static class LRUCache {
...
}
}
这就是典型的 空白模式。
面试时你最好能顺口讲出这几个点
1. 用了什么数据结构
HashMap + 双向链表
-
HashMap：O(1) 找到节点 -
双向链表：O(1) 删除节点、移动节点到头部、删除尾部节点
2. 为什么有 dummy 哨兵节点
为了统一链表操作，避免判空。
这样删除和插入都更方便，不需要区分：
-
空链表
-
只有一个节点
-
头节点
-
尾节点
3. get(key) 做了什么
-
先通过 map 找节点
-
找到后把节点移到链表头部
-
返回值
-
找不到返回
-1
4. put(key, value) 做了什么
-
如果 key 已存在，更新 value，并移到头部
-
如果不存在，新建节点，插到头部
-
如果超过容量，删除尾节点
这份代码有一个小优化点
你现在 getNode 里写的是：
if (!keyToNode.containsKey(key)) {
return null;
}
Node node = keyToNode.get(key);
面试里可以稍微优化成：
Node node = keyToNode.get(key);
if (node == null) {
return null;
}
这样少查一次 map，更简洁。
优化后：
private Node getNode(int key) {
Node node = keyToNode.get(key);
if (node == null) {
return null;
}
remove(node);
pushFront(node);
return node;
}
不过你原来的写法也没问题。
面试里更推荐的版本
我给你一个 稍微更像面试高分答案 的版本，只做一点点微调：
import java.util.*;
public class InterviewSolution {
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // 1
cache.put(3, 3);
System.out.println(cache.get(2)); // -1
cache.put(4, 4);
System.out.println(cache.get(1)); // -1
System.out.println(cache.get(3)); // 3
System.out.println(cache.get(4)); // 4
}
static class LRUCache {
private final int capacity;
private final Node dummy;
private final Map<Integer, Node> keyToNode;
static class Node {
int key;
int value;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
this.keyToNode = new HashMap<>();
this.dummy = new Node(0, 0);
dummy.prev = dummy;
dummy.next = dummy;
}
public int get(int key) {
Node node = getNode(key);
return node == null ? -1 : node.value;
}
public void put(int key, int value) {
Node node = getNode(key);
if (node != null) {
node.value = value;
return;
}
node = new Node(key, value);
keyToNode.put(key, node);
pushFront(node);
if (keyToNode.size() > capacity) {
Node lru = dummy.prev;
remove(lru);
keyToNode.remove(lru.key);
}
}
private Node getNode(int key) {
Node node = keyToNode.get(key);
if (node == null) {
return null;
}
remove(node);
pushFront(node);
return node;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void pushFront(Node node) {
node.prev = dummy;
node.next = dummy.next;
dummy.next.prev = node;
dummy.next = node;
}
}
}
你这题面试时最容易被追问的点
面试官很可能会问：
“为什么一定要双向链表？”
因为单链表删除一个节点时，需要先找到前驱节点，不是 O(1)。
双向链表可以直接：
node.prev.next = node.next;
node.next.prev = node.prev;
所以删除是 O(1)。
“为什么 put 里先调用 getNode？”
因为如果 key 已存在，除了更新 value，还要把它变成最近使用，也就是移到头部。
“复杂度是多少？”
-
get：O(1) -
put：O(1)
下一步你可以继续让我帮你把它改成 面试里带 TTL 的版本，我会在这个结构上直接加，不会一下子跳太复杂。
可以。下面我直接在你这个 面试空白模式 的基础上，改成 带 TTL 的 LRUCache。
我先给你一个 适合面试讲清楚、实现也不复杂 的版本：
-
put(key, value, ttlMillis)：每个 key 都可以单独设置过期时间 -
get(key)：如果不存在或已过期，返回-1 -
仍然保留 LRU 语义
-
过期删除采用 惰性删除
-
访问到过期 key 时删掉
-
put时顺手清理一下尾部过期节点
-
这版很适合面试第一步。
面试空白模式：LRU + TTL
import java.util.*;
public class InterviewSolution {
public static void main(String[] args) throws InterruptedException {
LRUCache cache = new LRUCache(2);
cache.put(1, 100, 2000); // 2秒过期
cache.put(2, 200, 5000); // 5秒过期
System.out.println(cache.get(1)); // 100
Thread.sleep(2500);
System.out.println(cache.get(1)); // -1，已过期
System.out.println(cache.get(2)); // 200
cache.put(3, 300, 5000);
System.out.println(cache.get(3)); // 300
cache.put(4, 400, 5000); // 可能触发淘汰
System.out.println(cache.get(2)); // 看最近使用情况
System.out.println(cache.get(3));
System.out.println(cache.get(4));
}
static class LRUCache {
private final int capacity;
private final Node dummy;
private final Map<Integer, Node> keyToNode;
static class Node {
int key;
int value;
long expireAt; // 过期时间戳，毫秒
Node prev;
Node next;
Node(int key, int value, long expireAt) {
this.key = key;
this.value = value;
this.expireAt = expireAt;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
this.keyToNode = new HashMap<>();
this.dummy = new Node(0, 0, 0);
dummy.prev = dummy;
dummy.next = dummy;
}
public int get(int key) {
Node node = getNode(key);
return node == null ? -1 : node.value;
}
public void put(int key, int value, long ttlMillis) {
long now = System.currentTimeMillis();
long expireAt = now + ttlMillis;
Node node = keyToNode.get(key);
// key 已存在
if (node != null) {
// 先判断是否过期
if (isExpired(node, now)) {
remove(node);
keyToNode.remove(key);
} else {
node.value = value;
node.expireAt = expireAt;
remove(node);
pushFront(node);
return;
}
}
// 新建节点
Node newNode = new Node(key, value, expireAt);
keyToNode.put(key, newNode);
pushFront(newNode);
// 顺手清理尾部连续过期节点
cleanExpiredFromBack();
// 超容量则淘汰最久未使用
if (keyToNode.size() > capacity) {
Node lru = dummy.prev;
remove(lru);
keyToNode.remove(lru.key);
}
}
// 获取节点：如果过期就删掉；没过期就移动到头部
private Node getNode(int key) {
Node node = keyToNode.get(key);
if (node == null) {
return null;
}
long now = System.currentTimeMillis();
if (isExpired(node, now)) {
remove(node);
keyToNode.remove(key);
return null;
}
remove(node);
pushFront(node);
return node;
}
private boolean isExpired(Node node, long now) {
return now >= node.expireAt;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void pushFront(Node node) {
node.prev = dummy;
node.next = dummy.next;
dummy.next.prev = node;
dummy.next = node;
}
// 从尾部开始清理连续过期节点
private void cleanExpiredFromBack() {
long now = System.currentTimeMillis();
Node cur = dummy.prev;
while (cur != dummy && isExpired(cur, now)) {
Node prev = cur.prev;
remove(cur);
keyToNode.remove(cur.key);
cur = prev;
}
}
}
}
面试时你要怎么讲
这题如果面试官问，你可以这样说：
核心结构
还是：
HashMap + 双向链表
-
HashMap：O(1) 定位 key -
双向链表：O(1) 删除、移动、淘汰尾节点
TTL 怎么做
每个节点多加一个字段：
long expireAt;
表示这个 key 的过期时间。
get 的逻辑
get(key) 时：
-
先从 map 取节点
-
判断是否过期
-
过期就删除并返回
-1 -
没过期就移动到头部并返回 value
put 的逻辑
put(key, value, ttlMillis) 时：
-
如果 key 已存在
-
先判断是否过期
-
没过期就更新 value 和 expireAt，并移到头部
-
已过期就先删，再按新节点插入
-
-
如果 key 不存在
-
直接新建节点插入头部
-
-
如果超容量
-
删除尾节点
-
这个版本的特点
这是一个 惰性过期 的版本。
意思是：
不是所有过期数据一到时间就立刻删掉，而是：
-
被访问到时删除
-
put时顺便从尾部清一点
这在面试里是完全可以接受的，而且很好解释。
面试官可能会追问的点
1. 为什么不是实时删除所有过期节点？
因为如果每次都全链表扫描，复杂度会变差，最坏会到 O(n)。
2. 这个版本有没有局限？
有。
cleanExpiredFromBack() 只能清理 尾部连续过期节点。
如果中间有过期节点但没访问到，它会暂时留着。
这就是惰性删除的特点。
这题面试时更稳的说法
你可以说：
这是一个 LRU + TTL 的基础实现。
TTL 用惰性删除处理，保证核心逻辑简单，get/put大部分情况下仍然接近 O(1)。
如果要更强的过期管理，可以再引入最小堆，按过期时间清理。
一个小提醒
这里我写的是：
long expireAt = now + ttlMillis;
所以要求：
ttlMillis > 0
如果你想兼容：
-
ttlMillis <= 0立刻过期
也可以改成：
long expireAt = ttlMillis <= 0 ? now : now + ttlMillis;
下一步最自然的就是，我帮你把这版再升级成 面试更强的“LRU + TTL + 最小堆”版，这样就能更像真实缓存系统。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
14
0- 0
已为社区贡献1条内容
所有评论(0)