算法通关村-----LRU的设计与实现

LRU 缓存

问题描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存。int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

问题分析

cache的优点是速度快，缺点是价格高，因此cache的容量是在平衡速度与价格基础上设计的。当cache已满，在添加元素时，无法添加，我们需要先移除，在添加，LRU是一种移除策略，最近最少使用，即移除最长时间未访问的元素。题目中要求get和put在常数时间内完成，get操作是先定位，然后返回，定位的常数时间，我们直接使用Hash即可，put操作是先get，看能不能获取到，如果存在，我们需要改变值，不存在添加值，get操作使用Hash，找到后，添加或更新是可以直接操作的。那么我们如何确定最近最少使用呢，假设我们有一个线性空间（很明显不适合用树或图，所以假设线性空间）,我们可以将元素按照最近最多使用到最近最少使用的顺序存放，即如果一个元素被访问了，立即放在最前面，如此，最后面就是就近最少使用。另外，当缓存满了，我们需要从最后方移除元素。数组无法在线性时间移除，单链表、栈无法同时操作前后端进行添加或移除，队列只能从队尾入，队头出，无法实现世界添加到队头，因此，我们只能使用双向链表或者双端队列了。最终我们的结论是，使用Hash在常数时间内获取，使用双向链表实现最近最少使用的添加和删除。

代码实现

class LRUCache {class DoubleLinkedNode{int key;int value;DoubleLinkedNode pre;DoubleLinkedNode next;public DoubleLinkedNode(){}public DoubleLinkedNode(int key, int value){this.key = key;this.value = value;}}Map<Integer,DoubleLinkedNode> map;DoubleLinkedNode head;DoubleLinkedNode tail;int size;int capacity;public LRUCache(int capacity) {map = new HashMap<>();head = new DoubleLinkedNode();tail = new DoubleLinkedNode();head.next = tail;tail.pre = head;size = 0;this.capacity = capacity;}public int get(int key) {if(map.containsKey(key)){DoubleLinkedNode node = map.get(key);remove(node);addToHead(node);return node.value;}return -1;}public void put(int key, int value) {if(map.containsKey(key)){DoubleLinkedNode node = map.get(key);node.value = value;remove(node);addToHead(node);}else{DoubleLinkedNode node = new DoubleLinkedNode(key, value);map.put(key, node);addToHead(node);size++;if(size>capacity){int removeKey = removeFromTail();map.remove(removeKey);size--;}}}public void remove(DoubleLinkedNode node) {node.pre.next = node.next;node.next.pre = node.pre;}public void addToHead(DoubleLinkedNode node) {node.next = head.next;head.next.pre = node;node.pre = head;head.next = node;}public int removeFromTail() {DoubleLinkedNode pre = tail.pre;remove(tail.pre);return pre.key;}
}