LRU实现(HashMap&&LinkedHashMap)

简介

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;
    }
}