【面试题】手撕缓存LRU
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
- put(key, value)：将记录(key, value)插入该结构
- get(key)：返回key对应的value值
对于put(key, value)来说，我们需要考虑两部分：
- 如果缓存中存在，那么直接将缓存中对应的元素移动到缓存头部
- 如果缓存中不存在，那么把元素添加到缓存头部，如果此时缓存的大小超出了预先设定的值，那么则将缓存尾部的元素删除
对于get(key)来说，我们还是需要考虑两部分：
- 如果缓存中存在，那么返回该值，并且将这个值移动到缓存头部
- 如果缓存中不存在，那么返回-1
综上所述：对于一个LRU缓存来说，主要包含以下三种操作。
- 查找一个元素。
- 在缓存末尾删除一个元素。
- 在缓存头部添加一个元素。
所以，我们最容易想到的实现方式就是通过双端链表+哈希表来实现这个问题，最终实现代码如下：
class LRUCache {private HashMap<Integer,ListNode> cache;private int capacity;private ListNode head,tail;class ListNode{int key;int value;ListNode prev;ListNode next;public ListNode(){}public ListNode(int key,int value){this.key=key;this.value=value;}}public LRUCache(int capacity) {this.capacity =capacity;cache = new HashMap<>();head = new ListNode();tail = new ListNode();head.next = tail;tail.prev = head;}public int get(int key) {//首先判断一下是否存在keyListNode node = cache.get(key);if(node==null){return -1;}//如果存在，把缓存移动到头部，返回valuemoveToHead(node);return node.value;}public void put(int key, int value) {//判断是否存在ListNode node = cache.get(key);//如果不存在，添加到头部,如果容量到达上限，则删除队尾的元素,如果存在直接移动到头部if(node==null){ListNode newNode = new ListNode(key,value);cache.put(key,newNode);addNode(newNode);if(cache.size()>capacity){ListNode last = popTail();cache.remove(last.key);}}else{node.value=value;moveToHead(node);}}public void addNode(ListNode node){node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}public void removeNode(ListNode node){ListNode prevNode = node.prev;ListNode NextNode = node.next;prevNode.next = NextNode;NextNode.prev = prevNode;}public void moveToHead(ListNode node){removeNode(node);addNode(node);}public ListNode popTail(){ListNode lastNode = tail.prev;removeNode(lastNode);return lastNode;}
}