[ 笔记列表 ]
所属分类:其它
浏览:541
内容:
参考: https://baijiahao.baidu.com/s?id=1767380323139541543 代码: // LRU缓存 public class LRUCache { public static void main(String[] args) { LRUCache lruCache = new LRUCache(5); lruCache.put(1, 1); lruCache.put(2, 2); lruCache.put(3, 3); lruCache.put(4, 4); lruCache.put(5, 5); lruCache.put(6, 6); lruCache.put(7, 7); int i = lruCache.getValue(8); System.out.println("i= " + i); int i1 = lruCache.getValue(3); System.out.println("i1= " + i1); } Node[] table; // 使用数组存储缓存数据,数组下标作为key,进行直接定位。 int size = 0, count = 0; Node head, tail; public LRUCache(int size) { this.size = size; table = new Node[1000]; head = new Node(-1, -1); // 定义头节点 tail = new Node(-1, -1); // 定义尾节点 head.next = tail; tail.pre = head; } public int getValue(int key) { Node node; if ((node = table[key]) == null) return -1; // 如果不存在,直接返回-1 moveToTail(node); // 将node节点移动到末尾(位置是tail节点的pre节点) return node.value; } public void put(int key, int value) { Node node; if ((node = table[key]) != null) { // 已存在节点,直接修改value值 node.value = value; } else { // 不存在节点,则新建Node if (count < size) { // 没有到达容量上限 count++; } else { // 超出容量上限,则需要删除“最近最少使用”的节点 table[head.next.key] = null; deleteNode(head.next); } node = new Node(key, value); table[key] = node; } moveToTail(node); // 将node节点移动到末尾 } // 删除节点操作 public void deleteNode(Node node) { if (node.pre == null || node.next == null) { return; } node.pre.next = node.next; node.next.pre = node.pre; } // 将节点移动到“末尾”操作(位置是tail节点的pre节点) public void moveToTail(Node node) { if (tail.pre == node) { return; // 如果已经是“末尾”节点,则不操作 } deleteNode(node); // 删除该节点的前后关联,下面会进行重新关联操作 tail.pre.next = node; node.pre = tail.pre; node.next = tail; tail.pre = node; } // 双向链表结构 class Node { public int key, value; public Node pre, next; public Node(int key, int value) { this.key = key; this.value = value; } } }
链接:
|