题目链接

LRU缓存机制

题目描述

注意点

• 当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间

解答思路

• LRU缓存机制的相关解释
• 需要根据键来取得值，所以考虑用map来存储数据
• 使用一个双链表来存储数据值的位置，方便后续删除结点

代码

class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int key, int value) {this.key = key; this.value = value;}
    }

    //用于存储键值对
    Map<Integer,DLinkedNode> map = new HashMap<>();
    //空间大小
    int capacity = 0;
    int size = 0;
    //虚拟头结点和尾结点，方便后续删除和添加结点
    DLinkedNode head;
    DLinkedNode tail;

    //初始化
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if(map.get(key) == null){
            return -1;
        }else{
            if(map.get(key) != head.next){
                //能找到该结点，则需要将该结点放到头部
                moveToHead(map.get(key));
            }
            return map.get(key).value;
        }
    }
    
    public void put(int key, int value) {
        //将该结点添加进DLinkedNode中
        //map中是否已经有该key值
        if(map.get(key) != null){
            DLinkedNode node = map.get(key);
            node.value = value;
            moveToHead(node);
        }else{
            //判断是否超出容量
            if(size == capacity){
                //超出容量的情况
                //先删除最后一个结点
                delTail();
                DLinkedNode node = new DLinkedNode(key,value);
                map.put(key,node);
                //将该结点设置为头结点
                setHead(node);
            }else{
                //没有超出容量，直接将该结点添加进map中，并设置为头结点
                DLinkedNode node = new DLinkedNode(key,value);
                map.put(key,node);
                setHead(node);
                size++;
            }
        }
        
    }

    //将双链表中的某个结点设置为头结点
    public void moveToHead(DLinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        setHead(node);
    }

    //设置头结点
    public void setHead(DLinkedNode node){
        DLinkedNode nex = head.next;
        head.next = node;
        node.prev = head;
        nex.prev = node;
        node.next = nex;
    }

    //删除尾结点
    public void delTail(){
        //从map中删除
        map.remove(tail.prev.key);
        tail.prev = tail.prev.prev;
        tail.prev.next = tail;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

关键点

• 在创建链表时创建了虚拟的头结点和尾结点，所以下面所说的头结点和尾结点都是指虚拟头结点的下一个结点和虚拟尾结点的上一个结点，可以使双向链表中的每一个结点的移动方式都相同而不需要判断是否有前结点和后结点，大大降低空指针异常发生的概率
• 利用map存储数据，可以通过key值获取value值
• 通过双链表存储数据，可以存储各个结点的位置
• 每次对数据进行操作后，需要将该数据移动至头结点
• 每次添加前，需要先判断该数据的键在map中是否已经存在，如果存在则只需要改变原双链表中键所对应的值即可，同时也要将该数据移动至头结点
• 添加时，如果容量已满，同时在map中找不到新数据的键，则需要先删除尾结点的数据，删除尾结点数据的同时还要将尾结点的数据从map中移除，然后再将新的数据添加至头结点中
• 添加至头结点和移动至头结点操作并不完全相同，区别在于移动至头结点还多了一步，即改变该结点的前后结点的索引