本文將介紹使用java語(yǔ)言實(shí)現(xiàn)一個(gè)對(duì)象緩存池挖滤。一步步的實(shí)現(xiàn)包括高速命中，固定大小的緩存隊(duì)列等功能浅役。
這一期我們終于能夠動(dòng)手編寫(xiě)一些代碼斩松，使用java來(lái)實(shí)現(xiàn)一個(gè)在內(nèi)存中的對(duì)象緩存池。
不限大小的高速緩存池
最開(kāi)始的需求是實(shí)現(xiàn)一個(gè)能夠在單線程模式下觉既，根據(jù)唯一主鍵key來(lái)緩存對(duì)象的功能惧盹。
對(duì)于java的集合類來(lái)說(shuō)，能夠得到近似的存取時(shí)間復(fù)雜度為O(1)的數(shù)據(jù)結(jié)構(gòu)就是HashMap了瞪讼，此處我們不再講述其數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)钧椰，簡(jiǎn)單的一段代碼實(shí)現(xiàn)此功能：
public class ObjectCache {
private Map<String, Object> cache;
public ObjectCache() {
cache = new HashMap<>();
}
public void put(String key, Object value) {
cache.put(key, value);
}
public Object get(String key) {
return cache.get(key);
}
}
限制大小的高速緩存池
JVM的堆內(nèi)存大小是有限的，如果一個(gè)緩存沒(méi)有退出機(jī)制符欠，永遠(yuǎn)只能往里面加入對(duì)象的話嫡霞，那么最終就會(huì)導(dǎo)致堆內(nèi)存溢出錯(cuò)誤。所以一般來(lái)說(shuō)我們都要限制緩存池的大小希柿，以免內(nèi)存耗盡诊沪。
那么當(dāng)緩存對(duì)象達(dá)到最大限制大小后，用什么機(jī)制來(lái)淘汰過(guò)期的緩存對(duì)象呢曾撤？常用的有如下策略：
- FIFO
此策略根據(jù)寫(xiě)入的時(shí)間排序端姚，當(dāng)需要淘汰時(shí)，首先淘汰最早寫(xiě)入的對(duì)象挤悉。 - LRU
此策略根據(jù)最后讀取的時(shí)間排序渐裸，當(dāng)需要淘汰時(shí)，首先淘汰最后讀取時(shí)間最早的對(duì)象装悲。 - LFU
此策略根據(jù)一段時(shí)間窗口內(nèi)昏鹃，總的讀取次數(shù)排序，當(dāng)需要淘汰時(shí)衅斩，首先淘汰時(shí)間窗口內(nèi)讀取次數(shù)最少的對(duì)象盆顾。
其中LFU實(shí)現(xiàn)比較復(fù)雜，需要使用滑窗計(jì)數(shù)器來(lái)幫助實(shí)現(xiàn)畏梆，后續(xù)會(huì)單獨(dú)一篇文章來(lái)介紹此算法。這次我們先來(lái)了解比較簡(jiǎn)單的FIFO和LRU算法的實(shí)現(xiàn)。
我們最開(kāi)始使用的HashMap是無(wú)序的奠涌，所以無(wú)法單獨(dú)來(lái)實(shí)現(xiàn)讀取或者寫(xiě)入的排序宪巨。我們考慮此場(chǎng)景，F(xiàn)IFO需要每次寫(xiě)入或者更新的時(shí)候都改變排序溜畅，而LRU每次讀取的時(shí)候要改變排序捏卓，所以我們就需要一個(gè)能夠排序的，而且很快速改變某個(gè)節(jié)點(diǎn)位置的數(shù)據(jù)結(jié)構(gòu)慈格。那么當(dāng)然我們會(huì)想到LinkedList鏈表數(shù)據(jù)結(jié)構(gòu)怠晴，其插入節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)且能夠保持節(jié)點(diǎn)次序，但是單獨(dú)的LinkedList的查詢時(shí)間復(fù)雜度又是O(N)浴捆，超出我們預(yù)期蒜田。所以此處我們需要將其結(jié)合使用，在使用HashMap提供高速查詢寫(xiě)入的同時(shí)选泻，又使用LinkedList來(lái)維護(hù)其插入或者最后讀取的次序冲粤，同時(shí)我們?cè)贖ashMap和LinkedList里維護(hù)同一個(gè)對(duì)象的引用，這樣整體的存儲(chǔ)空間保持基本不變页眯。
其實(shí)JDK在1.7之后已經(jīng)為我們提供了這樣的數(shù)據(jù)結(jié)構(gòu)：java.util.LinkedHashMap<K,V>
LinkedHashMap直接繼承自HashMap類梯捕，同時(shí)在內(nèi)部維護(hù)了一個(gè)雙向鏈表，其實(shí)現(xiàn)為：
可以看到其內(nèi)部的鏈表類LinkedHashMap.Entry繼承自HashMap.Node窝撵，同時(shí)也實(shí)現(xiàn)了Map.Entry接口傀顾，這樣就能在直接在鏈表中使用HashMap中的Node對(duì)象，從而保持同一個(gè)對(duì)象引用碌奉。
在LinkedHashMap.Entry類中短曾，其before和after屬性分別指向當(dāng)前節(jié)點(diǎn)的前節(jié)點(diǎn)和后節(jié)點(diǎn)，而LinkedHashMap中也通過(guò)屬性head和tail維護(hù)了此鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)：
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
LinkedHashMap通過(guò)重寫(xiě)了HashMap中創(chuàng)建節(jié)點(diǎn)的一些方法來(lái)在新增節(jié)點(diǎn)時(shí)維護(hù)鏈表數(shù)據(jù)：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
LinkedHashMap.Entry<K,V> t =
new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
這里可以看到道批，在HashMap的EntrySet數(shù)組中错英，根據(jù)hash碰撞的命中數(shù)量，采用鏈表和紅黑樹(shù)兩種節(jié)點(diǎn)結(jié)構(gòu)（JDK1.8以后）隆豹，分別用newNode和newTreeNode插入節(jié)點(diǎn)椭岩，每次都把新的節(jié)點(diǎn)放在LinkedHashMap雙向鏈表的最末尾。
同時(shí)我們來(lái)看HashMap中璃赡，在1.7之后為了LinkedHashMap提供了三個(gè)回調(diào)方法判哥，其在HashMap中的默認(rèn)實(shí)現(xiàn)為空：
// Callbacks to allow LinkedHashMap post-actions
// 訪問(wèn)節(jié)點(diǎn)的值后調(diào)用
void afterNodeAccess(Node<K,V> p) { }
// 插入新的節(jié)點(diǎn)后調(diào)用
void afterNodeInsertion(boolean evict) { }
// 刪除節(jié)點(diǎn)后調(diào)用
void afterNodeRemoval(Node<K,V> p) { }
而LinkedHashMap在繼承HashMap后重寫(xiě)這三個(gè)方法：
// 刪除節(jié)點(diǎn)后被HashMap回調(diào)
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
// 插入新的節(jié)點(diǎn)后被HashMap回調(diào)
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// 訪問(wèn)節(jié)點(diǎn)的值后被HashMap回調(diào)
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
可以看到其中主要就是一些經(jīng)典的鏈表操作，更新其次序碉考；我們注意到accessOrder屬性塌计，其為true后才會(huì)在訪問(wèn)節(jié)點(diǎn)對(duì)象后更新其次序，我們來(lái)看其在LinkedHashMap中的定義：
/**
* The iteration ordering method for this linked hash map: true
* for access-order, false for insertion-order.
*
* @serial
*/
final boolean accessOrder;
也就是當(dāng)accessOrder為true時(shí)鏈表采用訪問(wèn)次序排序侯谁，為false時(shí)采用插入次序排序锌仅。其值在LinkedHashMap的構(gòu)造函數(shù)中寫(xiě)入：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
……
}
我們?cè)賮?lái)看afterNodeInsertion回調(diào)方法中調(diào)用的方法：removeEldestEntry章钾，其默認(rèn)實(shí)現(xiàn)永遠(yuǎn)返回false，那么就是說(shuō)其實(shí)LinkedHashMap不會(huì)自動(dòng)刪除過(guò)期節(jié)點(diǎn)热芹，需要我們自己繼承后實(shí)現(xiàn)贱傀。
好了，既然如此伊脓，我們就來(lái)繼承它來(lái)實(shí)現(xiàn)一個(gè)固定大小的對(duì)象緩存池吧：
public class FixedSizeCache<K, V> extends LinkedHashMap<K, V> {
/**
* 緩存池的最大大小
*/
private int maxSize = 0;
public FixedSizeCache(int initialCapacity,
float loadFactor,
boolean accessOrder,
int maxSize) {
super(initialCapacity, loadFactor, accessOrder);
this.maxSize = maxSize;
}
/**
* 當(dāng)前緩存大小已經(jīng)大于maxSize后返回true府寒，在新增節(jié)點(diǎn)后會(huì)刪除一個(gè)最老的節(jié)點(diǎn)
*
* @param eldest
* @return
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > maxSize;
}
}
好了，如此簡(jiǎn)單报腔，當(dāng)accessOrder為true時(shí)就是一個(gè)LRU緩存池株搔，當(dāng)為false時(shí)就是一個(gè)FIFO緩存池。當(dāng)然此緩存池不保證線程安全纯蛾，只能在單線程下使用了纤房。
