現在軟件或者網頁的并發量越來越大了，大量請求直接操作數據庫會對數據庫造成很大的壓力，處理大量連接和請求就會需要很長時間，但是實際中百分之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
