淘汰算法LRU

1.基于双链表实现LRU
原理： 将Cache的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。

public class LRUCache {  
	
	//缓存大小
    private int cacheSize;
    //缓存容器
    private Hashtable<K, CacheNode<K, V>> nodes;
    //当前缓存对象数量
    private int currentSize;
    //(实现双链表)链表头
    private CacheNode first;
    //(实现双链表)链表尾
    private CacheNode last;

    public LRUCache(int i) {
        currentSize = 0;
        cacheSize = i;
        nodes = new Hashtable(i);//缓存容器
    }

    /**     * 链表节点     *     */
     * 链表节点
     *
     */
    private static class CacheNode<K,V> {
        CacheNode prev;
        CacheNode next;
        K key;
        V value;
        CacheNode() {
        }
    }

    public V get(K key){
        CacheNode<K, V> node = nodes.get(key);
        if(node!=null){
            moveToHead(node);
            return node.value;
        }else{

            return null;
        }
    }

    public void put(K key, V value){
        CacheNode<K, V> node = nodes.get(key);
        if(node == null){
            if(currentSize >= cacheSize){
                if(last != null){
                    nodes.remove(last.key);
                }
                removeLast();
            }else{
                currentSize++;
            }
            node = new CacheNode<>();
        }
        node.value=value;
        node.key=key;
        moveToHead(node);
        nodes.put(key, node);
    }

    private void removeLast(){
        if(last!=null){
            if(last.prev != null){
                last.prev.next = null;
            }else{
                first = null;
            }
            last = last.prev;
        }
    }

    private void moveToHead(CacheNode node){
        if(node == first){
            return;
        }

        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        if (last == node) {
            last = node.prev;
        }
        if (first != null) {
            node.next = first;
            first.prev = node;
        }
        first = node;
        node.prev = null;
        if (last == null) {
            last = first;
        }
    }
}

2.借助LinkedHashMap实现LRU算法
LinkedHashMap 添加元素的时候会调用removeEldestEntry方法，默认removeEldestEntry返回false；我们通过覆盖removeEldestEntry方法，判断当前容量是否已经超过最大容量，来实现lru功能。

public class LRUCache<K, V> extends LinkedHashMap<K, V>{
	private static final int MAX_ENTRIES;
	
	public LRUCache(int cacheSize){
		MAX_ENTRIES = cacheSize;
	}
	
	@Override
	protected boolean removeEldestEntry(Map.Entry<K, V> eldest){
		return size()>MAX_ENTRIES;
	}
}