设置一个带超时时间的LRU缓存

1.思路需要在LRU最近最少使用的基础上继续实现。1在定义双向链表节点Node的时候给Node增加过期时间戳字段expireTime表示该节点的过期时间是多少和检查节点是否过期的成员方法实例方法boolean isExpired()如果当前时间的毫秒数System.currentTimeMillis() expireTime那么就return true表示该节点已经过期。后续更新附代码class TimeoutLRUCache { // 双向链表节点增加过期时间戳字段 private static class Node { int key, value; long expireTime; // 过期时间戳毫秒 Node prev, next; Node(int key, int value, long expireTime) { this.key key; this.value value; this.expireTime expireTime; this.prev null; this.next null; } // 检查节点是否已过期 boolean isExpired() { return System.currentTimeMillis() expireTime; } } private final int capacity; private final long defaultTtl; // 默认过期时间毫秒 private final Node sentinel new Node(0, 0, Long.MAX_VALUE); private final MapInteger, Node keyToNode new HashMap(); // 构造函数只指定容量使用默认过期时间5分钟 public TimeoutLRUCache(int capacity) { this(capacity, 300000); // 默认5分钟 } // 构造函数指定容量和默认过期时间毫秒 public TimeoutLRUCache(int capacity, long defaultTtl) { this.capacity capacity; this.defaultTtl defaultTtl; sentinel.prev sentinel; sentinel.next sentinel; } // 获取值如果已过期则返回 -1 public int get(int key) { Node node getNode(key); if (node null || node.isExpired()) { if (node ! null) { // 过期节点从缓存中移除 remove(node); keyToNode.remove(key); } return -1; } return node.value; } // 放入缓存使用默认过期时间 public void put(int key, int value) { put(key, value, defaultTtl); } // 放入缓存指定过期时间毫秒 public void put(int key, int value, long ttlMillis) { Node node getNode(key); if (node ! null) { // 更新存在的节点 node.value value; node.expireTime System.currentTimeMillis() ttlMillis; return; } // 创建新节点 long expireTime System.currentTimeMillis() ttlMillis; node new Node(key, value, expireTime); keyToNode.put(key, node); pushFront(node); // 清理过期节点 容量控制 cleanExpiredNodes(); if (keyToNode.size() capacity) { Node backNode sentinel.prev; // 从后往前清理优先清理过期节点 while (backNode ! sentinel keyToNode.size() capacity) { if (backNode.isExpired()) { Node toRemove backNode; backNode backNode.prev; keyToNode.remove(toRemove.key); remove(toRemove); } else if (keyToNode.size() capacity) { // 容量超限移除最久未使用的节点 keyToNode.remove(backNode.key); remove(backNode); backNode sentinel.prev; } } } } // 获取节点并移到头部 private Node getNode(int key) { if (!keyToNode.containsKey(key)) { return null; } Node node keyToNode.get(key); // 如果节点已过期返回null让调用方处理 if (node.isExpired()) { return null; } remove(node); pushFront(node); return node; } // 清理所有过期节点 private void cleanExpiredNodes() { Node current sentinel.prev; while (current ! sentinel) { Node next current.prev; if (current.isExpired()) { keyToNode.remove(current.key); remove(current); } current next; } } // 从链表中移除节点 private void remove(Node x) { x.prev.next x.next; x.next.prev x.prev; } // 将节点插入链表头部 private void pushFront(Node x) { x.prev sentinel; x.next sentinel.next; x.prev.next x; x.next.prev x; } // 获取当前缓存大小包含未过期节点 public int size() { cleanExpiredNodes(); return keyToNode.size(); } // 检查缓存是否包含某个key未过期 public boolean containsKey(int key) { Node node keyToNode.get(key); return node ! null !node.isExpired(); } }ACM模式import java.util.*; class TimeoutLRUCache { // 双向链表节点增加过期时间戳字段 private static class Node { int key, value; long expireTime; // 过期时间戳毫秒 Node prev, next; Node(int key, int value, long expireTime) { this.key key; this.value value; this.expireTime expireTime; this.prev null; this.next null; } // 检查节点是否已过期 boolean isExpired() { return System.currentTimeMillis() expireTime; } } private final int capacity; private final long defaultTtl; // 默认过期时间毫秒 private final Node sentinel new Node(0, 0, Long.MAX_VALUE); private final MapInteger, Node keyToNode new HashMap(); // 构造函数只指定容量使用默认过期时间5分钟 public TimeoutLRUCache(int capacity) { this(capacity, 300000); // 默认5分钟 } // 构造函数指定容量和默认过期时间毫秒 public TimeoutLRUCache(int capacity, long defaultTtl) { this.capacity capacity; this.defaultTtl defaultTtl; sentinel.prev sentinel; sentinel.next sentinel; } // 获取值如果已过期则返回 -1 public int get(int key) { Node node getNode(key); if (node null || node.isExpired()) { if (node ! null) { // 过期节点从缓存中移除 remove(node); keyToNode.remove(key); } return -1; } return node.value; } // 放入缓存使用默认过期时间 public void put(int key, int value) { put(key, value, defaultTtl); } // 放入缓存指定过期时间毫秒 public void put(int key, int value, long ttlMillis) { Node node getNode(key); if (node ! null) { // 更新存在的节点 node.value value; node.expireTime System.currentTimeMillis() ttlMillis; return; } // 创建新节点 long expireTime System.currentTimeMillis() ttlMillis; node new Node(key, value, expireTime); keyToNode.put(key, node); pushFront(node); // 清理过期节点 容量控制 cleanExpiredNodes(); if (keyToNode.size() capacity) { Node backNode sentinel.prev; // 从后往前清理优先清理过期节点 while (backNode ! sentinel keyToNode.size() capacity) { if (backNode.isExpired()) { Node toRemove backNode; backNode backNode.prev; keyToNode.remove(toRemove.key); remove(toRemove); } else if (keyToNode.size() capacity) { // 容量超限移除最久未使用的节点 keyToNode.remove(backNode.key); remove(backNode); backNode sentinel.prev; } } } } // 获取节点并移到头部 private Node getNode(int key) { if (!keyToNode.containsKey(key)) { return null; } Node node keyToNode.get(key); // 如果节点已过期返回null让调用方处理 if (node.isExpired()) { return null; } remove(node); pushFront(node); return node; } // 清理所有过期节点 private void cleanExpiredNodes() { Node current sentinel.prev; while (current ! sentinel) { Node next current.prev; if (current.isExpired()) { keyToNode.remove(current.key); remove(current); } current next; } } // 从链表中移除节点 private void remove(Node x) { x.prev.next x.next; x.next.prev x.prev; } // 将节点插入链表头部 private void pushFront(Node x) { x.prev sentinel; x.next sentinel.next; x.prev.next x; x.next.prev x; } // 获取当前缓存大小包含未过期节点 public int size() { cleanExpiredNodes(); return keyToNode.size(); } // 检查缓存是否包含某个key未过期 public boolean containsKey(int key) { Node node keyToNode.get(key); return node ! null !node.isExpired(); } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n scanner.nextInt(); TimeoutLRUCache cache null; ListString output new ArrayList(); for (int i 0; i n; i) { String op scanner.next(); switch (op) { case TimeoutLRUCache: int capacity scanner.nextInt(); cache new TimeoutLRUCache(capacity); output.add(null); break; case put: int key scanner.nextInt(); int value scanner.nextInt(); // 可选读取过期时间如果没有则使用默认值 long ttl -1; if (scanner.hasNextInt()) { ttl scanner.nextInt(); } if (ttl 0) { cache.put(key, value, ttl); } else { cache.put(key, value); } output.add(null); break; case putWithTtl: int k scanner.nextInt(); int v scanner.nextInt(); long ttlMillis scanner.nextLong(); cache.put(k, v, ttlMillis); output.add(null); break; case get: int getKey scanner.nextInt(); int result cache.get(getKey); output.add(String.valueOf(result)); break; case size: output.add(String.valueOf(cache.size())); break; case contains: int checkKey scanner.nextInt(); output.add(String.valueOf(cache.containsKey(checkKey))); break; default: output.add(unknown); } } // 输出结果 for (int i 0; i output.size(); i) { System.out.print(output.get(i)); if (i output.size() - 1) { System.out.print( ); } } scanner.close(); } }