简介

LRU即(Least Recent Used)最近最少使用。缓存可以用HashMap去模拟，用String作为key去访问数据，当缓存满了的时候，我们就需要将最近最少使用的删掉。如果额外开辟空间去标记最近使用就很麻烦了，我们可以用双向链表去进行模拟。

当缓存新增节点时：该节点放到链表最前面。
当缓存数据被访问时：节点放到最前面
当缓存满时：将最后面的节点删除

基于HashMap

  • 代码如下:

    public class LRUNode {
  String key;
  Object value;
  LRUNode prev;
  LRUNode next;

  public LRUNode(String key, Object value) {
      this.key = key;
      this.value = value;
  }
}
public class LRUCache {

  private HashMap<String,LRUNode> map;
  private int capcity;
  private LRUNode head;
  private LRUNode tail;

  public LRUCache(int capcity) {
      this.capcity = capcity;
  }

  public Object get(String key){
      LRUNode node = map.get(key);
      if (node != null){
          remove(node,false);
          setHead(node);
          return node.value;
      }
      return null;
  }

  public void set(String key,Object value){
      LRUNode node = map.get(key);

      if (node != null){
          node.value = value;
          remove(node,false);
          setHead(node);
      }else {
          node = new LRUNode(key, value);
          if (map.size() >= capcity){
              remove(tail,true);
          }
          map.put(key, node);
          setHead(node);
      }
  }
  private void setHead(LRUNode node) {
      if (head != null) {
          node.next = head;
          head.prev = node;
      }
      head = node;
      if (tail == null) {
          {
              tail = node;
          }
      }
  }
  private void remove(LRUNode node,boolean flag){
      if (node.prev != null){
          node.prev.next = null;
      }else {
          head = node.next;
      }

      if (node.next != null){
          node.next.prev = node.prev;
      }else {
          tail = node.prev;
      }

      node.next = null;
      node.prev = null;

      if (flag){
          map.remove(node,flag);
      }
  }
}

基于LinkedHashMap实现

public class LRUCache<K,V> extends LinkedHashMap<K,V> {

    private final int CACHE_SIZE;

    public LRUCache(int cacheSize){
        // true基于访问排序，false基于插入排序
        super((int) (Math.ceil(cacheSize / 0.75) + 1),0.75f,true);
        CACHE_SIZE = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当 map中的数据量大于指定的缓存个数的时候，就自动删除最老的数据。
        return size() > CACHE_SIZE;
    }
}