题目：请设计实现一个最近最少使用缓存，要求如下两个操作的时间复杂度都是O(1)。
- get(key)：如果缓存中存在键key，则返回它对应的值；否则返回-1.
- put(key,value)：如果缓存中之前包含键key，则它的值设为value；否则添加键key及对应的value。在添加一个键时，如果缓存容量已满，则在添加新键之前删除最近最少使用的键（缓存中最长时间没有被使用过的元素）。
Hashmap的get和put方法时间复杂度是O(1)，但其不能找出最近最少使用的键。而要想表示一种顺序关系，不难想到可以使用链表，将链尾视为最近最少使用的元素，每次访问一个元素，将该元素移到链头。
而将元素移到链头之前，应先将节点从原来位置删掉，若仅仅知道待删除节点，是不能知道前驱节点的，故单链表的增删操作复杂度为O (n)。所以我们需使用双向链表。
用哈希表的键保存key，哈希表的值保存双向链表的节点。
class LRUCache {
class DLinkedNode {
int key; //初始化key
int value; //初始化value
//初始化双向链表前后联系指针
DLinkedNode prev;
DLinkedNode next;
//初始化双向链表
public DLinkedNode() {
}
public DLinkedNode(int _key, int _value) {
key = _key;
value = _value;
}
}
//创建哈希表
HashMap<Integer, DLinkedNode> map = new HashMap<>();
//链表当前大小
int size;
//链表当前容量
int capacity;
//链表头部尾部节点
DLinkedNode head;
DLinkedNode tail;
public LRUCache(int capacity) {
//大小初始化
this.size = 0;
//容量初始化
this.capacity = capacity;
//使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
//在哈希表中找到key所对应的节点
DLinkedNode node = map.get(key);
//如果这个节点不存在则返回-1
if (node == null) {
return -1;
}
//将这个节点移到头部，再返回这个节点所对应的值
movetohead(node);
return node.value;
}
public void put(int key, int value) {
//在哈希表中找到key所对应的节点
DLinkedNode node = map.get(key);
//如果这个节点不存在，则创建一个新的节点进行添加
if (node == null) {
//创建新节点
DLinkedNode newnode = new DLinkedNode(key, value);
//将节点加入哈希表
map.put(key, newnode);
//将这个节点添加到双向链表头部
addtohead(newnode);
//双向链表容量+1
size++;
//如果容量超过最大容量，则需将双向链表尾部的节点移除
if (size > capacity) {
//在链表中删去尾部节点，同时哈希表中也移除掉这个节点，并且双向链表容量-1
DLinkedNode tail = removetail();
map.remove(tail.key);
size--;
}
} else {
//如果这个节点存在，则直接修改value
node.value = value;
//将这个节点在双向链表中移到头部
movetohead(node);
}
}
//在头部添加节点的方法
public void addtohead(DLinkedNode node) {
//head为虚拟头结点，由于是双向链表，添加一个节点需要建立四个连接关系
node.next = head.next;
head.next.prev = node;
node.prev = head;
head.next = node;
}
//移除节点方法
public void removenode(DLinkedNode node) {
//跳过这个节点重新建立双向连接关系
node.prev.next = node.next;
node.next.prev = node.prev;
}
//将节点移到头部的方法
public void movetohead(DLinkedNode node) {
removenode(node);
addtohead(node);
}
//将节点从尾部移除的方法
public DLinkedNode removetail() {
//尾部的待删除节点即为虚拟尾结点的前一个节点
DLinkedNode res = tail.prev;
//将这个节点删除
removenode(res);
return res;
}
}当然Java中有已经封装好的数据结构LinkedHashmap可以解答，不过不建议。
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}