原题描述
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
解题思路
题目要求算法能根据键值对随机存取缓存，我们很容易就能想到使用哈希表来实现。但是题目还要求缓存是LRU（Least Recently Used）形式的，即在更新缓存时采用最近最少使用原则，这就需要数据结构能记录缓存的命中情况：每次有缓存被命中都需要将其标记为最近使用，当缓存大小超出容量时，需要删除最久未被使用的缓存。
在Java中，正好有这么一种哈希表，可以记录数据的访问顺序，它就是LinkedHashMap。借助于LinkedHashMap，我们可以很容易地实现LRU Cache。实现代码如下：
import java.util.LinkedHashMap;
public class LRUCache extends LinkedHashMap<Integer, Integer> {
private int capacity;
public LRUCache1(int capacity) {
super(capacity+1, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(
java.util.Map.Entry<Integer, Integer> eldest) {
return size() > capacity; //当缓存大小超出容量时，移除最久未被使用的缓存
}
public int get(int key) {
return super.get(key) != null ? super.get(key) : -1;
}
public void set(int key, int value) {
super.put(key, value);
}
public int size() {
return super.size();
}
}
LinkedHashMap的方案虽然简便，但是它毕竟不是基本的数据结构，从算法设计的角度来说，我们还是需要一个使用基本数据结构来实现的方案。参考LinkedHashMap类的内部实现原理，我们可以通过哈希表+双链表的组合来实现LRU Cache。由哈希表来实现根据键值对（值为双链表结点）随机存取，由双链表来维护缓存的命中情况：最近使用的缓存在链表头结点，最久未使用的缓存在链表尾结点，当缓存被命中时，将其移至链表头结点，当缓存大小超出容量时，直接删除链表尾结点。代码实现如下：
public class LRUCache {
class CacheNode {
public int key;
public int value;
public CacheNode pre;
public CacheNode next;
public CacheNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private int capacity;
private int size = 0;
private HashMap<Integer, CacheNode> map = new HashMap<>();
private CacheNode head;
private CacheNode tail;
public LRUCache(int capacity) {
this.capacity = capacity;
head = null;
tail = null;
}
private void removeNode(CacheNode node) {
CacheNode pre = node.pre;
CacheNode next = node.next;
if (pre != null) {
pre.next = next;
} else {
head = next;
}
if (next != null) {
next.pre = pre;
} else {
tail = pre;
}
}
private void setHead(CacheNode node) {
node.next = head;
node.pre = null;
if (head != null) {
head.pre = node;
}
head = node;
if (tail == null) {
tail = node;
}
}
public void set(int key, int value) {
if (map.containsKey(key)) {
CacheNode oldNode = map.get(key);
oldNode.value = value;
removeNode(oldNode);
setHead(oldNode);
} else {
CacheNode newNode = new CacheNode(key, value);
if (size < capacity) {
size++;
} else {
map.remove(tail.key);
tail = tail.pre;
if (tail != null) {
tail.next = null;
}
}
setHead(newNode);
map.put(key, newNode);
}
}
public int get(int key) {
if (map.containsKey(key)) {
CacheNode lastest = map.get(key);
removeNode(lastest);
setHead(lastest);
return lastest.value;
} else {
return -1;
}
}
}
