146. LRU 缓存(中等)

需要一个哈希表和一个双向链表完成,java中已经有了实现LinkedHashMap。其中

class LRUCache extends LinkedHashMap<Integer, Integer>{
   private int capacity;
    public LRUCache(int capacity) {
        //初始容量,装载因子,键值对保持顺序true表示最近最少使用次序,false表示插入顺序
        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);
    }

    //通过覆盖这个方法,加入一定的条件,满足条件返回true。当put进新的值方法返回true时,便移除该map中最老的键和值。
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }

}

手动实现该功能

双向链表,表头代表刚访问的数据,表尾代表很久没有访问的数据。

class LRUCache{
    class DlinkedNode{
        private int key;
        private int value;

        private DlinkedNode prev;
        private DlinkedNode next;

        public DlinkedNode(){};
        public DlinkedNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer,DlinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    //记录双向链表的伪头部和伪尾部节点
    private DlinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        //创建伪头部和伪尾部节点
        this.head = new DlinkedNode();
        this.tail = new DlinkedNode();

        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DlinkedNode node = cache.get(key);
        if(node == null){
            return -1;
        }
        // 如果 key 存在,先通过哈希表定位,再移到头部
        moveToHead(node);
        return node.value;
    }

    private void addToHead(DlinkedNode node) {

        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
        

    private void removeNode(DlinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
        
    private void moveToHead(DlinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    public void put(int key, int value) {
        DlinkedNode node = cache.get(key);
        if(node == null){
            //如果key不存在 创建一个新的节点
            DlinkedNode newNode = new DlinkedNode(key,value);
            //放进hash表
            cache.put(key,newNode);
            //添加至双向链表的头部
            addToHead(newNode);
            ++size; //当前数量加1
            if(size > capacity){
                DlinkedNode last = tail.prev;
                removeNode(last);
                cache.remove(last.key);
                --size;
            }

        }else{
            // 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

}