【面试题】手撕缓存LRU

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能

• put(key, value)：将记录(key, value)插入该结构
• get(key)：返回key对应的value值

对于put(key, value)来说，我们需要考虑两部分：

1. 如果缓存中存在，那么直接将缓存中对应的元素移动到缓存头部
2. 如果缓存中不存在，那么把元素添加到缓存头部，如果此时缓存的大小超出了预先设定的值，那么则将缓存尾部的元素删除

对于get(key)来说，我们还是需要考虑两部分：

1. 如果缓存中存在，那么返回该值，并且将这个值移动到缓存头部
2. 如果缓存中不存在，那么返回-1

综上所述：对于一个LRU缓存来说，主要包含以下三种操作。

1. 查找一个元素。
2. 在缓存末尾删除一个元素。
3. 在缓存头部添加一个元素。

所以，我们最容易想到的实现方式就是通过双端链表+哈希表来实现这个问题，最终实现代码如下：

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) {         //首先判断一下是否存在key         ListNode node = cache.get(key);         if(node==null){             return -1;         }         //如果存在，把缓存移动到头部，返回value         moveToHead(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;     } }