缓存淘汰算法--LRU算法

一个用hash表作为底层结构的数据库，当然少不了缓存淘汰算法。

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

LRU.png

1.新数据插入到链表头部；
2.每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3.当链表满的时候，将链表尾部的数据丢弃。

过程如下：

LRU

1.最开始时，内存空间是空的，因此依次进入A、B、C是没有问题的
当加入D时，就出现了问题，内存空间不够了，因此根据LRU算法，内存空间中A待的时间最为久远，选择A,将其淘汰
2.当再次引用B时，内存空间中的B又处于活跃状态，而C则变成了内存空间中，近段时间最久未使用的
3.当再次向内存空间加入E时，这时内存空间又不足了，选择在内存空间中待的最久的C将其淘汰出内存，这时的内存空间存放的对象就是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：访问顺序；false：插入顺序
        super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
        this.maxCapacity = maxCapacity;
    }

    /**
     * 默认的removeEldestEntry方法是返回false的，也就是不会进行删除，而是进行扩容
     *
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }
}

测试：

   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);
    }

结果：

{1=A, 2=B, 3=C, 4=D, 5=E}
{3=C, 4=D, 5=E, 1=A, 6=F}