本文实例讲述了java LRU算法介绍与用法。分享给大家供大家参考，具体如下：
1.前言
在用户使用联网的软件的时候，总会从网络上获取数据，当在一段时间内要多次使用同一个数据的时候，用户不可能每次用的时候都去联网进行请求,既浪费时间又浪费网络
这时就可以将用户请求过的数据进行保存，但不是任意数据都进行保存，这样会造成内存浪费的。LRU算法的思想就可以运用了。
2.LRU简介
LRU是Least Recently Used 近期最少使用算法，它就可以将长时间没有被利用的数据进行删除。
LRU在人们一些情感中也体现的得很好的。当你和一群朋友接触的时候，经常联系的人关系是很好的，若很久没有联系到最后估计都不会再有联系了，也就会是失去这位朋友了。
3.下面通过代码展现LRU算法:
最简单的一种方法是利用LinkHashMap，因为它本身就有一个方法就是在所设置的缓存范围内，去除掉额外的旧数据
|
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
|
public class LRUByHashMap<K, V> { /* * 通过LinkHashMap简单实现LRU算法 */ /** * 缓存大小 */ private int cacheSize; /** * 当前缓存数目 */ private int currentSize; private LinkedHashMap<K, V> maps; public LRUByHashMap(int cacheSize1) { this.cacheSize = cacheSize1; maps = new LinkedHashMap<K, V>() { /** * */ private static final long serialVersionUID = 1; // 这里移除旧的缓存数据 @Override protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) { // 当超过缓存数量的时候就将旧的数据移除 return getCurrentSize() > LRUByHashMap.this.cacheSize; } }; } public synchronized int getCurrentSize() { return maps.size(); } public synchronized void put(K k, V v) { if (k == null) { throw new Error("存入的键值不能为空"); } maps.put(k, v); } public synchronized void remove(K k) { if (k == null) { throw new Error("移除的键值不能为空"); } maps.remove(k); } public synchronized void clear() { maps = null; } // 获取集合 public synchronized Collection<V> getCollection() { if (maps != null) { return maps.values(); } else { return null; } } public static void main(String[] args) { // 测试 LRUByHashMap<Integer, String> maps = new LRUByHashMap<Integer, String>( 3); maps.put(1, "1"); maps.put(2, "2"); maps.put(3, "3"); maps.put(4, "4"); maps.put(5, "5"); maps.put(6, "6"); Collection<String> col = maps.getCollection(); System.out.println("存入缓存中的数据是--->>" + col.toString()); }} |
运行后的效果:
代码明明是put了6个Entry但最后只显示了三个，之间的三个是旧的所以直接被咔嚓掉了
第二种方法是利用双向链表 + HashTable
双向链表的作用是用来记录位置的，而HashTable作为容器来存储数据的
为什么用HashTable不用HashMap呢？
1.HashTable的键和值都不能为null;
2.上面用LinkHashMap实现的LRU，有用到 synchronized , 让线程同步去处理，这样就避免在多线程处理统一数据时造成问题
而HashTable自带同步机制的，所以多线程就能对HashTable进行正确的处理了。
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
public class LRUCache { private int cacheSize; private Hashtable<Object, Entry> nodes;//缓存容器 private int currentSize; private Entry first;//链表头 private Entry last;//链表尾 public LRUCache(int i) { currentSize = 0; cacheSize = i; nodes = new Hashtable<Object, Entry>(i);//缓存容器 } /** * 获取缓存中对象,并把它放在最前面 */ public Entry get(Object key) { Entry node = nodes.get(key); if (node != null) { moveToHead(node); return node; } else { return null; } } /** * 添加 entry到hashtable, 并把entry */ public void put(Object key, Object value) { //先查看hashtable是否存在该entry, 如果存在，则只更新其value Entry node = nodes.get(key); if (node == null) { //缓存容器是否已经超过大小. if (currentSize >= cacheSize) { nodes.remove(last.key); removeLast(); } else { currentSize++; } node = new Entry(); } node.value = value; //将最新使用的节点放到链表头，表示最新使用的. node.key = key moveToHead(node); nodes.put(key, node); } /** * 将entry删除, 注意：删除操作只有在cache满了才会被执行 */ public void remove(Object key) { Entry node = nodes.get(key); //在链表中删除 if (node != null) { 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 == node) first = node.next; } //在hashtable中删除 nodes.remove(key); } /** * 删除链表尾部节点，即使用最后 使用的entry */ private void removeLast() { //链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象） if (last != null) { if (last.prev != null) last.prev.next = null; else first = null; last = last.prev; } } /** * 移动到链表头，表示这个节点是最新使用过的 */ private void moveToHead(Entry 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; } /* * 清空缓存 */ public void clear() { first = null; last = null; currentSize = 0; }}class Entry { Entry prev;//前一节点 Entry next;//后一节点 Object value;//值 Object key;//键} |
希望本文所述对大家java程序设计有所帮助。
原文链接：http://www.cnblogs.com/liangstudyhome/p/4503957.html
