本文通過對(duì)Apache Commons Collections 項(xiàng)目中LRUMap這個(gè)集合類的源代碼進(jìn)行詳細(xì)解讀，為幫助大家更好的了解這個(gè)集合類的實(shí)現(xiàn)原理以及使用如何該集合類。
首先介紹一下LRU算法. LRU是由Least Recently Used的首字母組成，表示最近最少使用的含義，一般使用在對(duì)象淘汰算法上。也是比較常見的一種淘汰算法。
LRUMap 則是實(shí)現(xiàn)的LRP算法的Map集合類，它繼承于AbstractLinkedMap 抽象類。LRUMap的使用說明如下：
LRUMap的初始化時(shí)需要指定最大集合元素個(gè)數(shù)，新增的元素個(gè)數(shù)大于允許的最大集合個(gè)數(shù)時(shí)，則會(huì)執(zhí)行LRU淘汰算法。所有的元素在LRUMap中會(huì)根據(jù)最近使用情況進(jìn)行排序。最近使用的會(huì)放在元素的最前面(LRUMap是通過鏈表來存儲(chǔ)元素內(nèi)容). 所以LRUMap進(jìn)行淘汰時(shí)只需要?jiǎng)h除鏈表最后一個(gè)即可（即header.after所指的元素對(duì)象）
那么那些操作會(huì)影響元素的使用情況：
1. put 當(dāng)新增加一個(gè)集合元素對(duì)象，則表示該對(duì)象是最近被訪問的
2. get 操作會(huì)把當(dāng)前訪問的元素對(duì)象作為最近被訪問的，會(huì)被移到鏈接表頭
注：當(dāng)執(zhí)行containsKey和containsValue操作時(shí)，不會(huì)影響元素的訪問情況。
LRUMap也是非線程安全。在多線程下使用可通過 Collections.synchronizedMap(Map)操作來保證線程安全。
LRUMap的一個(gè)簡單使用示例：
public static void main(String[] args) {
LRUMap lruMap = new LRUMap(2);
lruMap.put("a1", "1");
lruMap.put("a2", "2");
lruMap.get("a1");//mark as recent used
lruMap.put("a3", "3");
System.out.println(lruMap);
}
上面的示例，當(dāng)增加”a3”值時(shí)，會(huì)淘汰最近最少使用的”a2”, 最后輸出的結(jié)果為：
{a1=1, a3=3}
下面根據(jù)LRUMap的源碼來解讀一下LRUMap的實(shí)現(xiàn)原理
整體類圖
LRUMap類的關(guān)鍵代碼說明如下：
1. get操作
public Object get(Object key) {
LinkEntry entry = (LinkEntry) getEntry(key);
if (entry == null) {
return null;
}
moveToMRU(entry); //執(zhí)行LRU操作
return entry.getValue();
}
moveToMRU方法代碼如下：
protected void moveToMRU(LinkEntry entry) {
if (entry.after != header) {
modCount++;
// remove 從鏈接中移除當(dāng)前節(jié)點(diǎn)
entry.before.after = entry.after;
entry.after.before = entry.before;
// add first 把節(jié)點(diǎn)增加到鏈接頭部
entry.after = header;
entry.before = header.before;
header.before.after = entry;
header.before = entry;
} else if (entry == header) {
throw new IllegalStateException("Can't move header to MRU" +
" (please report this to commons-dev@jakarta.apache.org)");
}
}
2. put新增操作
由于繼承的AbstractLinkedMap，所以put操作會(huì)調(diào)用addMapping 方法，完整代碼如下：
protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
if (isFull()) {
LinkEntry reuse = header.after;
boolean removeLRUEntry = false;
if (scanUntilRemovable) {
while (reuse != header && reuse != null) {
if (removeLRU(reuse)) {
removeLRUEntry = true;
break;
}
reuse = reuse.after;
}
if (reuse == null) {
throw new IllegalStateException(
"Entry.after=null, header.after" + header.after + " header.before" + header.before +
" key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
" Please check that your keys are immutable, and that you have used synchronization properly." +
" If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
}
} else {
removeLRUEntry = removeLRU(reuse);
}
if (removeLRUEntry) {
if (reuse == null) {
throw new IllegalStateException(
"reuse=null, header.after=" + header.after + " header.before" + header.before +
" key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
" Please check that your keys are immutable, and that you have used synchronization properly." +
" If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
}
reuseMapping(reuse, hashIndex, hashCode, key, value);
} else {
super.addMapping(hashIndex, hashCode, key, value);
}
} else {
super.addMapping(hashIndex, hashCode, key, value);
}
}
當(dāng)集合的個(gè)數(shù)超過指定的最大個(gè)數(shù)時(shí)，會(huì)調(diào)用 reuseMapping函數(shù)，把要?jiǎng)h除的對(duì)象的key和value更新為新加入的值，并再次加入到鏈接表中，并重新排定次序。
reuseMapping函數(shù)代碼如下：
protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) {
// find the entry before the entry specified in the hash table
// remember that the parameters (except the first) refer to the new entry,
// not the old one
try {
int removeIndex = hashIndex(entry.hashCode, data.length);
HashEntry[] tmp = data; // may protect against some sync issues
HashEntry loop = tmp[removeIndex];
HashEntry previous = null;
while (loop != entry && loop != null) {
previous = loop;
loop = loop.next;
}
if (loop == null) {
throw new IllegalStateException(
"Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous +
" key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
" Please check that your keys are immutable, and that you have used synchronization properly." +
" If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
}
// reuse the entry
modCount++;
removeEntry(entry, removeIndex, previous);
reuseEntry(entry, hashIndex, hashCode, key, value);
addEntry(entry, hashIndex);
} catch (NullPointerException ex) {
throw new IllegalStateException(
"NPE, entry=" + entry + " entryIsHeader=" + (entry==header) +
" key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
" Please check that your keys are immutable, and that you have used synchronization properly." +
" If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
}
}
上面的代碼中：
removeEntry 方法是刪除最近最少使用的節(jié)點(diǎn)在鏈接中的引用
reuseEntry方法則把該節(jié)點(diǎn)的key和value賦新加入的節(jié)點(diǎn)的key和value值
addEntry 方法則把該節(jié)點(diǎn)加入到鏈接表，并保障相關(guān)的鏈接順序
/**
* Adds an entry into this map, maintaining insertion order.
* <p>
* This implementation adds the entry to the data storage table and
* to the end of the linked list.
*
* @param entry the entry to add
* @param hashIndex the index into the data array to store at
*/
protected void addEntry(HashEntry entry, int hashIndex) {
LinkEntry link = (LinkEntry) entry;
link.after = header;
link.before = header.before;
header.before.after = link;
header.before = link;
data[hashIndex] = entry;
}
LRUMap的主要源碼實(shí)現(xiàn)就解讀到這里，實(shí)現(xiàn)思路還是比較好理解的。
LRUMap的使用場(chǎng)景會(huì)比較多，例如可以很方便的幫我們實(shí)現(xiàn)基于內(nèi)存的 LRU 緩存服務(wù)實(shí)現(xiàn)。