面试高频考题——手撸一个 LRU 算法!

简介: 今天给大家讲一道面试中经常容易遇到的一道题:“手写一个 LRU 算法”。

今天给大家讲一道面试中经常容易遇到的一道题:“手写一个 LRU 算法”


LRU 就是 Least Recently Used 的缩写,翻译过来就是“最近最少使用”。 也就是说 LRU 算法会将最近最少用的缓存移除,让给最新使用的缓存。这是非常常见的一个缓存淘汰策略


利用好 LRU 算法,我们能够提高对热点数据的缓存效率,进而提升缓存服务的内存使用率。


那么如何实现呢?


其实,通过缓存的 key 获取其对应的缓存,我们应该能想到用哈希表来实现,毕竟这是一个键值对结构,可以在 O(1) 时间内获取 key 对应的缓存值。


但是,哈希表本身是无序的,因此,我们还需要一个类似于队列的数据结构来记录访问的先后顺序,将最近访问的数据放在头部(如下图),移除最后一项数据(最旧),我们可以用双向链表来实现数据的增删以及顺序的调整。


36.png


因此,我们结合“哈希表 + 双向链表”来实现 LRU 算法。其中:


双向链表按照被使用的顺序存储 kv 键值对,靠近头部的 kv 键值对是最近使用的,而靠近尾部的键值对是最久未使用的。

哈希表通过缓存的 key 映射到双向链表中的位置。我们可以在 O(1) 时间内定位到缓存的 key 所对应的 value 在链表中的位置。


37.png


对于 get 操作,判断 key 是否存在哈希表中:


若不存在,返回 -1。

若存在,则 key 对应的节点 node 是最近使用的节点。将该节点移动到双向链表的头部,最后返回该节点的值即可。


对于 put 操作,同样先判断 key 是否存在哈希表中:


若不存在,则创建一个新的 node 节点,放入哈希表中。然后在双向链表的头部添加该节点。接着判断双向链表节点数是否超过 capacity。若超过,则删除双向链表的尾部节点,并且删除哈希表中对应的项。

若存在,则更新 node 节点的值,然后该节点移动到双向链表的头部。


双向链表节点(哈希表的 value)的结构如下:


class Node {    int key;    int value;    Node prev;    Node next;    Node() {    }    Node(int key, int value) {        this.key = key;        this.value = value;    }}


你可能会问,哈希表的 value 为何还要存放 key?


这是因为,双向链表有一个删除尾节点的操作。我们定位到双向链表的尾节点,在链表中删除之后,还要找到该尾节点在哈希表中的位置,因此需要根据 value 中存放的 key,定位到哈希表的数据项,然后将其删除。


以下是 Java 版本代码的完整实现。


class LRUCache {    class Node {        int key;        int value;        Node prev;        Node next;        Node() {        }        Node(int key, int value) {            this.key = key;            this.value = value;        }    }    private int size;    private int capacity;    private Map<Integer, Node> cache;    /* 虚拟头节点 */    private Node head;    /* 虚拟尾节点 */    private Node tail;    public LRUCache(int capacity) {        this.size = 0;        this.capacity = capacity;        cache = new HashMap<>();        head = new Node();        tail = new Node();        head.next = tail;        tail.prev = head;    }    public int get(int key) {        Node node = cache.get(key);        if (node == null) {            return -1;        }        // 将最近这次访问的数据移到头部        moveToHead(node);        return node.value;    }    public void put(int key, int value) {        Node node = cache.get(key);        if (node == null) {            Node newNode = new Node(key, value);            cache.put(key, newNode);            // 将最近新增的数据放到头部            addToHead(newNode);            ++size;            // 若数据量超过设定的最大容量,移除尾部(最不常访问)的节点数据            if (size > capacity) {                Node tail = removeTail();                // 缓存淘汰,移除尾部节点数据                cache.remove(tail.key);                --size;            }        } else {            node.value = value;            moveToHead(node);        }    }    private void moveToHead(Node node) {        removeNode(node);        addToHead(node);    }    private void removeNode(Node node) {        node.prev.next = node.next;        node.next.prev = node.prev;    }    private void addToHead(Node node) {        node.next = head.next;        head.next = node;        node.next.prev = node;        node.prev = head;    }    private Node removeTail() {        Node node = tail.prev;        removeNode(node);        return node;    }}


目录
相关文章
|
2月前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
这篇文章是关于Java面试中Redis相关问题的笔记,包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
|
12天前
|
机器学习/深度学习 JavaScript 算法
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
|
2月前
|
缓存 算法 前端开发
深入理解缓存淘汰策略:LRU和LFU算法的解析与应用
【8月更文挑战第25天】在计算机科学领域,高效管理资源对于提升系统性能至关重要。内存缓存作为一种加速数据读取的有效方法,其管理策略直接影响整体性能。本文重点介绍两种常用的缓存淘汰算法:LRU(最近最少使用)和LFU(最不经常使用)。LRU算法依据数据最近是否被访问来进行淘汰决策;而LFU算法则根据数据的访问频率做出判断。这两种算法各有特点,适用于不同的应用场景。通过深入分析这两种算法的原理、实现方式及适用场景,本文旨在帮助开发者更好地理解缓存管理机制,从而在实际应用中作出更合理的选择,有效提升系统性能和用户体验。
92 1
|
2月前
|
JavaScript 算法 索引
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
这篇文章深入分析了Vue中的diff算法,解释了其在新旧虚拟DOM节点比较中的工作机制,包括同层节点比较、循环向中间收拢的策略,并通过实例演示了diff算法的执行过程,同时提供了源码层面的解析,说明了当数据变化时,如何通过Watcher触发patch函数来更新DOM。
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
|
2月前
|
算法
聊聊一个面试中经常出现的算法题:组合运算及其实际应用例子
聊聊一个面试中经常出现的算法题:组合运算及其实际应用例子
|
2月前
|
消息中间件 存储 算法
这些年背过的面试题——实战算法篇
本文是技术人面试系列实战算法篇,面试中关于实战算法都需要了解哪些内容?一文带你详细了解,欢迎收藏!
|
2月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
2月前
|
Java C++
【Java基础面试十七】、Java为什么是单继承,为什么不能多继承?
这篇文章讨论了Java单继承的设计原因,指出Java不支持多继承主要是为了避免方法名冲突等混淆问题,尽管Java类不能直接继承多个父类,但可以通过接口和继承链实现类似多继承的效果。
【Java基础面试十七】、Java为什么是单继承,为什么不能多继承?
|
2月前
|
XML 存储 JSON
【IO面试题 六】、 除了Java自带的序列化之外,你还了解哪些序列化工具?
除了Java自带的序列化,常见的序列化工具还包括JSON(如jackson、gson、fastjson)、Protobuf、Thrift和Avro,各具特点,适用于不同的应用场景和性能需求。
|
2月前
|
Java
【Java基础面试三十七】、说一说Java的异常机制
这篇文章介绍了Java异常机制的三个主要方面:异常处理(使用try、catch、finally语句)、抛出异常(使用throw和throws关键字)、以及异常跟踪栈(异常传播和程序终止时的栈信息输出)。