缓存
缓存是一种提高应用程序性能的简单方法，应用程序从磁盘或数据库表中读取数据，但可能会多次重新读取相同的数据。大量的IO操作必然会导致应用程序性能降低，解决这个问题的简单办法就是，数据使用后一段时间内不丢弃，将其保存在内存中，以便减少不必要的IO操作。
LRU 缓存
LRU (Least Recently Used)，即最久未使用算法。LRU 缓存就是选择最长时间未被使用的数据移除。
FIFO 缓存
FIFO (First In First Out)，即先进先出算法。FIFO 缓存就是选择最先调入缓存数据进行替换。
基于 LinkedHashMap 的缓存
对一个 Cache 来说最常用的操作有三种：插入 (insert)、替换 (replace)、查找(lookup)。
同时缓存能够自动丢弃一段时间未访问的数据，以限制缓存空间的无限增长。
java.util.LinkedHashMap 已经实现了顺序存储，默认情况下按照元素的添加顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面，同时它包括自动删除数据的方法（如下），该方法能够让我们不用关心缓存的清除。1
2
3protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
LinkedHashMap 构造函数如下：1
2
3
4public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkedHashMap 元素大于 capacity * loadFactor 的时候，就会自动进行两倍扩容，为使缓存大小不会进行自动扩容，初始化大小（initialCapacity）设置为 (CACHE_SIZE / loadFactor) + 1。
负载因子（loadFactor）选择默认值 0.75。
当参数 accessOrder 为 true 时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面；当参数 accessOrder 为 false 时，即可实现先进先出。
下面是 LRU 缓存和 FIFO 缓存的实现方式，在公共方法上要加上 synchronized 关键字，防止线程同步问题：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
104import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
/**
* 原生 Java 本地 LRU、FIFO 缓存，LinkedHashMap 实现
*
* @author Leaves
* @version 1.0.0
* @date 2018/8/10
*/
public class LinkedHashMapCache<K, V> {
private final int CACHE_SIZE;
private static final float LOAD_FACTORY = 0.75f;
private LinkedHashMap<K, V> map;
/**
* @param cacheSize 缓存大小
* @param accessOrder true LRU, false FIFO
*/
public LinkedHashMapCache(int cacheSize, boolean accessOrder) {
CACHE_SIZE = cacheSize;
//LinkedHashMap 元素大于 capacity * loadFactor 的时候，就会自动进行两倍扩容
//为使缓存大小不会进行自动扩容，初始化大小设置为 (CACHE_SIZE / loadFactor) + 1
int initialCapacity = (int) Math.ceil(CACHE_SIZE / LOAD_FACTORY) + 1;
map = new LinkedHashMap<K, V>(initialCapacity, LOAD_FACTORY, accessOrder) {
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > 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 clear() {
map.clear();
}
public synchronized int size() {
return map.size();
}
public synchronized void remove(K key) {
map.remove(key);
}
public synchronized Set<Map.Entry<K, V>> getAll() {
return map.entrySet();
}
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (Map.Entry<K, V> entry : map.entrySet()) {
stringBuilder.append(String.format("%s -> %s\n", entry.getKey(), entry.getValue()));
}
return stringBuilder.toString();
}
public static void main(String[] args) {
System.out.println("========== LRU ==========");
Long start1 = System.currentTimeMillis();
LinkedHashMapCache<Integer, String> lru = new LinkedHashMapCache<>(5, true);
lru.put(1, "1");
lru.put(2, "1");
lru.put(3, "1");
lru.put(4, "1");
lru.put(5, "1");
System.out.println(lru.toString());
lru.put(11, "2");
lru.get(2);
lru.put(12, "3");
lru.get(4);
System.out.println(lru.toString());
System.out.println(System.currentTimeMillis() - start1);
System.out.println("========== FIFO ==========");
Long start2 = System.currentTimeMillis();
LinkedHashMapCache<Integer, String> fifo = new LinkedHashMapCache<>(5, false);
fifo.put(1, "1");
fifo.put(2, "1");
fifo.put(3, "1");
fifo.put(4, "1");
fifo.put(5, "1");
System.out.println(fifo.toString());
fifo.put(11, "2");
fifo.get(2);
fifo.put(12, "3");
fifo.get(4);
System.out.println(fifo.toString());
System.out.println(System.currentTimeMillis() - start2);
}
}
参考与感谢
Pete Ford : How to set up a simple LRU cache using LinkedHashMap
