接触到的一个题目，原题应该是在leetcode。LRU简单按意思来说就是符合最近最少使用的一个队列。我们首先的理解来说，LRU缓存需要几个核心的定义。1. 容量 2. 容器 3. 操作 4. 语义。首先，容量，定义这个LRU队列的长度。而容器是底层采用什么样的数据结构来存储。因为要保证不重复， 首先会想到Hash，而且应该是K-V的形式，Java相关有HashMap。对于操作来说，一个队列，需要有入队和出队，以及初始化的操作，即需要get(), set()等方法。最后一个语义，就是LRU的核心，如何去保证符合最近最少使用。按要求，需要把最近最少使用的放到队尾，最近最新使用的放到队头，引申即需要设置一个头，尾的单独标记，以及操作setHead。注意setHead是整个的难点，要详尽的考虑当前节点是否头节点，是否中间节点，是否尾节点等各种情况，操作实际内容需要是双向链表的形式，设计的核心是考虑各种异常和特殊情况。最初的版本无法通过，目前修改到Accepted，依然有些优化空间，注释有简单思路的介绍，同时代码中包括了默认的几个Case。
以下是代码：
import java.util.HashMap;
/**
Created by igoso on 18-1-8.
case 1
["LRUCache","put","put","get","put","put","get"]
[[2],[2,1],[2,2],[2],[1,1],[4,1],[2]]
-- [null,null,null,2,null,null,-1]
case 2
["LRUCache","put","put","put","put","get","get","get","get","put","get","get","get","get","get"]
[[3],[1,1],[2,2],[3,3],[4,4],[4],[3],[2],[1],[5,5],[1],[2],[3],[4],[5]]
-- [null,null,null,null,null,4,3,2,-1,null,-1,2,3,-1,5]
*/
public class LRUCacheDemo {
public static void main(String[] args) {
LRUCache cache = new LRUCache(2 /* capacity */);
/** default case **/
// cache.put(1,1);
// cache.put(2,2);
// cache.put(3,3);
// cache.put(4,4);
// cache.get(4);
// cache.get(3);
// cache.get(2);
// cache.get(1);
// cache.put(5, 5);
// cache.get(1);
// cache.get(2);
// cache.get(3);
// cache.get(4);
// cache.get(5);
/** case 1**/
// cache.put(1, 1);
// cache.put(2, 2);
// cache.get(1); // returns 1
// cache.put(3, 3); // evicts key 2
// cache.get(2); // returns -1 (not found)
// cache.put(4, 4); // evicts key 1
// cache.get(1); // returns -1 (not found)
// cache.get(3); // returns 3
// cache.get(4); // returns 4
/** case 2 **/
cache.put(2,1);
cache.put(2,2);
cache.get(2);
cache.put(1,1);
cache.put(4,1);
cache.get(2);
}
}
class LRUCache {
private class Node {
int key;
int value;
Node pre;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "[" + key + "," + value + "]";
}
}
private int capacity;
private HashMap<Integer, Node> map = new HashMap<>();
private Node head = null;
private Node tail = null;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (map.containsKey(key)) {
Node n = map.get(key);
setHead(n,false);
return n.value;
}
return -1;
}
private void remove(Node node) {
//是头节点
if (node.pre != null) {
node.pre.next = node.next;
} else {
head = node.next;
}
//是否尾节点
if (node.next != null) {
node.next.pre = node.pre;
} else {
tail = node.pre;
}
//貌似与上面条件重复,可以删除
if (node == tail) {
tail = tail.pre;
}
}
private void setHead(Node n, boolean isNew) {
//如果是头，直接返回
if (head == n) {
return;
}
//是否插入,注意在put的时候有remove 也算新节点
if (isNew) {
n.next = head;
n.pre = null;
if (head != null) {
head.pre = n;
}
head = n;
if (tail == null) {
tail = head;
}
if (tail == head && head.next != null) {
tail = head.next;
tail.next = null;
}
return;
}
//非新插入头，只修改头指针
//是尾节点
if (n.next == null) {
tail = n.pre;
tail.next = null;
head.pre = n;//记得给原先头节点的前驱赋当前值
n.next = head;
//设置新的头节点
head = n;
head.pre = null;
}else {
//非尾节点
head.pre = n;//记得给原先头节点的前驱赋当前值
n.next.pre = n.pre;
n.pre.next = n.next;
n.next = head;
head = n;
head.pre = null;
}
}
public void put(int key, int value) {
//已经存在
//先删除，再设置为头
if (map.containsKey(key)) {
Node old = map.get(key);
old.value = value;
remove(old);
setHead(old,true);
} else {
//不存在新建，包括设置新头和删除溢出节点
Node created = new Node(key, value);
if (map.size() >= capacity) {
map.remove(tail.key);
remove(tail);
setHead(created,true);
} else {
setHead(created,true);
}
map.put(key, created);
}
}
@Override
public String toString() {
return this.map.toString();
}
}
以上，相对来说还是比较复杂的，以下是简单的图解，核心是对头节点和尾节点的操作和标记，每个都有双向的指针。注意头指针和尾指针的特性，头的前驱为空，尾的后驱为空，以及只有一个元素，或者两个元素的情况。
更简单的解法看这篇文章：https://www.jianshu.com/p/c7adab253186
lru.png
