本文将分为以下两个部分：

1.简介几个缓存淘汰算法

2.实现自己的LRU内存缓存(Java)

1.几种缓存淘汰算法

1.1 FIFO(First In, First Out)

先进先出策略，意即缓存中优先淘汰最早被插入的元素。
可以基于Queue实现，有新数据访问时，直接插入队列尾部，数据在队列中移动，淘汰队列头部的数据。

1.2 LFU(Least Frequently Used)

一种按使用频率作为判断标准的算法，每个数据块有一个引用计数，所有数据按引用计数进行排序，具有相同引用计数的数据按时间排序：

1.新的数据被访问后，加入队列尾部，引用计数为1
2.队列中的数据被访问后，引用计数+1， 队列重新按引用计数排序
3.当需要淘汰缓存时，将排好序的末尾数据删除

1.3 LRU（Least Recently Used）

基于数据的历史访问记录来进行淘汰数据，越是近期被访问的，越不应该淘汰。
可以缓存基于链表实现，越靠近尾部，是越早之前访问过的数据。模式简图如下：

image

当有新数据需要访问时：

image

第一部分有参考极客时间王铮的数据结构与算法之美，了解了以上的思路，👇我们进入第二部分，如何自己实现一个基于链表的LRU缓存，缓存该满足的基本条件有以下几点：

1.缓存有一个容量限制: capacity；
2.从缓存里面拿数据: get()方法；
3.从缓存里面存数据: set()方法；
4.缓存的考虑出发，存取要方便快捷，所以get()和 set()方法的时间复杂度要低：因此选用Hashmap存数据，双向链表作为Cache的框架。

基于以上几点的考量，结合第一部分的LRU的基础知识，我给set()方法画了一个简单的路线图：

image

以下附上完整代码：

public class HedyCache2 {
    private int capcity;
    private Map<Object, Object> map = new HashMap<>();
    private Deque deque = new LinkedList();

    public HedyCache2(int capacity){
        this.capcity=capacity;
    }
    public void set(Object key,Object value){
        Object v = map.get(key);
        if(v != null){
            map.put(key,value);
            deque.removeFirstOccurrence(key);
            deque.addFirst(key);
        }else{
            if (map.size() == capcity){
                map.put(key,value);
                deque.addFirst(key);
                Object oldKey = deque.removeLast();
                map.remove(oldKey);
            }else{
                map.put(key,value);
                deque.addFirst(key);
            }
        }
    }

    public Object get(Object key){
        Object target = map.get(key);
        if(target == null){
            return null;
        }else{
          deque.removeFirstOccurrence(key);
          deque.addFirst(key);
        }
        return target;
    }


    public void displayAll(){
        map.forEach( (k,v) ->{
            System.out.print(k +":"+ v + ";" + "  ");
        });
        System.out.println("-----------------------------");

        deque.forEach( i ->{
            System.out.print(i + " ");
        });
    }
}

小结：

网上很多自己实现LRU的分享文章都是要自己先实现一个双向链表，然后才去一步步构造从头部添加或从尾部删除的方法，步骤比较多；本文尽量站在“拿来主义的视角”，想通过利用现有的比如deque.remove()/addFirst()/removeLast()/removeFirstOccurence()等方法，减少了码字效率，站在别人的肩膀上编程的这种思路值得推广到后续的其他操作里去。