什么是LRU算法
????LRU算法的全稱Least Recently Used孝鹊。即最近最少使用。
????LRU算法是內(nèi)存管理的一種頁面置換算法，對于在內(nèi)存中但是又不用的數(shù)據(jù)塊叫做LRU挺狰，操作系統(tǒng)會將那些數(shù)據(jù)數(shù)據(jù)LRU而將其移除內(nèi)存騰出空間來加載其他數(shù)據(jù)（以上來自百度百科）。
LRU算法的實現(xiàn)
????LRU算法通常是基于雙向鏈表來實現(xiàn)的壮不，下面我們一起看一下雙向鏈表是如何實現(xiàn)LRU算法的蔼夜。
image.png
????如上圖所示判呕，我們定義了一個雙向鏈表尘喝。對鏈表中元素的操作不外乎四種：get磁浇，put，remove朽褪，update置吓。其中remove操作，刪除鏈表中的一個元素缔赠，不會影響鏈表中現(xiàn)有的排序情況衍锚，而update和put操作可以看作是同一種操作。所以我們主要看get嗤堰，put操作對鏈表中元素的影響戴质。
image.png
image.png
????以上我們看到當在雙向鏈表中發(fā)生get和put操作時，鏈表內(nèi)元素的變化情況踢匣。下面再來看一下基于LinkedHashMap的LRU算法是如何實現(xiàn)的置森。
基于LinkedHashMap的LRU算法實現(xiàn)
????LinkedHashMap中LRU算法的實現(xiàn)主要依賴的幾個方法。
- afterNodeInsertion(boolean evict)
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// first = head 這一步是關鍵符糊，從if的判斷條件中可以看出，在鏈表的頭結點head存在的情況下呛凶，會將head賦值給first男娄，然后交給removeEldestEntry(first)執(zhí)行
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 該方法移除的是鏈表的頭結點
removeNode(hash(key), key, null, false, true);
}
}
- afterNodeAccess(Node<K,V> e)
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 執(zhí)行移動操作的前提是accessOrder和要移動的元素e != tail，這是為什么呢漾稀，剛開始看到這樣的代碼我也疑惑模闲，說好的移動到鏈表的頭部呢？撓頭
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;
}
}
- removeEldestEntry(Map.Entry<K,V> eldest)
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
// 默認返回false尸折，也就是不移除最老的元素，我們需要重新改寫該方法殷蛇，在當前容量大于預設的最大容量時实夹，移除最老元素。
return false;
}
????介紹完幾個關鍵方法之后粒梦，我們來從整體的角度看一下這幾個方法在整個流程中的作用亮航。
image.png
image.png
Demo
public class LruCache {
private Map<Object, Object> cache;
LruCache(int size) {
// 初始化LinkedHashMap三個參數(shù)，容量匀们，負載引子缴淋，accessOrder
this.cache = new LinkedHashMap<Object, Object>(size, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
// 比較當前LinkedHashMap中的節(jié)點數(shù)量與允許存放最大數(shù)量的比較
return super.size() > size;
}
};
}
public Object put(Object key, Object value) {
return cache.put(key, value);
}
public Object get(Object key) {
return cache.get(key);
}
}
