LRUCache

LRU (Least Recently Used) 的意思就是近期最少使用算法，它的核心思想就是会优先淘汰那些近期最少使用的缓存对象。一般采用：LinkedList+HashMap实现，在Java中用LinkedHashMap实现。

LinkedList+HashMap实现方案

  1. get/put时把value放到双向链表的tail
  2. map的size大于设定的容量后,移除链表的head.
    3）内存大概的结构为:
    head -> node -> node -> tail.
    1. /**
    2. * @author xiele.xl
    3. * @date 2020-04-17 19:18
    4. */
    5. public class LRUCache {
    6.  private int capacity;
    7.  private HashMap<Integer, Integer> map;
    8.  private LinkedList<Integer> list;
    9.  public LRUCache(int capacity) {
    10.      this.capacity = capacity;
    11.      map = new HashMap<>();
    12.      list = new LinkedList<>();
    13.  }
    14.  public int get(int key) {
    15.      if (map.containsKey(key)) {
    16.          list.remove((Integer)key);
    17.          list.addLast(key);
    18.          return map.get(key);
    19.      }
    20.      return -1;
    21.  }
    22.  public void put(int key, int value) {
    23.      if (map.containsKey(key)) {
    24.          list.remove((Integer)key);
    25.          list.addLast(key);
    26.          map.put(key, value);
    27.          return;
    28.      }
    29.      if (list.size() == capacity) {
    30.          map.remove(list.removeFirst());
    31.          map.put(key, value);
    32.          list.addLast(key);
    33.      } else {
    34.          map.put(key, value);
    35.          list.addLast(key);
    36.      }
    37.  }
    38. }
    直接继承LinkedHashMap
    1. public class LRUCache<K,V> extends LinkedHashMap<K,V>{
    2.  private final int cacheSize;
    3.  public LRUCache(int cacheSize) {
    4.      super((int)Math.ceil((cacheSize / 0.75) + 1), 0.75F, true);
    5.      this.cacheSize = cacheSize;
    6.  }
    7.  @Override
    8.  protected boolean removeEldestEntry(Entry<K, V> eldest) {
    9.      return size() > cacheSize;
    10.  }
    11. }