Last Recently Used

LRU算法，从名字就很容易看出，“最近最少使用”。它是一种可以帮助我们直到一组数据中，哪些数据是不经常用到的。这样在我们存储空间达到上限的时候，就可以将这个数据进行删除，以节省空间。这个算法在缓存中的应用是非常广泛的。
它也非常符合缓存的实际需求：查找删除速度快，但缓存容量是比较昂贵的。
不仅如此，在操作系统的内存管理中，也是应用了LRU算法的。

算法思想

对于一组数据，如果其中某一个元素我们在最近访问了它，那么将来还要访问它的可能性是非常高的。相反，对于一个元素，如果一直没有访问它，那么以后访问它的可能性就很低了。在空间不足的时候，我们就可以将很久没访问的元素删除。

所以，我们可以用一个链表来存储这一组数据。并且每当我们访问了一个元素，就将这个元素放置到链表的开头。这样一段时间过后，链表的尾巴部分，一定都是一些没怎么访问过的元素了。在空间上限的时候，我们就可以对它进行淘汰。

这样做的话，插入和删除的时间复杂度是O(1)。但是读取的复杂度就变高了，变成了O(N)显然不符合缓存读多写多的场景。

所以我们可以针对它进行优化，提高它读取的效率。用一个hashmap存储所有元素的key，value则是对应的链表元素
大概就是如图这样子：

这样我们在查找的时候，就直接拿着key，从hashMap里面就能拿到对应的链表节点了，查找的复杂度也变成了O(1)。

代码实现

随便用Java实现了下，对于链表操作并没有做封装，将链表的插入删除封装在链表类内部会更规范。

public class HashLinkList<K, V> {

    private final HashMap<K, HashLinkList.Node> hashMap = new HashMap<>();
    //头部
    private final Node<K, V> head;
    //尾部
    private final Node<K, V> tail;
    //最大容量
    private final int maxSize;

    public HashLinkList(int size) {
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        this.head.next = tail;
        tail.parent = head;
        this.maxSize = size;
    }

    public void insert(K key, V value) {
        Node node = new Node(key, value);
	//如果已有重复的元素，则先将它删除
        if (this.hashMap.containsKey(key)) {
            Node toDel = this.hashMap.get(key);
            toDel.parent.next = toDel.next;
            toDel.next.parent = toDel.parent;
            this.hashMap.remove(key);
        }
        //如果达到了最大容量，则删除末尾的元素
        if (this.hashMap.size() >= maxSize) {
            Node toDel = this.tail.parent;
            toDel.parent.next = tail;
            tail.parent = toDel.parent;
            this.hashMap.remove(toDel.key);
        }

        //将元素插入链表开头
        node.next = head.next;
        node.parent = head;
        head.next.parent = node;
        head.next = node;
        this.hashMap.put(key, node);

    }

    public V get(K key) {
        Node node = Node.class.cast(this.hashMap.get(key));
        if (node == null) return null;
        //将node从原本的位置移除
        node.parent.next = node.next;
        node.next.parent = node.parent;
        //node移至开头
        node.parent = head;
        node.next = head.next;
        head.next.parent = node;
        head.next = node;
        return (V) node.value;
    }


    public void remove(K key) {
        Node node = (Node) this.hashMap.get(key);
        if (node == null) return;
        node.parent.next = node.next;
        node.next.parent = node.parent;
        this.hashMap.remove(key);
    }

    public class Node<K, V> {

        private V value;

        private K key;

        private Node parent;

        private Node next;

        public Node(V value, K key) {
            this.value = value;
            this.key = key;
        }
    }
}