博客：https://www.xmaven.cn/

一、介绍LRU

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

简而言之：淘汰最早使用的元素

二、如何设计LRU

新增不同元素的时候就是需要往前挪动
新增相同的元素就需要我们先把它在当前位置删除，然后新增元素

这个设计思想需要一个队列和一个HashMap

1.为什么需要队列？

这个LRU有着先进先出的原则，我们所以考虑队列

2.为什么需要HashMap？

设计LRU都是基于Key-Value来建立
这个LRU需要我们建立相关的索引来取数据用的所以会使用到HashMap

我们Java中既有LinkedList又有HashMap特性的有 LinkedHashMap
**

三、LRU实现过程

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.StreamSupport;

/**
 * @Author: Ambition
 * @Description TODO 首先你可能会有点顾虑：1.为什么实现Iterable接口(为了方便我们迭代对象)
 * @Date: 2021/7/14 7:09 下午
 * @Version 1.0
 */
public class LRUCache<K, V> implements Iterable<K> {

    // 设置最大的缓存数
    int MAX = 3;

    LinkedHashMap<K, V> cache = new LinkedHashMap<>();

    public void cache(K key, V value) {
        // 第一种情况需要我们更新缓存
        if (cache.containsKey(key)) {
            // 1.当我们的缓存中包含这个key，我们需要更新缓存，也就是移除我们的这个key
            cache.remove(key);

        //第二种情况（容量超过我们限制的范围）需要我们移除最前面的元素    
        } else if (cache.size() >= MAX) {
            // 1.当缓存里面的数量超过我们的设置的阀值
            // 2.我们需要移除最右边的元素
            // 题外话，正常的移除最右边的元素对于我们的hashmap是做不到的，但是作为一个LinkedHashMap还是可以实现的
            // 这个是我们常用的迭代器迭代取对象
            Iterator<K> it = cache.keySet().iterator();
            // 这个一步判断可以直接省略，直接用中间的逻辑
            if (it.hasNext()) {
                // 取出第一个元素
                K first = it.next();
                // 移除第一个元素
                cache.remove(first);
            }
        }

        // 队列的形式追加元素
        cache.put(key, value);
    }

    @Override
    public Iterator<K> iterator() {
        // 迭代器还是沿用我们的LinkedHashMap 迭代的对象还是我们的 LinkedHashMap
        Iterator<Map.Entry<K, V>> it = cache.entrySet().iterator();
        return new Iterator<K>() {
            // 下一个元素是否存在
            @Override
            public boolean hasNext() {
                return it.hasNext();
            }
            
            // 下一个元素的key
            @Override
            public K next() {
                return it.next().getKey();
            }
        };
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> lru = new LRUCache<>();
        lru.cache("A", 1);
        lru.cache("B", 2);
        lru.cache("C", 3);

        lru.cache("D", 4);
        lru.cache("C", 10);
        // 利用Java8特新Stream来实现我们的迭代对象
        System.out.println(
                "leave <-" +
                        StreamSupport.stream(lru.spliterator(), false)
                                .map(Object::toString)
                                .collect(Collectors.joining("<-"))
        );
    }

}