LRU

全称

Least Recently Used，最近最少使用，如果一个数据在最近没有被访问到，那么在将来它被访问到的可能性也很小，根据访问的时间来处理的。

LinkedList实现

public class MyTest {

    // 缓存容量
    private final static int capacity = 3;

    // 缓存的key
    private static LinkedList<String> keys = new LinkedList<String>();

    public static void main(String[] args) {

        MyTest myTest = new MyTest();
        myTest.lru("a");
        myTest.lru("b");
        myTest.lru("c");
        myTest.lru("d");
        myTest.lru("b");
        System.out.println(Arrays.toString(keys.toArray()));
        // [b, d, c]

    }

    /**
     * 要访问的key，插入到头节点
     * 当key命中时，把key移动到头节点
     * 当容量满时，移除尾结点的数据
     */
    public void lru(String key){
        // 使用链表实现
        boolean containsFlag = keys.contains(key);
        // 如果不包含，则插入到头节点
        if(!containsFlag){
            // 如果超过了容量，则把尾结点移除
            if(keys.size() >= capacity){
                keys.removeLast();
            }
            // 插入到头节点中
            keys.addFirst(key);
        }else{
            // 如果包含，则把该元素移动到头节点
            // 先找到这个元素的索引位，然后移除，返回该元素添加到头节点
            keys.addFirst(keys.remove(keys.indexOf(key)));
        }
    }

}