LRU 缓存机制

题目链接

思路

• 需要额外的双向链表维持最近访问次序+HashMap来实现快速访问

  代码

  ```java class LRUCache { private Lru head = new Lru(0, 0); private Lru tail = new Lru(0, 0); private Map map; private int usedLen = 0; private int len;

  public LRUCache(int capacity) {

    this.map = new HashMap<>(capacity);
    this.head.next = tail;
    this.tail.prev = head;
    this.len = capacity;

  }

  public int get(int key) {

   if (map.containsKey(key)) {
       //移除节点
        Lru lru = map.get(key);
        remove(lru);
        //添加头部
        addHead(lru);
        return lru.val;
   }
   return -1;
  

  }

  public void put(int key, int value) {

    if (map.containsKey(key)) {
        //移除节点
        Lru lru = map.get(key);
        remove(lru);
        //插入头部
        lru.val = value;
        addHead(lru);
    } else {
        if (usedLen == len) {
            //移除
            map.remove(tail.prev.key);
            remove(tail.prev);
        } else {
            usedLen++;
        }
        //插入新节点操作
        Lru lru = new Lru(key, value);
        addHead(lru);
        map.put(key, lru);
    }
  

  }

  private void addHead(Lru lru) {

    Lru next = head.next;
    lru.next = next;
    next.prev = lru;
    head.next = lru;
    lru.prev = head;
  

  }

  private void remove(Lru lru) {

    Lru prev = lru.prev;
    Lru next = lru.next;
    prev.next = next;
    next.prev = prev;
  

  } }

class Lru { Lru prev; Lru next; int key; int val;

public Lru(int key, int val) {
    this.key = key;
    this.val = val;
}

}

//方式二 class LRUCache extends LinkedHashMap{ 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; 
}

} ``` LRU缓存机制