LRU手撕实现

国庆期间，因玩忘学，愧疚难当，一时冲动，手撕算法，以表歉意。谈起LRU，实则对其心仪已久，之前也对其实现原理进行过粗略的理解，也接触过相关应用：如经典的redis的淘汰策略、mybatis的二级缓存策略中都对其有过应用（LRU算法算是应用较广的保留热点数据的方法），但真正的讲起其原理总是略有差之毫厘之感（博客中的实现有多种），今天借着愧疚的冲动，具体实现一下当前已知的最优的实现。
LRU的基本实现是将热点数据移动到队列头，这样不常用的数据就会处于队列尾，常用的实现有数组、双向链表，但就查询效率而已，hashmap有较好的查询效率（O（1）级别），而双向链表又能够保证插入顺序，基于Hashmap+双向链表可以实现效率较高的LRU。
一、Hashmap+双向链表实现
基本的Hashmap+双向链表实现如下，nodes作为一个hashmap通过不断添加key、value（链表节点），而value间维持一个双向链表，这样就能保证维持capacity容量的
双向链表，而每个key对应的节点都存储在Hashmap里。但是，可能也会存在一个问题，
就是如果插入较多数据后，因为产生了大量的node在hashmap里没有被使用到，可能会产生内存泄露。

public class LRU<K,V> {
    private int capacity;
    private int size;
    private Entry<K,V> head;
    private Entry<K,V> tail;
    private class Entry<K,V>  extends SoftReference<K> {
        Entry(K key, V value){
            super(key);
            this.key = key;
            this.value = value;
        }
        private K key;
        private V value;
        private Entry<K,V> prev;
        private Entry<K,V> next;
    }
    private HashMap<K , Entry<K,V>> nodes = new ConcurrentHashMap<>();
    LRU(int capacity){
        this.capacity = capacity;
        size = 0;
        head=null;
        tail=null;
        head.prev = head;
        head.next = tail;
        tail.next = tail;
        tail.prev = head;
    }
    public void put(K key, V value){
        Entry<K,V> node = new Entry<K, V>(key, value);
        if(nodes.get(key) != null ){
            Entry<K,V> tempNode = nodes.get(key);
            Entry<K,V> prevNode = tempNode.prev;
            Entry<K,V> nextNode = tempNode.next;
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
            node.prev = node;
            node.next = head;
            head = node;
        } else if(size >= capacity){
            Entry<K,V> prevNode = tail.prev;
            prevNode.next = node;
            node.prev = prevNode;
            node.next = node;
            tail = node;
        } else{
            if(size == 0){
                head = node;
                tail = node;
            } else{
                node.prev = tail;
                node.next = node;
                tail = node;
            }
            size ++;
        }
        nodes.put(key,node);
    }
    public V get(K key){
        if(nodes.get(key) != null){
            Entry<K,V> tempNode = nodes.get(key);
            Entry<K,V> prevNode = tempNode.prev;
            Entry<K,V> nextNode = tempNode.next;
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
            tempNode.prev = tempNode;
            tempNode.next = head;
            head = tempNode;
            nodes.put(key,tempNode);
        }
        return null;
    }
    public List<V> printAllValue(){
        List<V> values = new ArrayList<V>();
        Entry<K,V> node = head;
        while(true){
            values.add(node.value);
            if(node == tail){
                break;
            }
            node = node.next;
        }
        return values;
    }
}

二、LinkedHashmap实现
JDk原生LinkedHashmap的实现中，已经实现了LRU清除非热点数据的逻辑，LinkedHashMap的实现与一中大同小异，其具体表现为重写了Hashmap的afterNodeInsertion、afterNodeAccess方法，由于这个特性，可以封装linkedHashmap，实现LRU，原理见一，实现大同小异，相对简单。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }
void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

三、缓存污染
缓存污染，当LRU遭遇偶发性、周期性批量操作，热点数据的准确率会被破坏。