LRU缓存机制

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”

HashMap实现LRU缓存机制思想

• 用LinkedList来做缓存，每次调用get、put方法时，都此节点放在链表的尾部
• 当链表满的时候，将链表首部的数据丢弃
  参考链接：https://blog.csdn.net/zzr2018xzy/article/details/97293640

LinkedHashMap实现LRU缓存机制思想

LinkedHashMap 指定 accessOrder 参数为 true，即可让它按访问顺序维护链表。当我们调用get/getOrDefault/replace等方法时，将这些方法访问的节点移动到链表的尾部即可，那我们借助其访问顺序排序的特性，访问到的结点每次会被移到链表尾部，我们可以在链表满的时候，将此链表的首部丢掉

//LinkedHashMap源码
void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;    // 根据条件判断是否移除最近最少被访问的节点
            removeNode(hash(key), key, null, false, true);
        }
    }
///通过覆盖此方法可实现LRU缓存机制思想：移除链表的头结点
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

当基于 LinkedHashMap 实现缓存时，可覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。我们可以根据节点数量判断是否移除最近最少被访问的节点，在构造缓存对象时，传入最大节点数。当插入的节点数超过最大节点数时，移除最近最少被访问的节点

package pra.draw;

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
	private static final int DEFAULT_NODE_NUM = 11; //默认缓存值
	private int capacityLimit; //缓存限定值

	public LRUCache() {
		this(DEFAULT_NODE_NUM);
	}

	public LRUCache(int capacity) {
		super(capacity, 0.75f, true); //依次：初始容量、负载因子、采用访问排序
		this.capacityLimit = capacity;
	}

	public V putKV(K key, V val) {
		return put(key, val);
	}

	public V getValue(K key) {
		return get(key);
	}

	public boolean exists(K key) {
		return containsKey(key);
	}

	@Override
	protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
		return size() > capacityLimit;  //如果LinkedHashMap的长度到达缓存容量，进行清除
	}

	public static void main(String[] args) {
		LRUCache cache = new LRUCache();
		for (int i = 0; i < 11; i++) {
			cache.putKV(i, i);
		}
		System.out.println(cache);
		cache.getValue(7);
		System.out.println(cache);
		cache.getValue(5);
		System.out.println(cache);
		cache.putKV(10, 9);  //覆盖掉原来的(10,10),此时缓存容量依旧够用
		System.out.println(cache);
		//再多增加一个节点
		cache.putKV(11, 11);
		System.out.println(cache);  //此时缓存中数据已经发生变化，移除掉了链表的头结点
	}
}

结果: