Java中LRU的實現

NO IMAGE

前言

LRU,全稱Least Recently Used,即最近最久未使用算法,用於操作系統的頁面置換算法,以及一些常見的框架。其原理實質就是當需要淘汰數據時,會選擇那些最近沒有使用過的數據進行淘汰,換句話說,當某數據被訪問時,就把其移動到淘汰隊列的隊首(也就是最不會被淘汰的位置)

實現

基於這樣的原則,我們就可以著手實現了。不過Java已經為我們提供了一個現成的模板,我們站在巨人的肩膀上,可以參考一下Java是如何實現LRU功能的

LinkedHashMap

在LinkedHashMap中,有一個很少用到的構造函數:

    public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

其中accessOrder這一屬性,在其他的構造函數中是默認為false的,如果我們通過該構造函數將其設為true之後,就實現了LRU功能,下面的程序簡單了做了下演示:

    public static void main(String[] args) {
int cacheSize = 3;
// 最大容量 = (緩存大小 / 負載因子)+ 1,保證不會觸發自動擴容
LinkedHashMap<String, String> cache = new LinkedHashMap<String, String>(
(int)(cacheSize/ 0.75f) + 1, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > cacheSize;
}
};
cache.put("1", "a");
cache.put("2", "b");
cache.put("3", "c");
// head => "1" => "2" => "3" => null
// put已存在的值,和get方法是一樣的效果
cache.put("1", "a");
// head => "2" => "3" => "1" => null;
cache.put("4", "d");
// head => "3" => "1" => "4" => null;
for (String key: cache.keySet()) {
System.out.println(key);
}
}

其實還有很重要的一點,就是需要重寫removeEldestEntry()這一方法,默認是返回false的,當返回true時,會移除最久沒有使用的節點,所以我們要做的,就是當容量達到緩存限制時,移除LRU算法判定的最近最久未使用節點

可以看到,我們依次插入節點1、2、3後,如果此時再插入節點4,就會導致removeEldestEntry()返回為true,然後移除隊首節點,即節點1。但是我們這裡由於中間重複插入了一次節點1,所以會判斷節點1是“經常訪問的節點”,所以節點1被提到鏈表最後,隊首節點就變成了節點2,當容量超過限制時,會把節點2移除

實現原理

探索LinkedHashMap中LRU的實現原理,我們就要追溯到HashMap中的putVal方法,這個方法最後觸發了一個回調函數:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// ...
if (e != null) { // existing mapping for key
// ...
afterNodeAccess(e);
return oldValue;
}
}
afterNodeInsertion(evict);
return null;
}

putVal()方法在插入後會觸發方法的回調,有兩種情況:

  • 如果插入的值已存在,則觸發afterNodeAccess(e)
  • 如果插入的值不存在,則觸發afterNodeInsertion(evict)

其中,變量e是“撞車”的節點,變量evict在子類不重寫put()方法的情況下是默認為true的,所以我們就把它當作常量來看

然後我們回到,LinkedHashMap中,來看這個兩個鉤子方法(HashMap中這兩個方法實現均為空):

    void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry<K,V> first;
// 以下情況滿足時,調用removeNode移除最久未使用的節點:
//      1. evict為true
//      2. 頭結點不為空
//      3. 符合移除條件:removeEldestEntry返回true
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
// 開啟LRU模式,且訪問的節點不是尾節點,則將被訪問的節點置於鏈表尾
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;
}
}

顯而易見,afterNodeInsertion負責在插入之後判斷是否需要移除最近最久未使用的節點(即鏈表頭節點),afterNodeAccess負責在訪問某節點之後,將該節點移動到鏈表尾

afterNodeAccess中,因為要考慮到各種特殊情況,而且是一個帶有頭尾節點的雙向鏈表,所以情況判斷比較複雜,實際上就是將指定節點移動到隊尾,如果自己想實現一個類似的功能可以不做的這麼複雜

總結

一般來說,如果想做一個LRU算法實現的話,LinkedHashMap就能滿足需要了。要是想自己實現的話,這裡提供一個實現的思路:

  1. 用鏈表存儲數據
  2. 一個節點被訪問後,將其置於鏈表尾
  3. 鏈表頭結點就是最近最久未使用的節點,直接移除即可

相關文章

隨便分享點不那麼常規的面試題(二)

隨便分享點不那麼常規的面試題(一)

淺談零拷貝機制

淺談ForkJoinPool