LinkedList实现基于LRU算法的缓存

学过操作系统的人都知道LRU页面切换算法,其实这个算法不仅仅只是能在页面切换中应用到,在缓存中也有很实际的应用。最典型的实现方式是采用LinkedHashMap来实现这个缓存,大家可以在Java源码里面看到这个类的作者关于这个的描述,不过全是英文,但是却明确提到过。

下面废话不多说,直接展示我自己关于这个算法实现的代码吧,亲测通过:

核心算法代码:

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
import java.util.Hashtable;
import java.util.LinkedList;

/**
* Created by IntelliJ IDEA.
* Date: 8/7/15 4:46 PM
* Author: Richard
*/
public class LinkedListCache<Object>{

//默认的缓存大小
private static int CAPACITY = 0;

//引用一个双向链接表
private LinkedList<Object> list;

//构造函数
public LinkedListCache(int capacity) {
this.CAPACITY = capacity;
list = new LinkedList<Object>();
}

//添加一个元素
public synchronized void put(Object object) {

if(list != null && list.contains(object)) {
list.remove(object);
}
removeLeastVisitElement();
list.addFirst(object);
}

//移除最近访问次数最少的元素
private synchronized void removeLeastVisitElement() {

int size = size();

//注意,这儿必须得是CAPACITY - 1否则所获的size比原来大1
if(size > (CAPACITY - 1) ) {
Object object = list.removeLast();
System.out.println("本次被踢掉的元素是:" + object.toString());
}
}

//获取第N个索引下面的元素
public synchronized Object get(int index) {
return list.get(index);
}

//清空缓存
public synchronized void clear() {
list.clear();
}

//获取链接表的大小
public int size() {
if(list == null) {
return 0;
}
return list.size();
}

//toString方法
public String toString() {
return list.toString();
}

}

测试代码:

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
package hk.inso.www.test;

import hk.inso.www.cache.LRUCache;
import hk.inso.www.cache.LinkedListCache;
import hk.inso.www.cache.MapCache;

import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

/**
* Created by Richard on 8/5/15.
*/
public class CacheTest {

public static void main(String[] args) throws InterruptedException {

LinkedListCache linkedListCache = new LinkedListCache<String>(5);

linkedListCache.put("1");
System.out.println(linkedListCache.toString());
Thread.sleep(1000);
linkedListCache.put("2");
System.out.println(linkedListCache.toString());
Thread.sleep(1000);
linkedListCache.put("3");
System.out.println(linkedListCache.toString());
Thread.sleep(1000);
linkedListCache.put("4");
System.out.println(linkedListCache.toString());
Thread.sleep(1000);
linkedListCache.put("5");
System.out.println(linkedListCache.toString());
Thread.sleep(1000);
linkedListCache.put("1");
System.out.println(linkedListCache.toString());
Thread.sleep(1000);
linkedListCache.put("6");
System.out.println(linkedListCache.toString());
Thread.sleep(1000);
linkedListCache.put("4");
System.out.println(linkedListCache.toString());
Thread.sleep(1000);
linkedListCache.put("7");
System.out.println(linkedListCache.toString());
}
}

不要吐槽这个哈,时间关系,就直接这么演示了,你可以直接拷贝下来运行就可以了。希望可以帮到你!

分享到