LRU算法手写实现

LRU(Least Recently Used)是一种常见的页面置换算法，在计算中，所有的文件操作都要放在内存中进行，然而计算机内存大小是固定的，所以我们不可能把所有的文件都加载到内存，因此我们需要制定一种策略对加入到内存中的文件进项选择。

LRU的设计原理就是，当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要然其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。

每次访问的数据都会放在栈顶，当访问的数据不在内存中，且栈内数据存储满了，我们就要选择移除栈底的元素，因为在栈底部的数据访问的频率是比较低的。所以要将其淘汰。

其实我们可以通过数组的形式简单的实现LRU算法，但性能不高，所以我们这里采用双向链表和Hash表的形式实现。
首先我们新建一个节点：

class Node<K,V> {
    public K key;
    public V val;
    public Node<K,V> next, prev;

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

节点里面需要保存一个key,value以及当前节点的前驱和后继节点。
我们需要实现LRU的put()和get()方法。
先讲一下get()的实现逻辑：

这里，将放入表头的方法moveHead()抽取出来。

下面是put()方法的逻辑：

这里有一点需要注意，put相同key的节点时，其实已经调用了get()方法进行了moveHead操作。将该节点移到了链表头部。
关于节点前驱和后继的操作大家自己体会，这里就不赘述，下面是完整的实现代码。

public class LRUCache<K,V> {
    private int capacity;
    private HashMap<K, Node<K,V>> map;
    private Node<K,V> head;
    private Node<K,V> tail;

    LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        K k = null;
        V v = null;
        head = new Node<>(k, v);
        tail = new Node<>(k, v);
        head.next = tail;
        tail.prev = head;
    }

    V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        Node current = map.get(key);
        current.next.prev = current.prev;
        current.prev.next = current.next;
        moveHead(current);
        return map.get(key).val;
    }

    void put(K key, V value) {
        if (get(key) != null) {
            map.get(key).val = value;
            return;
        }
        if (capacity == map.size()) {
            map.remove(tail.prev.key);
            tail.prev = tail.prev.prev;
            tail.prev.next = tail;
        }
        Node<K,V> node = new Node<>(key, value);
        map.put(key, node);
        moveHead(node);
    }
    private void moveHead(Node<K,V> current) {
        current.next = head.next;
        head.next = current;
        current.next.prev = current;
        current.prev = head;
    }
}