面试题目:手写一个LRU算法实现

一、常见的内存淘汰算法

  • FIFO  先进先出

    • 在这种淘汰算法中,先进⼊缓存的会先被淘汰

    • 命中率很低

  • LRU

    • Least recently used,最近最少使⽤get

    • 根据数据的历史访问记录来进⾏淘汰数据,其核⼼思想是“如果数据最近被访问过,那么将来被访问的⼏率也更⾼”

    • LRU算法原理剖析

  • LFU   

    • Least Frequently Used
    • 算法根据数据的历史访问频率来淘汰数据,其核⼼思想是“如果数据过去被访问多次,那么将来被访问的频率也更⾼”

    • LFU算法原理剖析

      • 新加⼊数据插⼊到队列尾部(因为引⽤计数为1)

      • 队列中的数据被访问后,引⽤计数增加,队列重新排序;

      • 当需要淘汰数据时,将已经排序的列表最后的数据块删除。

 

  • LFU的缺点
    • 复杂度
    • 存储成本
    • 尾部容易被淘汰

二、手写LRU算法实现

利用了LinkedHashMap双向链表插入可排序

@Slf4j
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private int cacheSize;

    public LRUCache(int cacheSize) {
        super(16, 0.75f, true);
        this.cacheSize = cacheSize;
    }

    @Override
    public synchronized V get(Object key) {
        return super.get(key);
    }

    @Override
    public synchronized V put(K key, V value) {
        return super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        boolean f = size() > cacheSize;
        if (f) {
            log.info("LRUCache清除第三方密钥缓存Key:[{}]", eldest.getKey());
        }
        return f;
    }

    public static void main(String[] args) {
        LRUCache<String, Object> cache = new LRUCache<>(5);
        cache.put("A","A");
        cache.put("B","B");
        cache.put("C","C");
        cache.put("D","D");
        cache.put("E","E");
        System.out.println("初始化:" + cache.keySet());
        System.out.println("访问值:" + cache.get("C"));
        System.out.println("访问C后:" + cache.keySet());
        System.out.println("PUT F后:" + cache.put("F","F"));
        System.out.println(cache.keySet());
    }

}

main函数执行效果:

三、注意事项

LinkedHashMap有五个构造函数

//使用父类中的构造,初始化容量和加载因子,该初始化容量是指数组大小。
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
//一个参数的构造
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
//无参构造
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }
//这个不用多说,用来接受map类型的值转换为LinkedHashMap
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }
//真正有点特殊的就是这个,多了一个参数accessOrder。存储顺序,LinkedHashMap关键的参数之一就在这个,
  //true:指定迭代的顺序是按照访问顺序(近期访问最少到近期访问最多的元素)来迭代的。 false:指定迭代的顺序是按照插入顺序迭代,也就是通过插入元素的顺序来迭代所有元素
//如果你想指定访问顺序,那么就只能使用该构造方法,其他三个构造方法默认使用插入顺序。
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
View Code

  参数accessOrder。存储顺序,LinkedHashMap关键的参数之一就在这个, true:指定迭代的顺序是按照访问顺序(近期访问最少到近期访问最多的元素)来迭代的。 false:指定迭代的顺序是按照插入顺序迭代,也就是通过插入元素的顺序来迭代所有元素。

  如果你想指定访问顺序,那么就只能使用该构造方法,其他三个构造方法默认使用插入顺序。

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

LinkedHashMap是非线程安全的,需要加互斥锁解决并发问题。

四、思考

  需要根据应用场景确定cacheSize大小,如果实际缓存数量过小,会导致缓存中的数据长期得不到刷新,为防止这种或偶发情况的发生,可配合定时任务如起一个newSingleThreadScheduledExecutor,将上面存储的value修改封装为一个对象,里面增加一个时间戳储存,每次访问实时更新,定时扫描该队列将最近30分钟未访问的key删除;还需增加一个初始进入队列的历史时间记录,将超过1小时的数据清除。

 


文章标签:

原文连接:https://www.cnblogs.com/better-farther-world2099/p/16083561.html

相关推荐

[原创]移动相机九点标定工具原理及实现(包涵部分源码)

34个图片压缩工具集合,包含在线压缩和CLI工具

[原创]一种自动化九点标定工具原理(包涵部分源码)

接口文档管理工具,选yapi 还是 Apifox? 这里列出了两款软件的深度分析,看完再下载不迟。

使用ComposeDesktop开发一款桌面端多功能APK工具

这个好用的办公网优化工具,官宣免费了

Sunmao——一个开发低代码工具的开源框架

前端必备 | 3分钟白嫖我常用的免费效率工具!

好用的办公网优化工具OneDNS

KusionStack 开源|Kusion 模型库和工具链的探索实践

从“AI玩具”到“创作工具”的云原生改造之路

LabelImg(目标检测标注工具)的安装与使用教程

效率低?响应慢?报表工具痛点及其解决方案

接口文档进化图鉴,有些古早接口文档工具,你可能都没用过

用 JavaScript 复原何同学B站头图、对前端构建工具的一些理解、弹幕的常规设计与实现 丨酱酱的下午茶第31期

关于目前流行的 Redis 可视化管理工具的详细评测

【云原生 • DevOps】一文掌握持续集成工具 Jenkins

【一起学Rust】Rust包管理工具Cargo初步了解

窥探性能的接口测试工具,性能优化的开端

照妖镜:一个工具的自我超越