一個(gè)用hash表作為底層結(jié)構(gòu)的數(shù)據(jù)庫(kù)露筒，當(dāng)然少不了緩存淘汰算法累铅。
LRU（Least recently used立宜，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問(wèn)記錄來(lái)進(jìn)行淘汰數(shù)據(jù)藕各，其核心思想是“如果數(shù)據(jù)最近被訪問(wèn)過(guò)舆瘪，那么將來(lái)被訪問(wèn)的幾率也更高”片效。
1.新數(shù)據(jù)插入到鏈表頭部；
2.每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問(wèn)）英古，則將數(shù)據(jù)移到鏈表頭部淀衣；
3.當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄召调。
過(guò)程如下：
1.最開始時(shí)膨桥，內(nèi)存空間是空的，因此依次進(jìn)入A唠叛、B只嚣、C是沒(méi)有問(wèn)題的
當(dāng)加入D時(shí)，就出現(xiàn)了問(wèn)題艺沼，內(nèi)存空間不夠了册舞，因此根據(jù)LRU算法，內(nèi)存空間中A待的時(shí)間最為久遠(yuǎn)障般，選擇A,將其淘汰
2.當(dāng)再次引用B時(shí)调鲸，內(nèi)存空間中的B又處于活躍狀態(tài)，而C則變成了內(nèi)存空間中挽荡，近段時(shí)間最久未使用的
3.當(dāng)再次向內(nèi)存空間加入E時(shí)藐石，這時(shí)內(nèi)存空間又不足了，選擇在內(nèi)存空間中待的最久的C將其淘汰出內(nèi)存定拟，這時(shí)的內(nèi)存空間存放的對(duì)象就是E->B->D
附上：java算法
import java.util.LinkedHashMap;
/**
* @ClassName: LRULinkedHashMap
* @Description:
* @Author: wugongzi
* @Date: 2021/9/4 16:48
* @Version: 1.0
*/
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
// 緩存最大容量
private final int maxCapacity;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
public LRULinkedHashMap(int maxCapacity) {
// accessOrder true：訪問(wèn)順序于微；false：插入順序
super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
this.maxCapacity = maxCapacity;
}
/**
* 默認(rèn)的removeEldestEntry方法是返回false的，也就是不會(huì)進(jìn)行刪除，而是進(jìn)行擴(kuò)容
*
* @param eldest
* @return
*/
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
return size() > maxCapacity;
}
}
測(cè)試：
public static void main(String[] args) {
LRULinkedHashMap<String, String> linkedHashMap = new LRULinkedHashMap<>(5);
linkedHashMap.put("1","A");
linkedHashMap.put("2","B");
linkedHashMap.put("3","C");
linkedHashMap.put("4","D");
linkedHashMap.put("5","E");
System.out.println(linkedHashMap);
linkedHashMap.get("1");
linkedHashMap.put("6","F");
System.out.println(linkedHashMap);
}
結(jié)果：
{1=A, 2=B, 3=C, 4=D, 5=E}
{3=C, 4=D, 5=E, 1=A, 6=F}
