【面试题】手撕缓存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;
    }
}