最近最少使用缓存

        题目：请设计实现一个最近最少使用缓存，要求如下两个操作的时间复杂度都是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; //初始化keyint 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);//如果这个节点不存在则返回-1if (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);//双向链表容量+1size++;//如果容量超过最大容量，则需将双向链表尾部的节点移除if (size > capacity) {//在链表中删去尾部节点，同时哈希表中也移除掉这个节点，并且双向链表容量-1DLinkedNode tail = removetail();map.remove(tail.key);size--;}} else {//如果这个节点存在，则直接修改valuenode.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);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity; }
}