现在软件或者网页的并发量越来越大了，大量请求直接操作数据库会对数据库造成很大的压力，处理大量连接和请求就会需要很长时间，但是实际中百分之80的数据是很少更改的，这样就可以引入缓存来进行读取，减少数据库的压力。
常用的缓存有redis和memcached，但是有时候一些小场景就可以直接使用java实现缓存，就可以满足这部分服务的需求。
缓存主要有lru和fifo，lru是least recently used的缩写，即最近最久未使用，fifo就是先进先出，下面就使用java来实现这两种缓存。
lru
lru缓存的思想
- 固定缓存大小，需要给缓存分配一个固定的大小。
- 每次读取缓存都会改变缓存的使用时间，将缓存的存在时间重新刷新。
- 需要在缓存满了后，将最近最久未使用的缓存删除，再添加最新的缓存。
按照如上思想，可以使用linkedhashmap来实现lru缓存。
这是linkedhashmap的一个构造函数，传入的第三个参数accessorder为true的时候，就按访问顺序对linkedhashmap排序，为false的时候就按插入顺序，默认是为false的。
当把accessorder设置为true后，就可以将最近访问的元素置于最前面，这样就可以满足上述的第二点。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/** * constructs an empty <tt>linkedhashmap</tt> instance with the * specified initial capacity, load factor and ordering mode. * * @param initialcapacity the initial capacity * @param loadfactor the load factor * @param accessorder the ordering mode - <tt>true</tt> for * access-order, <tt>false</tt> for insertion-order * @throws illegalargumentexception if the initial capacity is negative * or the load factor is nonpositive */public linkedhashmap(int initialcapacity, float loadfactor, boolean accessorder) { super(initialcapacity, loadfactor); this.accessorder = accessorder;} |
这是linkedhashmap中另外一个方法，当返回true的时候，就会remove其中最久的元素，可以通过重写这个方法来控制缓存元素的删除，当缓存满了后，就可以通过返回true删除最久未被使用的元素，达到lru的要求。这样就可以满足上述第三点要求。
|
1
2
3
|
protected boolean removeeldestentry(map.entry<k,v> eldest) { return false;} |
由于linkedhashmap是为自动扩容的，当table数组中元素大于capacity * loadfactor的时候，就会自动进行两倍扩容。但是为了使缓存大小固定，就需要在初始化的时候传入容量大小和负载因子。
为了使得到达设置缓存大小不会进行自动扩容，需要将初始化的大小进行计算再传入，可以将初始化大小设置为(缓存大小 / loadfactor) + 1，这样就可以在元素数目达到缓存大小时，也不会进行扩容了。这样就解决了上述第一点问题。
通过上面分析，实现下面的代码
|
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
|
import java.util.linkedhashmap;import java.util.map;import java.util.set;public class lru1<k, v> { private final int max_cache_size; private final float default_load_factory = 0.75f; linkedhashmap<k, v> map; public lru1(int cachesize) { max_cache_size = cachesize; int capacity = (int)math.ceil(max_cache_size / default_load_factory) + 1; /* * 第三个参数设置为true，代表linkedlist按访问顺序排序，可作为lru缓存 * 第三个参数设置为false，代表按插入顺序排序，可作为fifo缓存 */ map = new linkedhashmap<k, v>(capacity, default_load_factory, true) { @override protected boolean removeeldestentry(map.entry<k, v> eldest) { return size() > max_cache_size; } }; } public synchronized void put(k key, v value) { map.put(key, value); } public synchronized v get(k key) { return map.get(key); } public synchronized void remove(k key) { map.remove(key); } public synchronized set<map.entry<k, v>> getall() { return map.entryset(); } @override public string tostring() { stringbuilder stringbuilder = new stringbuilder(); for (map.entry<k, v> entry : map.entryset()) { stringbuilder.append(string.format("%s: %s ", entry.getkey(), entry.getvalue())); } return stringbuilder.tostring(); } public static void main(string[] args) { lru1<integer, integer> lru1 = new lru1<>(5); lru1.put(1, 1); lru1.put(2, 2); lru1.put(3, 3); system.out.println(lru1); lru1.get(1); system.out.println(lru1); lru1.put(4, 4); lru1.put(5, 5); lru1.put(6, 6); system.out.println(lru1); }} |
运行结果：
从运行结果中可以看出，实现了lru缓存的思想。
接着使用hashmap和链表来实现lru缓存。
主要的思想和上述基本一致，每次添加元素或者读取元素就将元素放置在链表的头，当缓存满了之后，就可以将尾结点元素删除，这样就实现了lru缓存。
这种方法中是通过自己编写代码移动结点和删除结点，为了防止缓存大小超过限制，每次进行put的时候都会进行检查，若缓存满了则删除尾部元素。
|
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
import java.util.hashmap;/** * 使用cache和链表实现缓存 */public class lru2<k, v> { private final int max_cache_size; private entry<k, v> head; private entry<k, v> tail; private hashmap<k, entry<k, v>> cache; public lru2(int cachesize) { max_cache_size = cachesize; cache = new hashmap<>(); } public void put(k key, v value) { entry<k, v> entry = getentry(key); if (entry == null) { if (cache.size() >= max_cache_size) { cache.remove(tail.key); removetail(); } } entry = new entry<>(); entry.key = key; entry.value = value; movetohead(entry); cache.put(key, entry); } public v get(k key) { entry<k, v> entry = getentry(key); if (entry == null) { return null; } movetohead(entry); return entry.value; } public void remove(k key) { entry<k, v> entry = getentry(key); if (entry != null) { if (entry == head) { entry<k, v> next = head.next; head.next = null; head = next; head.pre = null; } else if (entry == tail) { entry<k, v> prev = tail.pre; tail.pre = null; tail = prev; tail.next = null; } else { entry.pre.next = entry.next; entry.next.pre = entry.pre; } cache.remove(key); } } private void removetail() { if (tail != null) { entry<k, v> prev = tail.pre; if (prev == null) { head = null; tail = null; } else { tail.pre = null; tail = prev; tail.next = null; } } } private void movetohead(entry<k, v> entry) { if (entry == head) { return; } if (entry.pre != null) { entry.pre.next = entry.next; } if (entry.next != null) { entry.next.pre = entry.pre; } if (entry == tail) { entry<k, v> prev = entry.pre; if (prev != null) { tail.pre = null; tail = prev; tail.next = null; } } if (head == null || tail == null) { head = tail = entry; return; } entry.next = head; head.pre = entry; entry.pre = null; head = entry; } private entry<k, v> getentry(k key) { return cache.get(key); } private static class entry<k, v> { entry<k, v> pre; entry<k, v> next; k key; v value; } @override public string tostring() { stringbuilder stringbuilder = new stringbuilder(); entry<k, v> entry = head; while (entry != null) { stringbuilder.append(string.format("%s:%s ", entry.key, entry.value)); entry = entry.next; } return stringbuilder.tostring(); } public static void main(string[] args) { lru2<integer, integer> lru2 = new lru2<>(5); lru2.put(1, 1); system.out.println(lru2); lru2.put(2, 2); system.out.println(lru2); lru2.put(3, 3); system.out.println(lru2); lru2.get(1); system.out.println(lru2); lru2.put(4, 4); lru2.put(5, 5); lru2.put(6, 6); system.out.println(lru2); }} |
运行结果：
fifo
fifo就是先进先出，可以使用linkedhashmap进行实现。
当第三个参数传入为false或者是默认的时候，就可以实现按插入顺序排序，就可以实现fifo缓存了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/** * constructs an empty <tt>linkedhashmap</tt> instance with the * specified initial capacity, load factor and ordering mode. * * @param initialcapacity the initial capacity * @param loadfactor the load factor * @param accessorder the ordering mode - <tt>true</tt> for * access-order, <tt>false</tt> for insertion-order * @throws illegalargumentexception if the initial capacity is negative * or the load factor is nonpositive */public linkedhashmap(int initialcapacity, float loadfactor, boolean accessorder) { super(initialcapacity, loadfactor); this.accessorder = accessorder;} |
实现代码跟上述使用linkedhashmap实现lru的代码基本一致，主要就是构造函数的传值有些不同。
|
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
|
import java.util.linkedhashmap;import java.util.map;import java.util.set;public class lru1<k, v> { private final int max_cache_size; private final float default_load_factory = 0.75f; linkedhashmap<k, v> map; public lru1(int cachesize) { max_cache_size = cachesize; int capacity = (int)math.ceil(max_cache_size / default_load_factory) + 1; /* * 第三个参数设置为true，代表linkedlist按访问顺序排序，可作为lru缓存 * 第三个参数设置为false，代表按插入顺序排序，可作为fifo缓存 */ map = new linkedhashmap<k, v>(capacity, default_load_factory, false) { @override protected boolean removeeldestentry(map.entry<k, v> eldest) { return size() > max_cache_size; } }; } public synchronized void put(k key, v value) { map.put(key, value); } public synchronized v get(k key) { return map.get(key); } public synchronized void remove(k key) { map.remove(key); } public synchronized set<map.entry<k, v>> getall() { return map.entryset(); } @override public string tostring() { stringbuilder stringbuilder = new stringbuilder(); for (map.entry<k, v> entry : map.entryset()) { stringbuilder.append(string.format("%s: %s ", entry.getkey(), entry.getvalue())); } return stringbuilder.tostring(); } public static void main(string[] args) { lru1<integer, integer> lru1 = new lru1<>(5); lru1.put(1, 1); lru1.put(2, 2); lru1.put(3, 3); system.out.println(lru1); lru1.get(1); system.out.println(lru1); lru1.put(4, 4); lru1.put(5, 5); lru1.put(6, 6); system.out.println(lru1); }} |
运行结果：
以上就是使用java实现这两种缓存的方式，从中可以看出，linkedhashmap实现缓存较为容易，因为底层函数对此已经有了支持，自己编写链表实现lru缓存也是借鉴了linkedhashmap中实现的思想。在java中不只是这两种数据结构可以实现缓存，比如concurrenthashmap、weakhashmap在某些场景下也是可以作为缓存的，到底用哪一种数据结构主要是看场景再进行选择，但是很多思想都是可以通用的。
原文链接：http://www.cnblogs.com/liuyang0/p/6664586.html
