淘汰算法LRU

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
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功能。

1
2
3
4
5
6
7
8
9
10
11
12
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;
	}
}