缓存淘汰算法-LRU

比较常见的缓存淘汰算法有LRU(Least Recently Used 最近最少使用算法)和LFU(Least Frequently Used 最近最不常用算法).

LRU是按照最后访问时间来进行淘汰.

LRU实现起来比较简单,leetcode146就是实现一个LRU算法.

最简单的实现方式是利用Java提供的LinkedHashMap.

class LRUCache extends LinkedHashMap<Integer, Integer> {
   private static final long serialVersionUID = 5440871089044149474L;
   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;
   }
}

不用LinkedHashMap的话,也可以自己用双向链表加HashMap来实现.

class LRUCache {

   class Node{
      int key;
      int value;
      Node prev;
      Node next;
      Node(int key, int value) {
         this.key = key;
         this.value = value;
      }
   }

   private Map<Integer, Node> m;
   private Node head; //虚拟头结点
   private Node tail; //虚拟尾结点
   private int capacity;
   public LRUCache(int capacity) {
      m = new HashMap<Integer, Node>();
      head = new Node(0, 0);
      tail = new Node(0, 0);
      head.next = tail;
      tail.prev = head;
      this.capacity = capacity;
   }

   private void addNode(Node node) {
      node.next = head.next;
      head.next.prev = node;
      head.next = node;
      node.prev = head;
   }

   private void removeNode(Node node) {
      node.prev.next = node.next;
      node.next.prev = node.prev;
   }

   public int get(int key) {
      Node node = m.get(key);
      if (node == null) {
         return -1;
      } else {
         // 更改链表顺序,把node移到最前面
         removeNode(node);
         addNode(node);
         return node.value;
      }
   }

   public void put(int key, int value) {
      Node node = new Node(key, value);
      Node existed = m.get(key);
      if(existed != null) {
         removeNode(existed);
      }
      m.put(key, node);
      addNode(node);
      if(m.size() > capacity) {
         Node last = tail.prev;
         removeNode(last);
         m.remove(last.key);
      }
   }
}

调试结果如下:

当put(4,1)时,key=1被淘汰,因此get(1)返回-1.

调用get方法,也会将缓存数据移至表头.调用get(1),put(3,3)后,再get(2)就返回-1了.

LRU可以适用于大多数注重最后访问时间的场景.

但是不适用于注重访问次数的场景.

例如缓存容量为2的情况下,我们访问key=a的数据100次,后续访问一次key=b和key=c的数据,此时key=a的缓存数据就被淘汰了.

如果我们认为之前被访问次数越多,越应该被缓存起来,应该越晚被淘汰.那么这种场景下LRU就不适用了.

这时就需要用到LFU算法了.关于LFU的原理和实现,我们后续再进行分析.