什么是LRU算法
- Least Recently Used 淘汰算法以时间作为参考，淘汰最长时间未被使用的数据
- 如果数据最近被访问过，那么将来被访问的几率也更高；会淘汰最长时间没有被使用的元素（都没人要你了，不淘汰你淘汰谁）
- 基本原理是：在缓存满时，将最近最久未使用的数据淘汰出缓存，以便给新的数据留出空间。
- 实现方式可以用：数组、链表等方式
- 新插入的数据放在头部，最近访问过的也移到头部，空间满时将尾部元素删除
编码实现
public class LRUCache<K,V> { //定义存储key的顺序表 private LinkedList<K> cacheKey; //定规存储数据的map 存储key，value private HashMap<K,V> cacheValues; //定义缓存的容量 private int capacity; //构造方法初始化缓存 public LRUCache(int capacity) { this.cacheKey = new LinkedList<>(); this.capacity = capacity; this.cacheValues = new HashMap<>(); } //向缓存中put元素 public void put(K key, V value) { //先添加元素，无论有没有这个key，直接进行put cacheValues.put(key, value); cacheKey.add(0, key); //判断长度是否超出最大容量，超出进行淘汰 if (cacheKey.size() > capacity) { //如果容量已满，则删除最后一个key K lastKey = cacheKey.get(cacheKey.size() - 1); cacheKey.remove(lastKey); cacheValues.remove(lastKey); } } //获取指定key的元素的value，并且将这个key放置在队头的位置 public V get(K key) { V data = null; if (cacheKey.contains(key)) { data = cacheValues.get(key); cacheKey.remove(key); cacheKey.add(0,key); } return data; } // public void showList(){ System.out.println(cacheKey.toString()); } public static void main(String[] args) { LRUCache<String,String> cache = new LRUCache<>(5); cache.put("A", "任务A"); cache.put("B", "任务B"); cache.put("C", "任务C"); cache.put("D", "任务D"); cache.put("E", "任务E"); cache.showList(); System.out.println("G=" + cache.get("G")); System.out.println("C=" + cache.get("C")); cache.showList(); cache.put("F", "任务F"); cache.showList(); } }
