题解 | #java版——设计LRU缓存结构#

方法一在leetcode上是可以通过的，在牛客通过不了，可以学习下。

方法一：利用LinkedHashMap

public class Solution extends LinkedHashMap<Integer, Integer>{
    
    private int capacity;
    
    public Solution(int capacity) {
        // accessOrder默认为false表示按插入顺序排序，为true表示按访问顺序排序
        // LRU自然是按访问顺序，所以让accessOrder=true
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void set(int key, int value) {
        super.put(key, value);
    }
    
    // removeEldestEntry字面意思移除年龄最大元素，默认返回false表示不移除
    // 我们重写这个方法，加一个判断条件，当 size > capacit 时移除
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){
        return this.size() > capacity;
    }
}

关于 LinkedHashMap 具体使用大家可以阅读相应的源码

方法二：双链表+HashMap

public class Solution {
    class DLinkedNode<K, V> {
        private K key;
        private V value;
        DLinkedNode pre;
        DLinkedNode next;
        
        public DLinkedNode(){};
        
        public DLinkedNode(K key, V value){
            this.key = key;
            this.value = value;
        }
    }
    
    private int capacity;
    private Map<Integer, DLinkedNode> map = new HashMap<>();
    private DLinkedNode head;
    private DLinkedNode tail;
    private int size;
    
    public Solution(int capacity) {
         // write code here
        this.capacity = capacity;
        this.size = 0;
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        this.head.next = this.tail;
        this.tail.pre = this.head;
    }

    public int get(int key) {
         // write code here
        DLinkedNode<Integer, Integer> node = map.get(key);
        if(node == null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void set(int key, int value) {
         // write code here
        DLinkedNode<Integer, Integer> node = map.get(key);
        if(node == null){
            DLinkedNode<Integer, Integer> newNode = new DLinkedNode<>(key,value);
            map.put(key, newNode);
            addToHead(newNode);
            size++;
            if(size > this.capacity){
                DLinkedNode tail = removeTail();
                map.remove(tail.key);
                size--;
            }
        }else{
            node.value = value;
            moveToHead(node);
        }
    }
    
    // 插入
    public void addToHead(DLinkedNode node){
        node.next = this.head.next;
        node.next.pre = node;
        node.pre = this.head;
        this.head.next = node;
        
    }
        
    // 删除
    public DLinkedNode removeTail(){
        DLinkedNode p = this.tail.pre;
        this.tail.pre.pre.next = this.tail;
        this.tail.pre = this.tail.pre.pre;
        return p;
    }
    
    // 将该结点移到头部
    // 因为map中存放的是结点的索引（地址），所以我们不需要遍历链表去定位到这个node，可以直接用这个地址定位到这个node
    public void moveToHead(DLinkedNode node){
        // 把node从原位置摘除
        node.next.pre = node.pre;
        node.pre.next = node.next;
        // 将node移到表头
        node.next = head.next;
        node.next.pre = node;
        node.pre = head;
        head.next = node;
    }
}