LRU 缓存

原题链接

使用的方法

LinkedHashMap

解题思路

• LinkedHashMap 是 HashMap 的一个子类，维护了一个双向链表，记录了元素的插入顺序或者访问顺序。
• 通过重写 removeEldestEntry 方法，可以在每次插入新元素时，判断是否需要删除最旧的元素，从而实现 LRU 缓存的功能。
• 在构造函数中，传入 accessOrder 参数为 true，表示按照访问顺序维护链表，这样每次访问元素时，都会将该元素移动到链表的末尾，表示它是最近使用的。
• 在 get 方法中，调用 super.getOrDefault(key, -1) 来获取元素，如果元素存在，则会将其移动到链表末尾；如果不存在，则返回 -1。
• 在 put 方法中，调用 super.put(key, value) 来插入元素，如果元素已经存在，则会更新其值并移动到链表末尾；如果元素不存在，则会插入新元素，并根据 removeEldestEntry 方法的返回值来判断是否需要删除最旧的元素。
• 通过这种方式，LinkedHashMap 可以自动维护元素的访问顺序，并且在达到容量限制时，自动删除最旧的元素，从而实现 LRU 缓存的功能。

代码实现

class LRUCache extends LinkedHashMap<Integer,Integer> {
    private int capacity;

    public LRUCache(int capacity) {
        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);
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){
        return size() > capacity;
    }
}

/**
 * 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);
 */